Computing in Anonymous Dynamic Networks with One-Bit Communications
This work demonstrates that severe communication restrictions (one-bit messages) do not fundamentally limit distributed computation in anonymous dynamic networks, providing tight bounds and novel techniques for this extreme setting.
The paper shows that deterministic computation in anonymous dynamic networks is possible even when each agent broadcasts only one bit per round, achieving essentially the same computational power as the congested model with O(log n)-bit messages. The algorithms compute any function of the input multiset in O(n^3 log^2 n + U) rounds with a leader and known size bound, or in O(n^3 log^2 n) rounds without size knowledge, with an almost-matching lower bound of Ω(n^3) for large input universes.
We initiate the study of deterministic computation in anonymous dynamic networks where each agent broadcasts one bit per round and receives only the number of neighbors broadcasting each bit value. Despite this severe restriction, surprisingly rich global computation is possible. With a unique leader and a known upper bound $U$ on the network size $n$, we give a terminating algorithm for any computable function of the input multiset in $O(n^3\log^2 n+U)$ rounds, for inputs from a universe of size $N=2^{O(n\log n)}$. Without prior knowledge of $n$, we design a stabilizing algorithm for the same task running in $O(n^3\log^2 n)$ rounds. This essentially matches the state of the art for the congested model, where messages carry $O(\log n)$ bits and general computation takes $O(n^3)$ rounds. We also obtain comparable results for leaderless and multi-leader networks. We complement the upper bounds with an almost-matching lower bound of $$Ω!\left(\frac{n^2\log(N/n)}{\log n}\right)$$ rounds, which becomes $Ω(n^3)$ for $N=2^{Ω(n\log n)}$. The proof is information-theoretic, based on local histories, and holds even with a unique leader, known $n$ and $N$, and a communication graph restricted to a dynamically changing ring. Our algorithms extract global linear equations from local one-bit aggregate observations. A one-bit cut test yields conservation constraints on the sizes of indistinguishable agent classes; by refining these classes and collecting independent constraints, agents recover the required multiplicities. For unknown size, we introduce a self-correcting adaptive flooding primitive of independent interest. Thus, the computational power of congested anonymous dynamic networks is essentially preserved even when every message is compressed to one bit.