CMU-ISRI-07-117
Institute for Software Research
School of Computer Science, Carnegie Mellon University



CMU-ISRI-07-117

Probabilistic Opaque Quorum Systems

Michael G. Merideth, Michael K. Reiter

March 2007

CMU-ISRI-07-117.pdf

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


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

Byzantine-fault-tolerant service protocols like Q/U and FaB Paxos that optimistically order requests can provide increased efficiency and fault scalability. However, these protocols require n ≥ 5b + 1 servers (where b is the maximum number of faults tolerated), owing to their use of opaque Byzantine quorum systems; this is 2b more servers than required by some non-optimistic protocols. In this paper, we present a family of probabilistic opaque Byzantine quorum systems that require substantially fewer servers. Our analysis is novel in that it assumes Byzantine clients, anticipating that a faulty client may seek quorums that maximize the probability of error. Using this as motivation, we present an optional, novel protocol that allows probabilistic quorum systems to tolerate Byzantine clients. The protocol requires only one additional round of interaction between the client and the servers, and this round may be amortized over multiple operations. We consider actual error probabilities introduced by the probabilistic approach for concrete configurations of opaque quorum systems, and prove that the probability of error vanishes with as few as n > 3.15b servers as n and b grow.

35 pages


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu


Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu