For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Decentralized Voting Protocols and their Communication Structures
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/04/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
voting, decentralized commit protocols, communication structures,
Full Text: PDF>>
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.