Decentralized Voting Protocols and their Communication Structures


IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.4   pp.355-362
Publication Date: 1995/04/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
voting,  decentralized commit protocols,  communication structures,  

Full Text: PDF>>
Buy this Article

Voting is a general way of achieving mutual exclusion and synchronization in distributed systems with replicated data. In centralized voting protocols, a requesting node, which works as a central controller, exchanges messages in order to collect votes from other nodes. This paper proposes decentralized voting protocols, in which all nodes execute the same protocol and reach the same result in a decentralized and autonomous way. When a decentalized voting protocol is implemented by using one-round message exchange, it requires n(n1) messages, where n is the number of nodes. The number of messages can be reduced by using multiple-round message exchange. The paper describes the computation in each node in the form of the finite state automaton, and gives communication structures for it. It is shown that kn(n1/k1) messages are enough when messages are exchanged in k rounds.