Self-Stabilizing Clock Synchronization with 3-bit messages

Lucas Boczkowski, Amos Korman, Emanuele Natale

Abstract

Distributed systems, both biological and engineered, often rely on stochastic interactions to achieve global coordination. This paper addresses the challenge of achieving self-stabilizing clock synchronization and majority consensus in such environments while minimizing communication overhead. We present a "Message Reduction" compiler that recursively reduces message size, demonstrating that these fundamental tasks can be solved using only 3 bits per message in polylogarithmic time, even under severe fault conditions.

Introduction

In stochastic networks, such as sensor arrays or social insect colonies, agents interact randomly. A common model for this is the PULL model, where agents periodically sample the states of random neighbors. Two critical challenges arise in this setting: communication congestion and the need for self-stabilization. Self-stabilization requires a protocol to recover from any arbitrary initial state, including those where memory or clocks have been corrupted by an adversary.

Without a shared sense of time, agents cannot easily distinguish between current and stale information. While previous solutions required messages of size logarithmic to the number of agents or the clock period, this work proves that global coordination is possible with a constant message size of just 3 bits.

Methodology: The Message Reduction Compiler

The core contribution of this research is a general "Message Reduction Theorem." This theorem acts as a compiler for distributed protocols. If a protocol uses $\ell$-bit messages and exhibits "bitwise-independence"—meaning the protocol's correctness does not depend on all bits of a message originating from the same neighbor—it can be transformed into a protocol using only $\lceil \log \ell \rceil + 1$ bits.

Figure 2: The hierarchy of protocols developed using the Message Reduction Theorem to achieve 3-bit synchronization and consensus.

The transformation works by having agents use a small internal "indexing" clock to determine which single bit of the original $\ell$-bit message to display at any given time. By synchronizing these indexing clocks, agents can reconstruct the full message over time. This process is applied recursively: a protocol using $\log T$ bits is compiled down to $\log \log T$ bits, and eventually to a 3-bit floor. This methodology was used to derive Syn-Clock from a basic Syn-Simple protocol and to develop the Phase-Spread protocol for majority consensus.

Key Insights: Synchronizing through Phases

A pivotal insight is the concept of "clocks synchronizing clocks." To synchronize a large clock (modulo $T$), the system first synchronizes a much smaller clock. This smaller clock then coordinates when agents should observe specific bits of a larger clock, facilitating its stabilization.

Figure 1: A visualization of the clock phases, where different segments of the cycle are sensitive to different bit values (0 or 1).

Furthermore, the authors emulate active "PUSH" communication within the passive "PULL" model by utilizing clock parity. By displaying specific values on odd rounds and remaining "silent" (displaying a default state) on even rounds, agents can effectively signal information to their neighbors in a coordinated fashion.

Results and Performance

The proposed protocols achieve high efficiency and robustness:

  • 3-Bit Clock Synchronization: The Syn-Clock protocol achieves self-stabilizing synchronization modulo $T$ using 3-bit messages in $\tilde{O}(\log n \log T)$ rounds.
  • 3-Bit Majority Consensus: The Phase-Spread protocol solves Majority Bit Dissemination in $\tilde{O}(\log n)$ rounds, provided the initial majority has a sufficient margin.
  • Fault Tolerance: The system is resilient to up to $O(n^{1/2-\epsilon})$ Byzantine agents.
  • Memory Efficiency: Agents require only $O(\log T + \log \log n)$ bits of local memory.

Conclusion and Future Directions

This work establishes that 3 bits are sufficient for complex global coordination in stochastic, self-stabilizing environments. However, several questions remain. It is currently unknown if the message size can be further reduced to 1 or 2 bits while maintaining polylogarithmic convergence. Additionally, while the protocols are robust to a certain number of Byzantine agents, the exact limits of this resilience and the performance of consensus near a 50/50 split warrant further investigation.

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{boczkowski2019self,
  author = {Lucas Boczkowski and Amos Korman and Emanuele Natale},
  title = {{Self-Stabilizing Clock Synchronization with 3-bit messages}},
  journal = {Distributed Comput.},
  year = {2019},
  doi = {10.1007/s00446-018-0330-x},
}
Figure