Signed quorum systems

With n servers that independently fail with probability of p < 0.5, it is well known that the majority quorum system achieves the best availability among all quorum systems. However, even this optimal construction requires (n+1)/2 functioning servers out of n. Furthermore, the number of probes needed to acquire a quorum is also lower bounded by (n+1)/2. Motivated by the need for a highly available and low probe complexity quorum system in the Internet, this paper proposes signed quorum systems (SQS) that can be available as long as any O(1) servers are available, and simultaneously have O(1) probe complexity. SQS provides probabilistic intersection guarantees and exploits the property of independent mismatches in today’s Internet. Such key property has been validated previously under multiple Internet measurement traces. This paper then extensively studies the availability, probe complexity, and load of SQS, derives lower bounds for all three metrics, and constructs matching upper bounds. We show that in addition to the qualitatively superior availability and probe complexity, SQS also decouples availability from load and probe complexity, so that optimal availability can be achieved under most probe complexity and load values. Haifeng Yu is currently a Researcher at Intel Research Pittsburgh. He is also an Adjunct Assistant Professor at the Department of Computer Science, Carnegie Mellon University. His research interests cover the general area of distributed systems, as well as related fields such as operating systems, database systems, fault-tolerance and large-scale peer-to-peer systems. Haifeng receives his Ph.D. and M.S. from Duke University, and his B.E. from Shanghai Jiaotong University, China. More information about his research is available at http://www.cs.cmu.edu/yhf.