An efficient protocol for voting in distributed systems

A voting protocol that can reduce the communication costs in distributed systems significantly is proposed. The technique arranges nodes in small intersecting groups, such that a site, in absence of failures, needs to communicate only with members of its group to collect the quorum. A method for constructing such logical groups is presented. It is shown that the message overhead of any operation in a system of N nodes is O(√N) when there are no or few failures in the system. The availability and the communication overheads of the proposed protocol are compared with those of existing protocols