Multi-dimensional Quorum Sets for Read-Few Write-Many Replica Control Protocols

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