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


Write Markers for Probabilistic Quorum Systems

Michael G. Merideth, Michael K. Reiter

November 2007


Superceded CMU-ISRI-07-118R

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, they are hampered in that, like strict quorum systems, they allow for Byzantine-faulty servers to collude maximally to provide incorrect values to clients. We present a technique based on write markers that prevents faulty servers from colluding unless they are all also selected to be participants in the same update operations. We show that write markers increase the maximum fraction of faults that can be tolerated to b < n/ 2 from b < n/ 2.62, where n is the total number of replicas, for probabilistic masking quorum systems (compared with b < n/4 for strict masking quorum systems) and to
b < n/ 2.62 from b < n/ 3.15 for probabilistic opaque quorum systems (compared with b < n/ 5 for strict opaque quorum systems). In addition, with write markers, probabilistic masking quorums no longer require write quorums of large or maximal size in order to tolerate the maximum fraction of faults. We describe an implementation of write markers that is effective even if Byzantine clients collude with faulty servers.

25 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by