2022/04/05 by Giuseppe Antonio Di Luna, Giovanni Viglietta, Di Luna, Giuseppe A. +1 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2204.02128
openalex publication_date 2022/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give the first linear-time counting algorithm for processes in anonymous 1-interval-connected dynamic networks with a leader. As a byproduct, we are able to compute in 3n rounds every function that is deterministically computable in such networks. If explicit termination is not required, the running time improves to 2n rounds, which we show to be optimal up to a small additive constant (this is also the first non-trivial lower bound for counting). As our main tool of investigation, we introduce a combinatorial structure called "history tree", which is of independent interest. This makes our paper completely self-contained, our proofs elegant and transparent, and our algorithms straightforward to implement. In recent years, considerable effort has been devoted to the design and analysis of counting algorithms for anonymous 1-interval-connected networks with a leader. A series of increasingly sophisticated works, mostly based on classical mass-distribution techniques, have recently led to a celebrated counting algorithm in O(n4+ ε log3 (n)) rounds (for ε>0), which was the state of the art prior to this paper. Our contribution not only opens a promising line of research on applications of history trees, but also demonstrates that computation in anonymous dynamic networks is practically feasible, and far less demanding than previously conjectured.