Probabilistic quorum systems
Dahlia Malkhi, Michael K. Reiter, Rebecca N. Wright · 1997
Services replicated using a quorum system allow operations to be performed at only a subset (quorum) of the servers, and ensure consistency among operations by requiring that any two quorums intersect. In this paper we explore the consequences of requiring this intersection property to hold only with very high probability. We show that doing so can offer dramatic improvements in the performance and availability of the service, both for services tolerant of benign server failures and services tolerant of arbitrary (Byzantine) ones. We also prove a lower bound on the performance that can be achieved with this technique. 1 Introduction Quorums are tools for increasing the availability and efficiency of replicated services. A quorum system is a set of subsets of servers, every pair of which intersect. Intuitively, the intersection property guarantees that if a "write" operation is performed at one quorum, and later a "read" operation at another quorum, then there is some server that obse...