Computer Science Department
School of Computer Science, Carnegie Mellon University
Write Markers for Probabilistic Quorum Systems
Michael G. Merideth, Michael K. Reiter
Revised November 2008
Also appears as Institute for Software Research
Probabilistic quorum systems can tolerate a larger fraction of faults than can traditional (strict) quorum systems, while guaranteeing consistency with an arbitrarily high probability for a system with enough replicas. However, the masking and opaque types of probabilistic quorum systems are hampered in that their optimal load–a best-case measure of the work done by the busiest replica, and an indicator of scalability–is little better than that of strict quorum systems. In this paper we present a variant of probabilistic quorum systems that uses write markers in order to limit the extent to which Byzantine-faulty servers act together. Our masking and opaque probabilistic quorum systems have asymptotically better load than the bounds proven for previous masking and opaque quorum systems. Moreover, the new masking and opaque probabilistic quorum systems can tolerate an additional 24% and 17% of faulty replicas, respectively, compared with probabilistic quorum systems without write markers.