Search papers, labs, and topics across Lattice.
This paper investigates deterministic computation in anonymous dynamic networks where agents can only communicate one bit per round and receive aggregate information about their neighbors' broadcasts. The authors present algorithms that achieve global computation of any function of the input multiset in polynomial time, even without prior knowledge of the network size, while matching the performance of more complex communication models. Notably, they establish both upper and lower bounds on the computation time, demonstrating that the capacity for rich computation remains intact despite severe communication constraints.
Even with just one-bit communications, agents can perform complex global computations in dynamic networks, challenging assumptions about communication limits.
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 $$\Omega!\left(\frac{n^2\log(N/n)}{\log n}\right)$$ rounds, which becomes $\Omega(n^3)$ for $N=2^{\Omega(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.
