Probabilistic quorum systems
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.