Leaderless and Multi-Leader Computation in Disconnected Anonymous Dynamic Networks

We give a simple and complete characterization of which functions can be deterministically computed by anonymous processes in disconnected dynamic networks, depending on the number of leaders in the network. In addition, we provide efficient distributed algorithms for computing all such functions assuming minimal or no knowledge about the network. Each of our algorithms comes in two versions: one that terminates with the correct output and a faster one that stabilizes on the correct output without explicit termination. Notably, all of our algorithms have running times that scale linearly both with the number of processes and with a parameter of the network which we call "dynamic disconnectivity". We also provide matching lower bounds, showing that all our algorithms are asymptotically optimal for any fixed number of leaders. While most of the existing literature on anonymous dynamic networks relies on classical mass-distribution techniques, our work makes use of a recently introduced combinatorial structure called "history tree". Among other contributions, our results establish a new state of the art on two popular fundamental problems for anonymous dynamic networks: leaderless "Average Consensus" (i.e., computing the mean value of input numbers distributed among the processes) and multi-leader "Counting" (i.e., determining the exact number of processes in the network).