OPTIMIZING THE COSTS OF HIERARCHICAL QUORUM CONSENSUS

We study the problem of how to minimize the cost of maintaining consis tency among at least N copies of an object in an enviroment where the mix of read and write operations can vary. Quorum consensus requires t hat read and write operations must assemble appropriate quorums before an operation can succeed. The cost of an operation is proportional to the size of a quorum, and the objective is obviously to minimize the cost while still maintaining consistency. It is known that the quorum size can be reduced by organizing a number of copies into logical stru ctures such as grids and hierarchies. In this paper, we show (a) how m ethods based on grids and hierarchies can be treated in a common frame work, and (b) how these hierarchies can be optimized so as to minimize the cost of consensus. Of course, the optimal solution depends upon t he mix of read and write operations that is present. Consequently, giv en N copies of an object and a ratio of write operations F, our algori thms determine the optimal values for the number of levels in the hier archy and the read/write quorum sizes at each level. The algorithms, w hich run in O(N-1.63) and O(N-2) time, were tested, and the results ar e reported and discussed.