One-bit messages still enable rich computation in dynamic networks

In a new paper from arXiv, researchers Thibaut Blanc, Giuseppe Antonio Di Luna, and Giovanni Viglietta tackle a fundamental question: how much computational power is lost when agents in a dynamic network can only broadcast a single bit per round and only receive aggregate counts of how many neighbors sent a 0 or 1? Surprisingly, the loss is minimal. They present deterministic algorithms that can compute any computable function of the input multiset, even though agents have no identifiers and the network topology changes arbitrarily each round.

The key insight is to extract global linear equations from local one-bit aggregate observations. By using a novel “one-bit cut test,” agents can infer conservation constraints about the sizes of indistinguishable classes. By iteratively refining these classes and collecting independent constraints, they recover the required multiplicities. For unknown network sizes, they introduce a self-correcting adaptive flooding primitive that allows agents to stabilize on the correct output without ever exchanging more than one bit. The algorithms run in O(n³ log² n) rounds, matching the state of the art in the much more powerful congested model (where messages carry O(log n) bits). The lower bound shows this is nearly optimal, proving that Ω(n² log(N/n) / log n) rounds are needed even on a dynamically changing ring, which becomes Ω(n³) for large input universes. This work essentially closes the gap between one-bit and multi-bit communication in anonymous dynamic networks.