Decentralized Voting Protocols and their Communication Structures

概要

論文の詳細を見る
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 decentralized voting protocol is implemented by using one-round message exchange, it requires n(n - 1) 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(n^<1/k> - 1) messages are enough when messages are exchanged in k rounds.
社団法人電子情報通信学会の論文
1995-04-25