In a setting of replicated variables held by distributed servers, quorum systems provide efficient fault-tolerance by allowing operations to be performed at only a subset (quorum) of servers. Consistency among operations is ensured by requiring that any two quorums intersect. In this talk, I will discuss probabilistic quorum systems, in which the intersection property is required to hold only with very high probability. Probabilistic quorum systems can offer dramatic improvements in performance and availability, both for benign failures and Byzantine ones. I will present benign and Byzantine probabilistic quorum system constructions, as well as a lower bound on the performance that can be achieved with this technique.
(Joint work with Dahlia Malkhi and Michael Reiter.)