HIERARCHICAL QUORUM CONSENSUS - A NEW ALGORITHM FOR MANAGING REPLICATED DATA

This paper describes a new algorithm for managing replicated data. The standard quorum consensus method is an expensive means of maintaining consistency across multiple copies of an object if the number of copies is large because it typically requires at least a majority of the copies to form a quorum for a write operation. Our method is based on organizing the copies of an object into a logical, multilevel hierarchy, and extending the quorum consensus algorithm to such an environment. Several properties of the method are derived and optimality conditions are given for minimizing the quorum size. It is shown that, given a collection of n copies of an object, our method allows a quorum to be formed with n0.63 copies versus [GRAPHICS] copies in the case of the majority voting algorithm. Tradeoffs between ours and three other quorum-based methods are discussed, and the main features of each method are highlighted.