Multi-dimensional Quorum Sets for Read-Few Write-Many Replica Control Protocols
Multi-dimensional Quorum Sets for Read-Few Write-Many Replica Control Protocols
Files
Publication or External Link
Date
2003-02-27
Authors
Silaghi, Bujor
Keleher, Pete
Bhattacharjee, Bobby
Advisor
Citation
DRUM DOI
Abstract
e describe d-spaces, a replica control protocol defined in terms of
quorum sets on multidimensional logical structures. Our study is performed
in the context of transactional replica control protocols that support the
strongest form of replica consistency guarantees, one-copy
serializability. This work is primarily motivated by asymmetrical access
patterns, where the number of read accesses to data are dominant relative
to update accesses, i.e. where the consistency protocols should be
read-few write-many.
We show that quorums on d-spaces are optimal with respect to quorum group
sizes (message complexity). We present a detailed availability analysis
for read and write operations. For highly asymmetrical access patterns,
our approach approximates the read-one write-all protocol with respect to
read efficiency, while maintaining configurable levels of availability for
write operations. Specifically, we show that implementing a read-few
write-many replica protocol using $d$-spaces yields both superior
operation availability, as well as message complexity, to the hierarchical
quorum consensus method.
UMIACS-TR-2003-10