Institute for Software Research
School of Computer Science, Carnegie Mellon University


Write Markers for Probabilistic Quorum Systems

Michael G. Merideth, Michael K. Reiter

Revised November 2008


Supercedes CMU-ISRI-07-118

Also appears as Computer Science Department
Technical Report CMU-CS-07-165R

Keywords: Distributed systems, Byzantine fault tolerance, probabilistic quorum systems

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.

27 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by