DIMACS Special Year on Networks Seminar


Probabilistic Quorum Systems


Rebecca Wright
AT&T Labs - Research


AT&T Murray Hill Building, Room: 6B-101
Note: Visitors not from the MH building should use the MAIN ENTRANCE, and call Mike Reiter, phone number 5424, to let them in. Since entering the MH building takes time, visitors are requested to arrive no latter than 1:45pm.
AT&T Host: Mike Reiter


2:00 p.m
Friday, February 21, 1997

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.)

Document last modified on February 14, 1997