Coordinated Consensus in Dynamic Networks
The authors study several variants of coordinated consensus in dynamic networks. They assume a synchronous model, where the communication graph for each round is chosen by a worst-case adversary. The network topology is always connected, but can change completely from one round to the next. The model captures mobile and wireless networks, where communication can be unpredictable. They show that in the absence of a good initial upper bound on the size of the network, eventual consensus is as hard as computing deterministic functions of the input, e.g., the minimum or maximum of inputs to the nodes. They also give an algorithm for computing such functions that is optimal in every execution.