Multi-dimensional quorum sets for read-few write-many replica control protocols

Abstract

We describe d-spaces, a replica control protocol defined in terms of quorum sets on multi-dimensional logical structures. Our work is motivated by asymmetrical access patterns, where the number of read accesses to data are dominant relative to update accesses, i.e. where the protocols should be read-few write-many. D-spaces are optimal with respect to quorum group sizes. The quality of the tradeoff between read efficiency and update availability is not matched by existing quorum protocols. We also propose a novel scheme for implementing d-spaces that combines caching and local information to provide a best-effort form of global views. This allows quorum reconfiguration to be lightweight without impacting access latencies, even when the rate of membership changes is very high.