Delay-optimal quorum consensus for distributed systems
Ada Wai-Chee Fu · IEEE Transactions on Parallel and Distributed Systems · 1997
Given a set of nodes S, a coterie is a set of pairwise intersecting subsets of S. Each element in a coterie is called a quorum. Mutual exclusion in a distributed system can be achieved if each request is required to gel consensus from a quorum of nodes. This technique of quorum consensus is also used for replicated distributed database systems, and bicoteries and wr-coteries have been defined to capture the requirements of read and write operations in user transactions. The author is interested in finding coteries, bicoteries, and wr-coteries with optimal communication delay. The protocols take into account the network topology. They design delay-optimal quorum consensus protocols for network topologies of trees, rings, and clustered networks.