Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits

Lucas Boczkowski, Amos Korman, Emanuele Natale

Abstract

In large-scale distributed systems, agents often interact through random, local exchanges. Minimizing the communication overhead while maintaining system robustness is a critical challenge. This paper introduces a novel "compiler" that transforms complex distributed algorithms into highly efficient versions using only 3-bit messages. By leveraging a recursive Message Reduction Theorem, the authors provide self-stabilizing solutions for fundamental tasks like clock synchronization and majority consensus. These protocols are shown to converge rapidly from arbitrary initial states, establishing a new benchmark for the "information floor" in stochastic communication.

Introduction

Distributed systems, ranging from swarms of micro-robots to biological colonies, rely on decentralized coordination. In these environments, agents typically follow a "PULL" model of communication: an agent periodically samples a random neighbor to update its internal state. Two primary constraints govern these systems: bandwidth and fault tolerance. Communication is often the most energy-intensive operation, necessitating minimal message sizes. Simultaneously, the system must be "self-stabilizing"—capable of recovering from any arbitrary initial configuration caused by transient faults or adversarial interference.

This paper addresses the gap between message complexity and robustness. Specifically, it asks: what is the minimum number of bits required to achieve fast, self-stabilizing computation for core distributed tasks like clock synchronization and majority bit dissemination?

The Message Reduction Framework

The central contribution of this work is a general "compiler" based on a Message Reduction Theorem. This framework allows a protocol using $\ell$-bit messages to be converted into one using only $\lceil \log \ell \rceil + 1$ bits.

The Compiler Mechanism

The transformation relies on agents using a small internal clock to coordinate which specific bit of their state they reveal during an interaction. Instead of transmitting an entire $\ell$-bit string, an agent sends a single bit of the original message along with the index of that bit (requiring $\log \ell$ bits). For this to work, the underlying algorithm must possess the bitwise-independence property, meaning its correctness does not depend on receiving all bits of a neighbor's state simultaneously from a single source.

Recursive Refinement

The authors achieve the 3-bit limit through recursive application. A high-bit protocol is first reduced to a $\log \ell$-bit version. This intermediate protocol is then used to synchronize a clock, which in turn facilitates a second round of reduction. This iterative process allows the system to "bootstrap" its way down to a 3-bit message size without significantly compromising convergence time.

Roadmap of protocol development and message reduction.

Key Protocols and Applications

The paper demonstrates the power of this framework through two primary applications: Clock Synchronization and Majority Bit Dissemination.

Syn-Clock: Self-Stabilizing Synchronization

The authors develop Syn-Clock, a 3-bit protocol that achieves clock synchronization modulo $T$ in $\tilde{O}(\log n \log T)$ rounds. Unlike previous methods that required larger messages or lacked self-stabilization, Syn-Clock ensures that all $n$ agents eventually agree on a common time, even if they start with completely chaotic internal counters.

Phase-Spread: Majority Consensus

Building on the synchronized clock, the Phase-Spread protocol solves the Majority Bit Dissemination problem. In this task, agents must agree on the majority value of their initial inputs. The protocol uses the synchronized clock to divide time into "phases." During specific phases, agents are sensitive to certain values (0 or 1), allowing the majority opinion to propagate through the network efficiently.

Sensitivity phases in the majority dissemination protocol.

As shown in Figure 1, the clock cycle is split into regions where agents are "sensitive" to specific bits. This temporal coordination ensures that information spreads reliably despite the 3-bit bottleneck.

Results and Robustness

The theoretical analysis proves that these protocols are "probabilistically self-stabilizing." Regardless of the initial state, the system reaches a legal configuration with high probability:

  • Clock Sync: Achieved in $\tilde{O}(\log n \log T)$ rounds with 3 bits.
  • Majority Dissemination: Achieved in $\tilde{O}(\log n)$ rounds with 3 bits, assuming a clear initial majority.

Furthermore, the protocols exhibit inherent resilience to Byzantine faults, maintaining functionality even when a small fraction of agents behave maliciously.

Conclusion

The "Power of 3" bits stems from the ability to use two bits for a counter and one bit for data, providing just enough structure to coordinate complex behaviors. While this work establishes a significant lower bound for efficient self-stabilization, future research remains to determine if 2-bit or even 1-bit protocols can achieve similar performance. Expanding the compiler to handle algorithms without bitwise-independence also remains a promising avenue for future study.

Summary updated

Abstract

This paper considers the basic $\mathcal{PULL}$ model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of $n$ agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast. We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property that uses $\ell$-bits messages to one that uses only $\log \ell$-bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer $T$, within $\tilde O(\log n\log T)$ rounds w.h.p., and using messages that contain $3$ bits only. We then employ the new Clock Synchronization tool to obtain a self-stabilizing Majority Bit Dissemination protocol which converges in $\tilde O(\log n)$ time, w.h.p., on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction.
BibTeX
@article{boczkowski2019minimizing,
  author = {Lucas Boczkowski and Amos Korman and Emanuele Natale},
  title = {{Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits}},
  journal = {Distributed Comput.},
  year = {2019},
  doi = {10.1007/s00446-018-0330-x},
}
Figure