Efficient decentralized consensus protocols

Abstract

Decentralized consensus protocols are characterized by successive rounds of message interchanges. Protocols which achieve a consensus in one round of message interchange require O(N-squared) messages, where N is the number of participants. In this paper, a communication scheme, based on finite projective planes, which requires only O(N sq rt N) messages for each round is presented. Using this communication scheme, decentralized consensus protocols which achieve a consensus within two rounds of message interchange are developed. The protocols are symmetric, and the communication scheme does not impose any hierarchical structure. The scheme is illustrated using blocking and nonblocking commit protocols, decentralized extrema finding, and computation of the sum function.