The Hierarchical Ring Protocol: An Efficient Scheme for Reading Replicated Data

Voting is the traditional mechanism used for maintaining the consistency of replicated data in distributed systems. One of the problems involved in voting mechanisms is the size of the quorums needed on each access to the data. To reduce the quorum size needed for voting, some protocols for copy consistency organize the copies into some logical structure, and use the this structure during the voting process. We present two new protocols for maintaining copy consistency. Both protocols organize the copies into a ring structure, and use the adjacency property to reduce the read and write quorums. The flat ring protocol uses one single ring and achieves a read quorum of two copies (constant), and a write quorum equal to the majority of copies. The hierarchical ring protocol is a generalization of the flat ring protocol and uses a multi-level ring structure. The read quorum in the hierarchical ring protocol is independent on the total number of copies, and the write quorum is, in general,..