Integration: Reaching Consensus in Low-Diameter Wireless Networks

In a centrally controlled system consensus is often reached by decree: the central entity in charge of the system dictates the "consensus" to the rank-and-file. The situation is vastly different in a truly decentralized distributed system where the various entities in the system must agree on a common view - the consensus. Consensus is, in this regard, an exercise in integration, for it is the local, often parochial, views of the various participants that are being integrated in the process. We study the consensus problem in an eminently decentralized distributed system populated by anonymous participants communicating by radio. Our main contribution is to show that consensus can be reached in four deterministic communication steps in systems whose underlying graph has diameter two, even if the topology of the network is completely unknown to the participants. This result is relevant to all situations where a consensus must be reached by anonymous participants (who perhaps do not wish to reveal their identities) provided that the underlying graph has low diameter