Communication Complexity of Consensus in Anonymous Message Passing Systems

We consider the message complexity of achieving consensus in synchronous anonymous message passing systems. Unlabeled processors (nodes) communicate through links of a network. An adversary wakes up some subset of processors at possibly different times and assigns them arbitrary numerical input values. All other processors are dormant and do not have input values. Any message wakes up a dormant processor. The goal of consensus is to have all processors agree on one of the input values. We seek deterministic consensus algorithms using as few messages as possible. As opposed to most of the literature on consensus, the difficulty of our scenario are not faults (we assume that the network is fault-free) but the arbitrary network topology combined with the anonymity of nodes. For n-node networks of unknown topology we show a consensus algorithm using Ώ(n2) messages; this complexity is optimal for this class. We show that if the network topology is known, then the complexity of consensus decreases significantly. Our main contribution is an algorithm that uses Ώ(n2/3 log2 n) messages on any n-node network and we show that some networks require (n log n) messages to achieve consensus.