Decentralized voting protocols

Decentralized voting protocols, in which all nodes execute the same protocol and reach the same result in a decentralized and autonomous way, are proposed. 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 computation in each node is described in terms of a finite-state automaton, and communication structures for it are given. It is shown that kn(n1/k - 1) messages are sufficient when messages are exchanged in k rounds.