Paul Bastide

George Giakkoupis

Hayk Saribekyan

Self-Stabilizing Clock Synchronization with 1-bit Messages

We study the fundamental problem of distributed clock synchronization in a basic probabilistic communication setting. We consider a synchronous fully-connected network of n agents, where each agent has a local clock, that is, a counter increasing by one modulo T in each round. The clocks have arbitrary values initially, and they must all indicate the same time eventually. We assume a pull communication model, where in every round each agent receives an -bit message from a random agent. We devise several fast synchronization algorithms that use small messages and are self-stabilizing, that is, the complete initial state of each agent (not just its clock value) can be arbitrary.

We first provide a surprising algorithm for synchronizing a binary clock (T = 2) using 1-bit messages ( = 1). This is a variant of the voter model and converges in O(log n) rounds w.h.p., unlike the voter model which needs polynomial time. Next we present an elegant extension of our algorithm that synchronizes a modulo T = 4 clock, with = 1, in O(log n) rounds. Using these two algorithms, we refine an algorithm of Boczkowski et al. (SODA'17), that synchronizes a modulo T clock in polylogarithmic time (in n and T ). The original algorithm uses = 3 bit messages, and each agent receives messages from two agents per round. Our algorithm reduces the message size to = 2, and the number of messages received to one per round, without increasing the running time. Finally, we present two algorithms that simulate our last algorithm achieving < 2, without hurting the asymptotic running time. The first algorithm uses a message space of size 3, i.e., = log 2 (3). The second requires a rough upper bound on log n, and uses just 1-bit messages. More generally, our constructions can simulate any self-stabilizing algorithm that requires a shared clock, without increasing the message size and by only increasing the running time by a constant factor and a polylogarithmic term.

Introduction

We study the following clock synchronization problem. We have a synchronous fully-connected system of n processors, which we call agents. Each agent is equipped with a local clock, that is, a counter increasing by one modulo T in each round, where T is an integer common across all agents. The initial state of each agent, including the value of its clock, can be arbitrary, and the clocks of all agents must agree eventually. We assume a probabilistic pull communication model, where in each round each agent receives a message from an agent sampled uniformly at random. The message is just a function of the state of the sampled agent at the beginning of the round. In this setting, we investigate synchronization algorithms that are simple and efficient, converging in a small (polylogarithmic in n and T number of rounds and using small (constant-size) messages.

Clock synchronization is a fundamental distributed task, both in engineered and natural systems. In engineered systems, clock synchronization is an essential building block, as most algorithms require that processors have a common notion of time (e.g., so that they all start an execution at the same point in time). In natural systems, spontaneous synchronization of clock oscillators is ubiquitous, e.g., in populations of synchronously flashing fireflies, electrically synchronous pacemaker cells, and groups of women whose menstrual cycles become mutually synchronized [START_REF] Mirollo | Synchronization of pulse-coupled biological oscillators[END_REF].

In the model we consider, we assume agents take steps in synchronous rounds, but do not have a consistent numbering of the rounds. (E.g., agents regularly receive a common pulse.) Clock synchronization in this setting is often referred to as digital clock synchronization, or synchronous counting [START_REF] Ben-Or | Fast selfstabilizing byzantine tolerant digital clock synchronization[END_REF][START_REF] Dolev | Synchronous counting and computational algorithm design[END_REF][START_REF] Lenzen | Near-optimal self-stabilising counting and firing squads[END_REF][START_REF] Lenzen | Efficient counting with optimal resilience[END_REF]. The focus of most previous work on this problem has been to achieve resilience against Byzantine agents, whose behaviour can be arbitrary (and malicious), along with self-stabilization, which guarantees convergence from any configuration of the agents' states (and thus resilience to transient failures). However, achieving resilience to Byzantine agents is known to incur significant communication overhead, even for the simpler problem Our Contribution. We answer both the above questions in the affirmative. We first consider the simplest instance of the problem, namely, synchronizing a binary clock (T = 2). A natural approach, and one used by Boczkowski et al. [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF], is to exploit the similarity between clock synchronization and consensus, as the former is just an agreement problem on a counter. Indeed, there are several well-studied self-stabilizing consensus protocol, such as 3-median, 2-choices, and 3majority [START_REF] Becchetti | Stabilizing consensus with many opinions[END_REF][START_REF] Doerr | Stabilizing consensus with the power of two choices[END_REF][START_REF] Ghaffari | Nearly-tight analysis for 2choice and 3-majority consensus dynamics[END_REF], which can be trivially used to synchronize a binary clock in a self-stabilizing manner, in logarithmic rounds w.h.p. 1 However, all currently known such protocols require that each agent receives the clock values of two other agents per round.

It is plausible that one can drop this requirement, by having each agent use the message from the previous round together with the current round's. This approach, however, is not exactly equivalent to the original consensus protocol, thus requires a new analysis. (E.g., even if agents only update their state every other round, they need to do that simultaneously to achieve equivalence, but a synchronized binary clock is needed for that.) More importantly, the approach is unnecessarily complicated, requiring extra space in addition to the bit counter.

We present a surprisingly simple protocol for the problem: The state of an agent is just one bit, the actual clock. Whenever an agent u with clock 1 samples an agent v with clock 0, u changes its clock to 0. Also at the end of each round every agent increments its clock mod 2, i.e., flips its bit value. The next statement gives the properties of the protocol.

Theorem 1.1. There is a self-stabilizing algorithm for synchronizing a binary clock, which uses 1-bit messages and 2 states, and converges in O(log n) rounds w.h.p.

Our algorithm has a superficial similarity to the well-known voter model [START_REF] Liggett | Interacting Particle Systems[END_REF], where each agent has a binary state, and in each round each agent copies the state of a random agent. It is not hard to see that the dynamics of our algorithm is equivalent to that of a slightly modified voter model, where agents in state 1 update their state in odd rounds, and agents in state 0 in even rounds (this alternation is realized in our algorithm by flipping the agent states at the end of each round). This seemingly small modification has a dramatic affect on the convergence time, as the standard voter model converges in expected Θ(n) rounds [START_REF] Aldous | Reversible markov chains and random walks on graphs[END_REF].

Unlike the voter model, and similarly to the stabilising consensus algorithms with two messages, mentioned earlier, the process underlying our algorithm has a single fixed point (which, however, is not n/2), and a slight deviation from that point creates a bias away from the point, which increases the closer we move to 0 or n. Our analysis follows a similar line as that of [START_REF] Doerr | Stabilizing consensus with the power of two choices[END_REF].

Next we focus on extending our algorithm to synchronize a mod T clock, for a small integer T ≥ 3, as that can be used to directly improve the algorithm of [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF]. We devise a simple algorithm for synchronizing a mod 4 clock: The state of each agent consists of a 2bit string b 1 b 0 , that is the binary representation of the mod 4 clock. The message of an agent is just its most significant bit, b 1 . Whenever an agent u with b u 1 = 1 samples an agent v with b v 1 = 0, u flips both its clock bits, i.e., b u 1 ← 1 -b u 1 and b u 0 ← 1 -b u 0 . Also at the end of each round every agent increments its clock mod 4. The next statement gives the properties of the protocol. Theorem 1.2. There is a self-stabilizing algorithm for synchronizing a modulo 4 clock, which uses 1-bit messages and 4 states, and converges in O(log n) rounds w.h.p.

Though not immediately obvious, there is a simple connection between the new algorithm and our first algorithm, which reduces the analysis of the former to the latter. If we consider only every other round of an execution of the mod 4 algorithm, and look just at the most significant bit of the agents, the observed process is distributed identically to an execution of the mod 2 algorithm. It follows from Theorem 1.1 that after 2 • O(log n) rounds, all agents agree on the most significant clock bit w.h.p. Applying this argument twice (in parallel) starting from rounds 0 and 1, yields the desired logarithmic convergence time.

The two algorithms we have presented above are space-and message-optimal. They are also extremely simple, and thus, it is plausible that they are relevant to some biological or other natural processes, although we do not currently have any results in that direction.

We use the two algorithms as building blocks to implement a (more sophisticated) synchronization algorithm for a general modulo T clock. The high level approach is the same as in Boczkowski et al. [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF]. We use a recursive construction, with log * T layers. The first layer consists of two bits, and each subsequent layer consists of (roughly) the maximum number of bits that can be indexed using the bits of the previous layer. The bits in all layers taken together constitute the mod T clock, with the bits in the first layer being the least significant ones. Each message consists of two bits, one for synchronizing the mod 4 clock of the first layer (using our second algorithm above), and one bit with the value of the bit indexed by the first non-zero layer. This bit is then updated using our binary clock synchronization algorithm (instead of a consensus algorithm as done in [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF]). The precise way that the binary clock synchronization algorithm is used is slightly subtle, as it takes into account the frequency with which each bit in the clock increases, and the frequency in which it is updated. A detailed description of the construction is given in Section 6. The next statement summarizes the main properties of the protocol.

Theorem 1.3.

There is a self-stabilizing algorithm for synchronizing a modulo T clock, for any T that is a power of 2, which uses 2-bit messages and T states, and converges in Õ(log n log T ) rounds w.h.p. 2We also address the case where T is not a power of 2, but we discuss that later, in Remark 1.1, as it relies on some additional results.

Next we provide two general constructions that, when applied to the algorithm above, further reduce the message size. First, we introduce some terminology. The τ -clocked model is an extension of the (standard) model we have considered so far, equipped with a shared modulo τ clock, i.e., all agents have a consistent numbering of the rounds mod τ ; other than that, the agents' initial state can be arbitrary, as in the standard model. An algorithm S simulates (in the standard model) an algorithm A for the τ -clocked model, with delay d and slowdown s, if, roughly speaking, after at most d steps, S achieves the shared clock abstraction, and from then on all agents execute (in sync) a round of A once in every s rounds of S. In all statements below, the slowdown is constant and is a power of 2.

The algorithm of Theorem 1.3, which uses 2-bit messages, can be directly converted into an algorithm for the 2-clocked model with 1-bit messages: each message of the original algorithm is split into two 1-bit messages, sent in an odd and the next even round, while each agent updates its state only in even rounds. This approach works because our analysis does not require that the two bits are received from the same agent, a property termed bitwise-independence in [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF].

Our first construction achieves the following result.

Theorem 1.4. Any protocol A for the 2-clocked model using 1-bit messages and σ states, can be simulated in the standard model using a message space of size 3 and 4σ states, with delay O(log n) w.h.p. and constant slowdown.

The algorithm for simulating A in Theorem 1.4 is a simple adaptation of our modulo 4 clock synchronization algorithm. Agents simulate A when the most significant bit of their mod 4 clock is b 1 = 1 and use bit b 0 as the shared mod 2 clock value. When b 1 = 0 the message the agent sends is 0, as in the standard mod 4 clock protocol, and when b 1 = 1 it sends the corresponding message of the simulated algorithm A increased by one (i.e., the message is either 1 or 2). Thus an agent with b 1 = 1 which receives message µ ∈ {0, 1, 2}, updates its mod 4 clock if µ = 0, and updates its local state of the simulated algorithm A if µ = 0. The operation of the mod 4 clock synchronization algorithm is not affected by these changes, and once all clocks are in sync, agents correctly simulate A, twice every 4 rounds.

Next we show how to reduce the message size to a single bit. At a high level the protocol is divided into two phases, one for synchronizing a mod 4 clock, whose role is similar to the clock's in the previous construction, and a second phase which assumes already synchronized clocks, and is when the actual simulation takes place. An agent stays in the first phase for a logarithmic number of rounds before switching to the second, and from the second phase it moves back to the first if it has an indication that some agent is out of sync. Unlike all our previous results, this requires that agents know a rough upper bound on log n, which is hardcoded into the algorithm. 3 A detailed description of the algorithm and explanation of its various subtle details is given in Section 8.

Theorem 1.5. If each agent knows a linear upper bound on log n, then any protocol A for the 2-clocked model using 1-bit messages and σ states, can be simulated in the standard model using 1-bit messages and Θ(σ log n) states, with delay O(log n) w.h.p. and constant slowdown.

Applying Theorem 1.5 to the algorithm of Theorem 1.3, which, as we pointed out, can be transformed to an equivalent algorithm for the 2-clocked model with 1-bit messages (by the bitwise-independence property), we obtain the following.

Corollary 1.1. There is a self-stabilizing algorithm for synchronizing a modulo T clock, for any T that is a power of 2, which uses 1-bit messages and Θ(T log n) states, and converges in Õ(log n log T ) rounds w.h.p. S Using the construction of Theorem 1.5 and the algorithm of Corollary 1.1, we can efficiently simulate any algorithm A for the T -clocked model: In the 2clocked model, one can simulate A by running the mod T clock synchronization algorithm in odd rounds, and A in even rounds using that clock instead of a shared clock. The resulting algorithm can then be simulated in the standard model. Corollary 1.2. Any protocol A for the T -clocked model, where T is a power of 2, that uses 1-bit messages and σ states, can be simulated in the standard model using 1-bit messages and Θ(σT log 2 n) states, with delay Õ(log n log T ) w.h.p. and constant slowdown.

In a similar way, we can use Theorem 1.5 (or Theorem 1.4) and Corollary 1.1 to simulate any k-bit message protocol A for the T -clocked model, by a k-bit message protocol in the standard model.

So far we have assumed that T is a power of 2. We can easily extend Corollaries 1.1 and 1.2 to the case in which T is not a power of 2 as follows. Boczkowski et al. [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF] provided a simple and clever way to implement a mod T clock synchronization algorithm in the τ -clocked model, where τ = Θ(log n log T ) is a power of 2. The algorithm uses T states and 1-bit messages, and converges in O(log n log T ) rounds w.h.p. Simulating this algorithm using Corollary 1.2, we obtain an extension of Corollary 1.1 to arbitrary T . Combining then Theorem 1.5 with the resulting algorithm, we can obtain a similar extension of Corollary 1.2. The next remark gives the precise changes we need make to the statements of Corollaries 1.1 and 1.2.

Remark 1.1. For any integer T ≥ 2 that is not a power of 2, Corollary 1.1 still holds if we increase the number of states by factor τ = Θ(log n log T ), from Θ(T log n) to Θ(T log 2 n log T ). Similarly, if T is not a power of 2, Corollary 1.2 still holds if we increase the number of states from Θ(σT log 2 n) to Θ(σT log 3 n log T ).

Corollary 1.1 (together with Remark 1.1) settles the open problem posed by Boczkowski et al. [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF], establishing that fast clock synchronization is possible even when just single bit messages are used, and even when each agent receives a single message per round, from a random agent.

Boczkowski et al. [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF] showed the following message reduction theorem. Let A(η, ) denote the class of all algorithms in a variant of our model, where each agent receives η messages per round (from η random agents), and is the message size. The theorem says that any algorithm in A(η, ) with the bitwiseindependence property (i.e., each bit of each message can be received from a different random agent), can be simulated in A [START_REF] Alistarh | Spaceoptimal majority in population protocols[END_REF][START_REF] Aldous | Reversible markov chains and random walks on graphs[END_REF]. Using the construction of Theorem 1.5 and the algorithm of Corollary 1.1, and applying a similar reasoning as for Corollary 1.2, we can directly strengthen the message reduction theorem to allow simulation in the A(1, 1) model, with the same overhead as in the original theorem.

Related Work

The problem of self-stabilizing clock synchronization in fully-connected synchronous systems, has been studied extensively in the Byzantine failure model, under the names digital clock synchronization and synchronous counting [START_REF] Ben-Or | Fast selfstabilizing byzantine tolerant digital clock synchronization[END_REF][START_REF] Dolev | Synchronous counting and computational algorithm design[END_REF][START_REF] Dolev | On self-stabilizing synchronous actions despite byzantine attacks[END_REF][START_REF] Dolev | Self-stabilizing clock synchronization in the presence of byzantine faults[END_REF][START_REF] Lenzen | Near-optimal self-stabilising counting and firing squads[END_REF][START_REF] Lenzen | Efficient counting with optimal resilience[END_REF]. The goal has been to achieve resilience to the optimal 1/3 fraction of Byzantine agents, while at the same time minimizing the number of rounds and the message size. This requires significantly more communication than in our model, and typically all-to-all communication is employed in each round. Without Byzantine faults, the same problem has been studied as the self-stabilizing unison problem [START_REF] Arora | Maintaining digital clocks in step[END_REF][START_REF] Boulinier | Synchronous vs. asynchronous unison[END_REF][START_REF] Gouda | Stabilizing unison[END_REF]. The unison problem assumes an arbitrary underlying graph, unlike the fully-connected setting we consider in our work, and every process can read the state of all its neighbors in each round.

Clock synchronization is a fundamental task in the model of population protocols [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF][START_REF] Angluin | Self-stabilizing population protocols[END_REF]. This is an asynchronous model, where a random pair of agents interact in each step, by observing each other's state before updating their state. The synchronization task here is to implement a phase clock abstraction [START_REF] Angluin | The computational power of population protocols[END_REF], which allows agents to collectively count time in phases of Θ(n log n) interactions, with bounded skew. Efficient phase clock algorithms have been proposed in [START_REF] Alistarh | Spaceoptimal majority in population protocols[END_REF][START_REF] Gasieniec | Fast space optimal leader election in population protocols[END_REF], and self-stabilizing algorithms based on oscillation dynamics were proposed in [START_REF] Dudek | Universal protocols for information dissemination using emergent signals[END_REF][START_REF] Kosowski | Population protocols made easy[END_REF]. Very recently, a variant of the standard population protocol model was proposed [START_REF] Amir | Message complexity of population protocols[END_REF], where interacting agents can only observe a function of the other agent's state, similarly to our model. Among other results, they proposed a phase clock implementation using 1-bit messages.

The beeping model [START_REF] Afek | Beeping a maximal independent set[END_REF][START_REF] Emek | Stone age distributed computing[END_REF] is another model in which communication is severely restricted. There is typically an arbitrary underlying graph, and in each round each agent can either send a 'beep' to all its neighbors, or stay silent. Optimal clock synchronization algorithms have been proposed recently [START_REF] Feldmann | Timeand space-optimal discrete clock synchronization in the beeping model[END_REF], assuming arbitrary activation times, which is a weaker property than selfstabilization.

The stochastic process underlying our binary clock algorithm, behaves similarly to consensus dynamics that have been studied recently under the names of stabilizing consensus, majority consensus (if there are two opinions), or plurality consensus (for k > 2 opinions). Typically, in these algorithms, each agent observes the opinions of two (or more) random agents in each round and updates its opinion as a function of the observed opinions and its own, e.g., adopting the median value, or the majority [START_REF] Becchetti | Plurality consensus in the gossip model[END_REF][START_REF] Berenbrink | Ignore or comply?: On breaking symmetry in consensus[END_REF][START_REF] Doerr | Stabilizing consensus with the power of two choices[END_REF][START_REF] Ghaffari | Nearly-tight analysis for 2choice and 3-majority consensus dynamics[END_REF]]. An interesting variant, where each agent observes the opinion of only one other agent per round, called the undecided state dynamics, was analysed in [START_REF] Angluin | A simple population protocol for fast robust approximate majority[END_REF][START_REF] Becchetti | Stabilizing consensus with many opinions[END_REF]. A majority algorithm that uses push communication, and is optimal for a failure model where 1-bit messages are flipped independently with constant probability, was proposed in [START_REF] Feinerman | Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication[END_REF].

In [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF], a self-stabilizing majority protocol is described, which converges in Õ(log n) rounds w.h.p., uses 3 bits-messages, and each agent receives two messages per round (from random agents). Our improvement to the message reduction theorem of [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF], directly implies that the message size of the above protocol can be reduced to 1-bit, and the number of messages received to one, without hurting the convergence time.

Model

We assume a synchronous system of n agents that execute a protocol in a sequence of parallel rounds. The set of all agents is denoted N . In each round t, every agent u can sample one agent v uniformly at random, and receive information about v's state. Precisely, u receives a message m(s v ), where s v is v's state prior to round t, and m is a function specified by the protocol, whose domain is the agent state space. We call m the protocol's message function. After receiving m(s v ), u updates its state according to the protocol, completing the round. We assume the initial state of each agent (before the first round) is arbitrary.

We refer to the model described above as the standard model. We also consider an extension of this model, equipped with a shared modulo τ clock. Precisely, at the beginning of each round, the current value of the shared clock is broadcast to each agent. The initial value of the shared clock (at round 0) can be an arbitrary value in {0, . . . , τ -1}. We will refer to this model as the τ -clocked model.

For a protocol A in the standard model, we write A(s, msg) to denote the state of an agent after a round of the protocol, when the agent's state prior to the round is s, and the message it receives is msg. Similarly, if A is a protocol in the τ -clocked model, we define A(s, k, msg) as above, except that we additionally assume that the shared clock value in the round is k.

A protocol B simulates protocol A if for a random execution of B (from any initial configuration), there is some round d such that after d, all agents execute in sync a rounds of A in every b rounds of B periodically. (For a formal definition of a simulation see Appendix A.) We call B a simulator of A. The efficiency of the simulator is measured in terms of d and the ratio a : b, which we call delay and slowdown, respectively. We will use simulators to simulate in the standard model a protocol for the τ -clocked model, or to simulate a protocol in the same model but using shorter messages.

For a binary string s of length k, we write val(s) to denote the value of the string interpreted as a binary number, and write incr(s) to denote the string with value val(s) + 1 mod 2 k .

Binary Clock

In Algorithm 1, we present a simple binary clock synchronization protocol. The state of each agent is a single bit b ∈ {0, 1}, which is the clock value of the agent. In each round, first, every agent u whose clock is 1 samples a random agent v, and if v's clock is 0 then u sets its own clock to 0 (thus the message function is just m(b) = b). Then, every agent increases its clock modulo 2. The algorithm satisfies Theorem 1.1, i.e., uses 1bit messages and 2 states, and converges in O(log n) rounds w.h.p. The proof of the convergence time bound is similar to the analysis in [START_REF] Doerr | Stabilizing consensus with the power of two choices[END_REF], and can be found in Appendix B. Proof. Let N t ij denote the set of agents whose clock bits are b 1 = i and b 0 = j right after the first t rounds. The state transitions in round t + 1 are then as follows:

1. If u ∈ N t 00 , then u ∈ N t+1 01 . 2. If u ∈ N t 01 , then u ∈ N t+1 10 .
Algorithm 2: Modulo 4 clock synchronization protocol. Proof. From (5.1),

N t+2 10 ∪ N t+2 11 = N t+1 01 ∪ N t+1 10 = N t 00 ∪ N t 01 ∪ Z t+1 .
Let z t+1 = |Z t+1 |/n. The above equation then implies

y t+2 = (1 -y t ) + z t+1 .
It follows that for any y, y ∈ {0, 1/n, 2/n, . . . , n/n},

Pr[y t+2 = 1 -y + y | y t = y] = Pr[z t+1 = y | y t = y] = Pr[B(ny, 1 -y) = ny ],
since |Z t+1 | ∼ B(ny, 1 -y) given y t = y. We can also easily show that

Pr[x t+1 = 1 -y + y | x t = y] = Pr[B(ny, 1 -y) = ny ],
where x t is the fraction of agents whose binary clock is 1 after executing the first t rounds of Algorithm 1. (See Lemma B.1). Thus,

Pr[y t+2 = z | y t = y] = Pr[x t+1 = z | x t = y],
for any z. We present a protocol that uses 2-bit messages to synchronize a mod T clock, where T is a power of 2.

6.1 Protocol Description. Let T = 2 k , and suppose that k ≥ 3, as Sections 4 and 5 already give 1-bit message protocols for k ∈ {1, 2}. The state of each agent u ∈ N simply consists of exactly k bits necessary to store the clock value. We denoted the clock by a bit-string C = b k-1 . . . b 0 of length k, where b 0 is the least significant bit. We represent C as a concatenation of its substrings Q h , Q h-1 , . . . , Q 1 , which we call subclocks. The lengths of the sub-clocks are given using a sequence of functions (ρ i (l)) i≥0 defined on integers l ≥ 2 as follows. Let ρ(l) = log 2 (l + 1) . Then ρ i (l) is the iterative application of ρ on l, i times, i.e., (6.2)

ρ i (l) = l, if i = 0, ρ(ρ i-1 (l)), if i ≥ 1.
For any l ≥ 2, we define ν(l) = min{i ≥ 0 : ρ i (l) = 2}, which is the number of iterations until the sequence reaches its fixed point ρ(2) = 2. Next we define

λ = min    l ≥ 2 : ν(l) i=0 ρ i (l) ≥ k    . (6.3) The number of sub-clocks is then h = ν(λ) + 1. For i ∈ {1, . . . , h -1}, the length of the sub-clock Q i is l i = ρ h-i (λ), and the sub-clock Q h contains the remaining l h = k - h-1
i=1 l i bits. For convenience, we define s 0 = 0, and s i = s i-1 + l i for 1 ≤ i ≤ h. Thus, for the ith sub-clock we have

Q i = b si-1 . . . b si-1 .
We will write ⊕ to denote the standard XOR operator, i.e., for x, y ∈ {0, 1}, x ⊕ y = 1 if and only if x = y. Using this notation, the pseudocode of the mod T clock synchronization protocol is given in Algorithm 3.

We will write C u to refer to the clock of agent u, and C u,t to refer to the clock's value right after round t. The same notation is used for variables Q i and b j . The algorithm synchronizes the sub-clocks Q u i in the increasing order of i. The first sub-clock, Q u 1 , is a modulo 4 clock, which uses the first bit µ 1 of the message for synchronization, in Lines 3 to 4. The synchronization of this clock happens exactly as in Algorithm 2. The second bit µ 2 of the message is used for synchronizing the rest of the bits of the clocks. For each round, agent u uses π(C u ) to determine the bit to synchronize in that round. Let i be the index of the first non-zero sub-clock (i = +∞ if all sub-clocks are zero). If i < h and q = val(Q u i ) ≤ l i+1 , then we synchronize the qth least significant bit of sub-clock Q u i+1 (Line 16 returns its index in C u ). By the construction of the sub-clocks, 2 li -1 ≥ l i+1 , thus, val(Q u i ) suffices to index all the bits of Q u i+1 . If the condition in Line 15 fails, i.e., i ≥ h or val(Q u i ) > l i+1 , no bit synchronization takes place in that round. Now suppose p = π(C u ) ≥ 0 at some round. Under the conditions in Lines 8 to 10, the bit b u p adopts the received value µ 2 . Notice that if the bits at indices 0, . . . , p are synchronized, then b u p does not change as a result. Additionally, if for some p < p, the bit at index p is not the same in all clocks, then in the analysis we ignore the update of b u p . In other words, we analyse the synchronization of the bits one by one, starting from the least significant bit.

Therefore, we consider the case in which the bits up to index p -1 are synchronized at rounds t ≥ t 0 . In this case, π(C u,t ) = p implies π(C v,t ) = p for all agents v, and thus, Line 11 synchronizes bits at index p of all clocks.

We argue that the synchronization is completed in at most Õ(log T • log n) rounds. Our first observation is that the period of the clock Q u i (i.e., the number of rounds between two consecutive resets of

Q u i ) is 2 si . This implies that if π(C u,t ) = p, then π(C u,t ) = p for t = t + 2 si . It is not hard to compute that 2 si = Õ(log T ), since i < h.
Now observe that in the case in which p = s i in some round t, the condition on Line 8 is equivalent to that of Line 2 of Algorithm 1. Additionally, in the next 2 si rounds, as a result of clock increments on Line 12, the bit b u p will be flipped exactly once. It follows that the bits at index p of all clocks, considered only in rounds t when π(C u,t-1 ) = p, emulate the modulo 2 clock of Algorithm 1. By Theorem 1.1 and the observation that π(C u ) = p every Õ(log T ) rounds, we conclude the clock bits of index p are synchronized in Õ(log T • log n) rounds, w.h.p.

If s i < p in round t, the condition of the update on Lines 9 and 10 is more subtle. We argue that the bit c u,t-1 = b u,t-1 p ⊕ b u,t-1 si , when considered at almost all rounds t with π(C u,t-1 ) = p, emulates the binary clock from Algorithm 1. Precisely, we exclude the rounds t with π(C u,t-1 ) = p for which

(6.4) b t-1 si = • • • = b t-1 p-1 = 1.
We observe that when (6.4) does not hold, the bit b u,t-1 si flips exactly once in the next 2 si rounds due to the increments on Line 12, whereas b u p does not flip, and so bit c u flips exactly once, emulating Line 5 of Algorithm 1. On the other hand, if (6.4) holds, then in the next 2 si rounds, both b u si and b u p flip once due to Line 12, and so the bit c u we consider will not flip. Therefore, the condition on Lines 9 and 10, which prevents updating b u p in the last case, ensures that bit c u correctly emulates an execution of Algorithm 1. Again by Theorem 1.1, we conclude that the bits of the clocks at index p are synchronized in Õ(log T • log n) rounds, w.h.p. This implies that by considering the k = log T bits one by one (starting from the least significant one), we can prove that the clocks are synchronized in Õ(log 2 T • log n) rounds.

We can improve upon this sequential argument, by observing that for some z = s h-1 + log log n + Θ(1), the bits at indices z + 1, . . . , k -1 become synchronized simultaneously in Õ(log T • log n) rounds after the bits at indices 0, . . . , z are synchronized. Since z = O(log log T + log log n), almost all k bits become synchronized in parallel. Thus, by analysing the synchronization time of just the (z + 1) least significant bits, in a sequential order, we reduce the bound on the total synchronization time to Õ(log T • log n).

6.2 Properties. The protocol uses 2-bit messages and T = 2 k states, as promised by Theorem 1.3. Next we provide a detailed convergence analysis.

Theorem 6.1. For any T ≥ 8 that is a power of 2 and any initial configuration, Algorithm 3 synchronizes all mod T clocks in O(log T log n • (log log T ) 3 log log(nT )) rounds, w.h.p.

Remark 6.1. Algorithm 3 satisfies the bitwiseindependence property, as defined in [START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF]. This is because the two bits µ 1 µ 2 that an agent receives in one round serve different purposes: one for synchronizing Q 1 , and the other for synchronizing the rest of the sub-clocks. In particular, the proof of Theorem 6.1 remains the same if an agent receives the two bits of its message from two randomly selected agents.

6.3 Notation. For any round t ≥ 0, let r t ≤ k be the largest integer such that the r t least significant bits of all agents' clocks are the same immediately after round t, i.e., r t equals max{r ∈ N : b u,t j = b v,t j for all u, v ∈ N and 0 ≤ j < r}.

For an arbitrary agent u, let R t = b u,t rt-1 . . . b u,t 0 , which is the longest common suffix of the binary representations of all clocks.

Let E T denote an execution of Algorithm 3, which also describes the uniformly random choices that the agents make in each round. We will also consider an execution E 2 of Algorithm 1 which synchronizes a binary clock β. For an agent u and j ≥ 0, let β u,j be the value of the binary clock of u immediately after round j of E 2 . (Unlike in Algorithm 1, we use β instead of b in order to avoid confusion with the mod 4 clock in Algorithm 3). Proof. From the definition of π on Lines 13 to 17, it follows that for any agent u, π(C u ) ≥ 2 or π(C u ) = ⊥.

In particular, if the condition in Line 15 holds then the expression in Line 16 is at least s i , as val (Q i ) = 0, and s i ≥ s 1 = l 1 = 2. It follows that Lines 5 to 11 never affect the two least significant bits of clock C u . The remaining lines of Algorithm 3 are identical to the mod 4 clock presented in Algorithm 2. Therefore the lemma is proved by Theorem 5.1. Lemma 6.2. For any t ≥ 0, if r t ≥ 2 then (a)

r t+1 ≥ r t ; (b) val (R t+1 ) ≡ val (R t ) + 1 (mod 2 rt ).
Proof. Since r t ≥ 2, the 2-bit sub-clock Q 1 is synchronized, thus from Lemma 6.1 it follows that r t+1 ≥ 2. Therefore, we just need to prove that the updates on Lines 5 to 11 keep the r t least significant bits synchronized.

For an agent u, let p u = π(C u,t ) as on Line 5 in round t+1. Fix u such that p u = ⊥, if such u exists, and let i ≥ 1 be such that p u ∈ [s i , s i+1 -1] as in Line 7. If p u < r t , then the sub-clocks Q 1 , . . . , Q i are synchronized in all agents, and, in particular, for any agent v, val(

Q u i ) = val(Q v i ) = 0 for 1 ≤ i < i and val(Q u i ) = val(Q v i ) = 0. This implies that p v = π(C v,t ) = p u < r t .
Therefore, the second bit received by all agents in round t + 1 is the same and is equal to µ 2 = b u,t pu . This implies that after executing Lines 7 to 11, the r t least significant bits of the clocks remain synchronized. Finally, Line 12 is a simple incrementing operation which preserves the above property and implies that r t+1 ≥ r t in this case.

If p u ≥ r t , then either p v = ⊥ or p v ≥ r t for all agents v (otherwise, the argument above with respect to v gives a contradiction). In this case (and in the remaining case when p u = ⊥ for all u), p u and p v may not be equal for some two agents u and v, but the Lines 5 to 11 do not modify the r t least significant bits of the C u and C v . Once again, this implies that r t+1 ≥ r t , completing the proof of (a).

Finally, (b) holds due to Line 12 and the fact that in round t + 1 Lines 3 to 11 do not change any of the first r t bits of any agent clock.

Lemma 6.3. If 2 ≤ r t0 < k for some t 0 ≥ 0, then there is a round t = t 0 +O(2 s h-1 •log n) such that r t ≥ r t0 +1, w.h.p.
Proof. For conciseness we set p = r t0 . We need to bound the number of rounds until the bit at index p of the clocks is synchronized. Let i be such that p ∈ [s i , s i+1 -1]. This implies that for any two agents u, v, if t ≥ t 0 and 1

≤ i ≤ i, then Q u,t i = Q v,t
i . Fix an agent u and consider a round t ≥ t 0 .By the definition of function π, p = π(C u,t ) if and only if for

1 ≤ i < i, val(Q u,t i ) = 0 and val(Q u,t i ) = p -s i + 1, or equivalently, if val(C u,t ) ≡ (p -s i + 1) • 2 si-1 (mod 2 si ).
By Lemma 6.2, r t ≥ r t0 ≥ s i , so the s i least significant bits of C u,t and R t are identical, i.e., val(C u,t ) ≡ val(R t ) ≡ val(R t0 ) + t -t 0 (mod 2 si ).

Combining the last two equations above, we get that p = π(C u,t ) if and only if t = t j for some j ≥ 1, where t 1 = min{t ≥ t 0 : π(C u,t ) = p} < t 0 + 2 si , and t j+1 = t j + 2 si for j ≥ 1. Moreover, for any other agent v, if t ≥ t 0 , then it is also the case that p = π(C v,t ) if and only if t = t j for some j ≥ 1. In other words, the values (t j ) j≥1 are universal among agents. We consider two cases.

Case s i = p. In this case b p is the least significant bit of Q i+1 . Consider an execution E 2 of the binary clock protocol, and couple executions E T and E 2 as follows: If u samples v in round t j of E T , then u samples v in round j of E 2 . We set the initial clocks of the binary clock protocol β u,0 = b u,t1-1 p , and prove by induction that for any j ≥ 0, β u,j = b u,tj+1-1 p . The base case of j = 0 holds by construction. For j ≥ 1, suppose β u,j-1 = b u,tj -1 p , and that in round t j of E T agent u receives a message µ 1 µ 2 from agent v. The condition on Line 8 of Algorithm 3 is satisfied in round t j if b u,tj -1 p = 1, or equivalently by the inductive hypothesis, if β u,j-1 = 1 as in Algorithm 1. By the inductive hypothesis again, µ 2 = b v,tj -1 p = β v,j-1 = β , where β is the bit received by u in round j of E 2 . This implies that on Line 11 of Algorithm 3 and on Line 4 of Algorithm 1, the same bit value is assigned by both operations. We have that val(Q u,tj -1 i ) = 1 because s i = p, hence, the increment of C u in Algorithm 3 does not change the bit at index p of C u in round t j . In Algorithm 1 however, the clock β u changes in the corresponding round j. Therefore, b u,tj p = 1 -β u,j . Since t j+1 -t j = 2 si = 2 p , in exactly one of the rounds in {t j + 1, . . . , t j+1 -1}, the bit at index p of C u will flip (due to the increments), and thus, b u,tj+1-1 p = 1-b u,tj p = β u,j , which completes our inductive proof.

Finally, let j s ≥ 0 be the first round when the binary clock β is synchronized in E 2 . This implies that for t ≥ t js+1 , the bit b p is also synchronized among agents in E T , i.e., r t+1 ≥ r t0 + 1. From Theorem 1.1,

j s = O(log n), w.h.p. It follows t js+1 -t 0 ≤ (j s +1)•2 si = O(2 s h-1 • log n) w.h.p.
Case s i < p. In this case, we also use a coupling with a mod 2 clock, however in a more subtle way. Among the rounds t ∈ {t j } j≥1 , i.e., when π(C u,t ) = p, consider the ones where the condition in Lines 9 and 10 is met. Formally, let (6.5)

T u = t j : j ≥ 1, ∃ p ∈ [s i , p -1] s.t. b u,tj -1 p = 0 .
For any j ≥ 1, the bits of the clocks at indices up to p -1 are synchronized, thus, T v = T u for any agent v. We therefore simply refer to the sets T u as T . Denote by τ j the jth smallest element of T , and note that if t j / ∈ T , then t j+1 ∈ T , implying that, τ j ≤ t 2j . For any t ≥ 0, define c u,t = b u,t p ⊕ b u,t si . (The bit c u can be thought of as an implicit variable of Algorithm 3.) We prove that for t ∈ T , the bit c u,t-1 emulates the binary clock from Section 4. To formalize that, consider an execution E 2 of Algorithm 1, and couple this execution to execution E T restricted to rounds in T (similarly to the previous case). The binary clocks β u are initialized to β u,0 = c u,τ1-1 in E 2 . We prove, by induction, that for any j ≥ 0, β u,j = c u,τj+1-1 .

Once again the base case j = 0 holds by construction, so for j ≥ 1, we assume that β u,j-1 = c u,τj -1 . Let v be the agent from which u receives message µ 1 µ 2 in round τ j . Then, µ 2 = b v,τj -1 p . Since τ j ∈ T , the condition on Lines 9 and 10 of Algorithm 3 is satisfied in round τ j if c u,τj -1 = 0, or equivalently, if β u,j-1 = 0 due to the inductive hypothesis. Therefore, Line 11 of Algorithm 3 is executed in round τ j of E T if and only if Line 4 of Algorithm 1 is executed in round j of the coupled E 2 . Following the argument from the previous case, we have that after round τ j of E T , c u,τj = 1 -β u,j . As before, it remains to show that before the next coupled round τ j+1 the implicit bit c u is incremented exactly once, i.e., c u,τj+1-1 = 1 -c u,τj . (6.6) First suppose that τ j + 2 si ∈ T , i.e., the first coupled round after τ j is τ j+1 = τ j + 2 si . Since τ j , τ j+1 ∈ T , in each of C u,τj -1 and C u,τj+1-1 there is a bit equal to 0 at least on one of the indices in {s i , . . . , p -1}. This implies that the bit at index p does not change in rounds τ j + 1, . . . , τ j+1 -1 (which could only happen due to the increments on Line 12). On the other hand, the bit at index s i changes exactly once in those rounds. Thus,

b u,τj+1-1 p = b u,τj p and b u,τj+1-1 si = 1 -b u,τj si ,
which implies (6.6). If τ j + 2 si / ∈ T , then the next coupled round is τ j+1 = τ j + 2 • 2 si ∈ T . In this case, bit p flips once due to the increments, while bit s i flips twice (and does not change), because τ j+1 -τ j = 2 • 2 si . Thus, (6.6) holds in this case too.

Note that if the binary clock β is synchronized in round j s of E 2 , then so are the bits c u,t for t ≥ t 2(js+1) ≥ τ js+1 . This in turn implies that the bits b u,t p = c u,t ⊕ b u,t si are synchronized since s i ≤ r t . By the fact that t 2(js+1) -t 0 ≤ 2(j s + 2) • 2 si and Theorem 1.1, we complete the proof. Lemma 6.4. There is a constant η > 0, such that, if r t0 ≥ s h-1 + log log n + η, for some t 0 ≥ 0, then, there is a round t = t 0 +O(2 s h-1 •log n), such that the clocks of all agents are synchronized after round t (i.e., r t = k), w.h.p.

Proof. Consider an index p ∈ [r t0 , k-1]. We analyse the number of rounds before the bits at index p of the clocks are the same. The analysis is similar to the analysis of the case p > s i = s h-1 in Lemma 6.3; so we use the same notation as there. Unlike in Lemma 6.3, we do not have the assumption that all bits at indices 0, . . . , p -1 are synchronized. This implies that the sets T u , as defined in (6.5), are not identical, which was used to prove (6.6). We circumvent this problem by considering a set of rounds T , which is a subset of T u for all agents u. Moreover, T contains sufficiently many consecutive rounds from the sequence (t j ) j≥1 to synchronize bit p.

Let z = s h-1 + log log n + η ≤ r t0 , where constant η ∈ N will be defined later. Denote by τ the first round after t 0 , such that after round τ the bits at indices 0, . . . , z -1 are all 0, i.e.,

τ = min{t ≥ t 0 : val(R t ) ≡ 0 (mod 2 z )}. Note that τ -t 0 ≤ 2 z . Let T = {t j : j ≥ 1 and τ < t j < τ + 2 z -2 s h-1 }.
By Lemma 6.2, for any t ∈ T ,

val(R t-1 ) ≡ val(R τ ) + t -1 -τ ≡ t -1 -τ (mod 2 z ).
And since t -1 -τ < 2 z -2 s h-1 , there is some index p ∈ [s h-1 , z -1] such that the bit at index p of C u,t is 0 for all agents u, as r t ≥ z. Therefore, T ⊂ T u for all u. Similarly to (6.6), we obtain that if τ j is the jth smallest element of T and j < |T |, then for any u, c u,τ j+1 -1 = 1 -c u,τ j .

Unlike in Lemma 6.3, where T is infinite, we have to argue that T contains sufficiently many elements for bit p to become synchronized. By construction,

|T | ≥ 2 z-s h-1 -2 ≥ 2 η • log n -2.
By Theorem 1.1, there exists a constant η such that |T | rounds are sufficient for a binary clock to synchronize w.h.p. This implies that for τ max = max(T ), the bits at index p of the clocks are the same immediately after round τ max , w.h.p. Since τ max is independent of p, this statement holds for all p ∈ {z + 1, . . . , k -1}, thus all clocks are synchronized at round τ max w.h.p., by a union bound. Since

τ max ≤ τ + 2 z ≤ t 0 + 2 • 2 z = t 0 + O(2 s h-1 • log n), the proof is complete. Claim 6.1. s h-1 ≤ log k + 3 log log k + O(1). 4
Proof. We show by induction that for any i ∈ {1, . . . , h -1}, s i ≤ 3l i . The base case is trivial since s 1 = l 1 , so suppose s i-1 ≤ 3l i-1 for some i ≥ 2. Then,

s i = l i + s i-1 ≤ l i + 3l i-1 = l i + 3ρ(l i ) = l i + 3 log(l i + 1) ≤ 3l i ,
where the last inequality holds since l i ≥ 3. Therefore,

s h-1 = l h-1 + s h-2 ≤ l h-1 + 3l h-2 = ρ(λ) + 3ρ 2 (λ),
where λ is defined in (6.3), from which it also follows that λ ≤ k. Since ρ is a non-decreasing function and ρ(l) ≤ log(l + 1) + 1 ≤ log l + 2 for any l ≥ 2, for some constant c > 0,

s h-1 ≤ ρ(k) + 3ρ 2 (k) ≤ log k + 3 log log k + c.
This completes the proof.

Proof of Theorem 6.1. Let η be the constant guaranteed by Lemma 6.4, and let z = s h-1 + log log n+η . For r ∈ {2, . . . , z}, let τ r = min{t : r t = r} be the first round when the r least significant bits of the clocks C are synchronized. We have that τ 2 = O(log n) and, for r > 2, τ r -τ r-1 = O(2 s h-1 • log n), w.h.p., by Lemmas 6.1 and 6.3, respectively. By a union bound, therefore,

τ z = O(z • 2 s h-1 • log n). By Lemma 6.
A (s) + 1 ∈ {1, 2} if b 1 = 1,
where m A is the binary message function of A. Thus a single ternary digit suffices to encode each message of the simulator. The protocol is the same as Algorithm 2, except that, when the received message is µ = 0, then a round of A is executed, using µ -1 as the message and b 0 as the shared binary clock value. The simulator above satisfies the state space and message space conditions of Theorem 1.4. Next we show that the delay is logarithmic and specify the slowdown. is synchronized across all agents after O(log n) rounds, w.h.p. From that point on, all agents u execute a round of A in each round t at which b 1 = 1, using µ -1 as the message received in the simulated round and b 0 as the shared clock value. Thus the slowdown is 2 : 4.

Simulator with 1-bit Messages

We present a simulator that uses 1-bit messages, and simulates in the standard model any protocol A for the 2-clocked model with 1-bit messages.

8.1 Protocol Description. The pseudocode of the simulator is given in Algorithm 5. We assume that every agent has a linear upper bound on log n. It is not necessary that the bound is the same for all agents, but to simplify exposition we assume it is. Each agent u stores two modulo 4 clocks, b 1 b 0 and c 1 c 0 , and at any point, u is in one of two phases, φ ∈ {0, 1}. Both clocks follow the protocol in Algorithm 2. Clock b 1 b 0 is incremented in each round, in both phases, whereas clock c 1 c 0 is incremented only when the agent is in The transition of agent u from phase 0 to phase 1 is controlled by the agent's level . The level is used only when the agent is in phase 0, and in each round, is either reset to 0 or increased by one. Precisely, if conditions b 1 = 1 and µ = 0 hold (which, as we will see, means that the clocks b 1 b 0 of u and the v are not in sync), then is reset; otherwise it increases by one. After reaches the maximum value * = Θ(log n), the agent moves to phase 1. On the other hand, when an agent is in phase 1 and the conditions b 1 = 1 and µ = 0 hold, then the agent returns to phase 0. For technical reasons discussed later, the level is not reset in that case, but is set to * /2.

In phase φ = 0, agent u just runs the synchronization protocol for the modulo 4 clock b 1 b 0 , updating also the level as described above. In particular, the value of u's message is m = b 1 , similarly to Algorithm 2. When conditions b 1 = 1 and µ = 0 hold, then u flips its bits b 1 , b 0 in Line 6, as in Algorithm 2, but only if < * /2. If ≥ * /2 then the bits are not flipped (again for technical reasons discussed later).

In phase φ = 1, the message of u is m = 1 if b 1 = 1. Similarly to phase φ = 0, if conditions b 1 = 1 and µ = 0 hold, it means that u's clock b 1 b 0 is not in sync with v's. Then u moves back to phase 0 setting its level to * /2 as mentioned above (but does not flip its bits b

1 , b 0 ). When b 1 b 0 = 11 and µ = 0, agent u increments clock c 1 c 0 . When b 1 = 0 then u's message is m = 0 if b 0 • c 1 + (1 -b 0 ) • c 1 • m A (s) = 0 and 1 otherwise.
In particular, when b 1 b 0 = 01, then m = c 1 , and u updates its clock c 1 c 0 in that round. For technical reasons discussed later, clock c 1 c 0 uses the symmetric update rule of that in Algorithm 2, i.e., the clock's bits are flipped when c 1 = 0 and µ = 1 (compare Lines 4 and 18). When b 1 b 0 = 00 and c 1 = 1, then m = m A (s), and u executes a round of A using c 0 as the shared clock value.

We now provide some informal explanation of why the protocol works, and justify some subtle design choices. First, it is not hard to see that, once all clocks b 1 b 0 are synchronized, they stay in sync forever and agents never reset their level. This follows from the observation that if b 1 = 1 then m = 1, thus Lines 6, 7 and 14 are never executed again. Hence, after clock b 1 b 0 is synchronized, all agents reach phase 1 within a logarithmic number of rounds. Then clock c 1 c 0 is synchronized in logarithmic additional rounds, as all agents execute the modulo 4 synchronization protocol in sync (clock c 1 c 0 is updated when b 1 b 0 = 01, and incremented when b 1 b 0 = 11). Once both clocks are synchronized, all agents simulate algorithm A in sync, twice every 16 rounds.

It suffices thus to focus on the synchronization of clock b 1 b 0 . In the idealized case where all agents start at level 0 of phase 0, the clocks become synchronized before any agent reaches level * /2 (assuming * is large enough), as agents execute just the synchronization protocol of Algorithm 2. However, this is not the case in general, when agents start from arbitrary states. The main source of complication is that an agent u's message in phase 1 can be m = 1 even if b 1 = 0, whereas in Algorithm 2 it is always m = b 1 . This can result in "missed update opportunities," where b 1 is 1 for u and 0 for v, but u does not flip its bits b 1 , b 0 .

Even though it is possible that u's message is m = 1 when b 1 = 0 and φ = 1, as mentioned above, the protocol ensures that while u is in phase 1, m = 0 "sufficiently often." More concretely, by switching the roles of 0 and 1 in the condition for modifying the modulo 4 clock c 1 c 0 , we achieve that, as long as u stays in phase 1, we have c 1 = 0 when b 1 = 0 (and thus m = 0) at least twice every four cycles of clock b 1 b 0 . 5We use the above property, that for any agent in phase 1 we have m = 0 sufficiently often, to show that the following property holds w.h.p. If S is the set of agents that do not reach level 0 in the first Θ(log n) < * /4 rounds, then either S = ∅, or there is a set S ⊇ S, containing all but an -fraction of agents, such that all agents u ∈ S have the same clock value.

The case of S = ∅ is similar to the idealized case where all agents start at level 0 of phase 0, mentioned earlier, thus all clocks get synchronized quickly. If S = ∅, then we show that the small minority of the clocks which show a different value quickly converges to the majority value. To simplify this technical argument, we give an "edge" to the agents u ∈ S, by not modifying their clock when moving from phase 1 back to phase 0, and when resetting their level to zero from a level ≥ * /2.

8.2 Properties. The simulator satisfies the message size and state space conditions of Theorem 1.5, i.e., uses 1-bit messages and increases the number of states by at most a logarithmic factor. Next we specify the slowdown, and establish a logarithmic upper bound on the delay. 8.3 Notation. For any agent u ∈ N , integer t ≥ 0, and state variable σ (e.g., b 1 , , or φ) we write σ u,t to denote the value of variable σ in u's state right after the first t rounds. By m u,t we denote the value of the message function applied to the state of u right after

Let λ = mp -k. Pr[B(m, p) = k] = m k p k (1 -p) m-k = m! k!(m -k)! • p k (1 -p) m-k ≥ √ 2πm(m/e) m e 2 k(m -k)(k/e) k ((m -k)/e) m-k • p k (1 -p) m-k = √ 2πm e 2 k(m -k) • (mp) k k k • (m -mp) m-k (m -k) m-k = √ 2πm e 2 k(m -k) • k + λ k k • m -k -λ m -k m-k ≥ √ 2πm e 2 k(m -k) • e λ-λ 2 /k • e -λ-λ 2 /(m-k) = √ 2πm e 2 k(m -k) • e -mλ 2 /(k(m-k)) ,
where the second-last line was obtained using the fact 1 + x ≥ e x-x 2 , for x ≥ -1/2. Condition x ≥ -1/2 holds in our case, as λ/k ≥ 0, and

-λ/(m -k) = -(mp -k)/(m -k) ≥ -(mp)/m = -p ≥ -1/2.
Using Lemma B.4, we show the following anticoncentration result. Recall,

E[x t+1 | x t = x] = 1 -x 2 , from (B.2). Lemma B.5. For any 1/2 ≤ x ≤ 2/3 and 4n -1/2 ≤ δ ≤ (1/18) • n 1/2 , Pr[x t+1 ≤ 1 -x 2 -δn -1/2 | x t = x] ≥ 0.62 • δe -48δ 2 .
Proof. Suppose that x t = x. We have

Pr[x t+1 ≤ 1 -x 2 -δn -1/2 ] = Pr[x t+1 ≤ 1 -x + x(1 -x) -δx -1/2 ] = Pr[B(nx, 1 -x) ≤ nx(1 -x) -δx 1/2 ],
by (B.1). Let m = nx and p = 1 -x. Since 1/2 ≤ x ≤ 2/3, it follows that n/2 ≤ m ≤ 2n/3, 1/3 ≤ p ≤ 1/2, and 2n/9 ≤ mp ≤ n/4 (we implicitly use these bounds below). Let also λ = δn 1/2 , thus 4 ≤ λ ≤ n/18 ≤ mp/4. Then,

Pr[x t+1 ≤ 1 -x 2 -δn -1/2 ] = Pr[B(m, p) ≤ mp -λ] = 0≤k≤mp-λ Pr[B(m, p) = k] ≥ 0≤k≤mp-λ √ 2π e 2 • m k(m -k) • e -m•(k-mp) 2 k•(m-k) ≥ mp-2λ≤k≤mp-λ √ 2π e 2 • m m 2 /4 • e - m•(2λ) 2 (mp-2λ)(m-(mp-2λ)) ≥ λ • √ 2π e 2 • 2 √ m • e - m•4λ 2 (mp/2)•(m-mp/2) ≥ (3λ/4) • √ 2π e 2 • 2 2n/3 • e - m•4λ 2 (n/9)•(m-m/4) > 0.62 • δ • e -48δ 2 ,
where in the first inequality above was obtained using Lemma B.4.

B.2 Main

Lemmas. Recall that β 2 + β = 1 and β ≈ 0.618. The first lemma below upper bounds x t+2 when x t < β, and the second lemma upper bounds x t+1 when x t > β.

Lemma B.6. There is a constant c > 0, such that for any 0 < x < β,

Pr[x t+2 ≤ x -βx(β -x) | x t = x] ≥ 1 -2e -cnx(β-x) 2 .
Proof. Let z = β -x, and δ = z(2β -1)/4. We bound x t+1 using (B.4):

(B.5) Pr[x t+1 < 1 -x 2 -δx(1 -x) | x t = x] < e -δ 2 nx(1-x)/2 < e -c1nxz 2 ,
where

c 1 = (δ/z) 2 (1 -β)/2. Let y 0 = 1 -x 2 -δx(1 -x).
We use (B.3) to bound x t+2 given x t+1 = y, for y 0 ≤ y < 1. Let σ = δ • 1-y0 y(1-y) > δ. We have

1 -y 2 + σy(1 -y) ≤ 1 -y 2 0 + δ(1 -y 0 ) = (1 -y 0 )(1 + y 0 + δ) ≤ (x 2 + δx)(2 -x 2 + δ),
where for the last inequality we used that 1 -x 2 -δx ≤ y 0 ≤ 1 -x 2 . The rightmost side above is

(x 2 + δx)(2 -x 2 + δ) ≤ x(2x -x 3 + 4δ) = x(2(β -z) -(β -z) 3 + 4δ) = x(1 -z(3β -1) -z 2 (3β -z) + 4δ) ≤ x(1 -z(3β -1) + 4δ) = x(1 -zβ),
where the third line is obtained using

β 2 = 1 -β. It follows Pr[x t+2 > x(1 -zβ) | x t+1 = y] ≤ Pr[x t+2 > 1 -y 2 + σy(1 -y) | x t+1 = y] < e -σ 2 ny(1-y)/(2+σ) , by (B.3) = e -σny(1-y)•σ/(2+σ) ≤ e -δn(1-y0)•δ/(2+δ) ≤ e -δ 2 n(1-y0)/3 ≤ e -c2nxz 2 , (B.6)
where c 2 = (δ/z) 3 β(1 -β)/3, and the last inequality is obtained by substituting

1 -y 0 = x(x + δ(1 -x)) ≥ x(x + δ(1 -β)) = x(x • [(δ/z)(1 -β)] -1 + z) • [(δ/z)(1 -β)] ≥ x(x + z) • [(δ/z)(1 -β)] = xβ • (δ/z)(1 -β).
Equation (B.6) is also true when y = 1, as x t+2 = 0 in that case. Finally, we have Pr

[x t+2 > x(1 -zβ) | x t = x] ≤ Pr[x t+1 < y 0 | x t = x] + y≥y0 Pr[x t+2 > x(1 -zβ) | x t+1 = y] • Pr[x t+1 = y | x t = x] ≤ e -c1nxz 2 + e -c2nxz 2 • Pr[x t+1 ≥ y 0 | x t = x], by (B.5),(B.6) ≤ e -c1nxz 2 + e -c2nxz 2 .
The claim then follows.

Lemma B.7. There is a constant c > 0, such that for any

β < x < 1, Pr[x t+1 ≤ 2β -x | x t = x] ≥ 1 -e -cn(1-x)(x-β) 2 .
Proof. Let z = x -β, and δ = z(2β -1). We bound x t+1 using (B.3). We have

1-x 2 +δx(1-x) ≤ 1-(β+z) 2 +δ ≤ 1-β 2 -2βz+δ = β-z,
where for the last equality we used that

β 2 = 1 -β. Then, Pr[x t+1 > β -z | x t = x] ≤ Pr[x t+1 > 1 -x 2 + δx(1 -x) | x t = x] < e -δ 2 nx(1-x)/(2+δ) , by (B.3) ≤ e -cn(1-x)z 2 , for c = (δ/z)
w 1 = (ln n) 2 /n, w 0 = z 0 = β/2, z 1 = (α ln n/n) 1/2 , z 2 = (α/n) 1/2 , i 1 = max{i : w 0 (1 -γ) i ≥ w 1 } = ln(w 1 /w 0 )/ ln(1 -γ) , i 2 = max{i : z 0 /(1 + γ) i ≥ z 1 } = ln(z 0 /z 1 )/ ln(1 + γ) , i 3 = max{i : z 0 /(1 + γ) i ≥ z 2 } = ln(z 0 /z 2 )/ ln(1 + γ) , w 1 = w 0 • (1 -γ) i1 ∈ [w 1 , w 1 /(1 -γ)), z 2 = z 0 /(1 + γ) i3 ∈ [z 2 , z 2 (1 + γ)).
We partition interval (0, 1) into the following intervals A, B i , D i , G: A = (0, w 1 ],

B i = w 0 • (1 -γ) i , w 0 • (1 -γ) i-1 , 1 ≤ i ≤ i 1 , D i = β -z 0 /(1 + γ) i-1 , β -z 0 /(1 + γ) i , 1 ≤ i ≤ i 3 , G = (β -z 2 , 1).
We write left(I) to denote the left endpoint of interval I, e.g., left

(B i ) = w 0 • (1 -γ) i .
Let T be a subset of N = {0, 1, . . .} defined recursively as follows: 0 ∈ T , and for each t ∈ N, if t ∈ T and 0 < x t ≤ β -z 2 then t + 1 / ∈ T , otherwise t + 1 ∈ T . Later, in the proof of Lemma B.8, we will show an upper bound on the number of rounds t ∈ T for which x t / ∈ {0, 1}. Since, T contains at least every other round t ∈ N, the above bound (multiplied by 2) yields an upper bound on the total number of rounds before x t ∈ {0, 1}. In preparation for Lemma B.8, we prove a series of claims, for the different classes of intervals defined above.

In the next claim, a is the first t ∈ T for which

x t ∈ A, or a = ∞ if no such t exists. Claim B.1. Let a = min{t ∈ T : x t ∈ A}∪{∞}. Then, Pr[{a = ∞} ∪ {x a+2 = 0}] = 1 -O(ln 4 n/n).
Proof. Suppose that a < ∞. Then, from Lemma B.3, for any x ∈ A,

Pr[x a+1 = 1 | x a = x] ≥ 1 -nx 2 ≥ 1 -n(w 1 ) 2 = 1 -O(ln 4 n/n).
The claim then follows.

Claim B.2. For 1 ≤ i ≤ i 1 , let b i = min{t ∈ T : x t ∈ B i } ∪ {∞}. Then, Pr[{b i = ∞} ∪ {x bi+2 ≤ left(B i )}] = 1 -o(1/n). Proof. Suppose that b i < ∞, and recall that left(B i ) = w 0 • (1 -γ) i . Then, for any x ∈ B i , Pr[x bi+2 ≤ w 0 • (1 -γ) i | x bi = x] ≥ Pr[x bi+2 ≤ x • (1 -γ) | x bi = x] ≥ Pr[x bi+2 ≤ x • (1 -β(β -x)) | x bi = x] ≥ 1 -2e -cnx(β-x) 2
, by Lemma B.6

≥ 1 -2e -cnx1(β-w0) 2 = 1 -o(1/n).
The claim then follows.

Claim B.3. For 1 ≤ i ≤ i 2 , let d i = min{t ∈ T : x t ∈ D i } ∪ {∞}. Then, Pr[{d i = ∞} ∪ {x di+2 ≤ left(D i )}] = 1 -o(1/n).
Proof. Suppose that d i < ∞, and recall that left

(D i ) = β -z 0 /(1 + γ) i-1 . Then, for any x ∈ D i , Pr[x di+2 ≤ β -z 0 /(1 + γ) i-1 | x di = x] ≥ Pr[x di+2 ≤ β -(β -x) • (1 + γ) | x di = x] ≥ Pr[x di+2 ≤ x -βx(β -x) | x di = x] ≥ 1 -2e -cnx(β-x) 2 , by Lemma B.6 ≥ 1 -2e -cn(β-z0)(z1) 2 = 1 -o(1/n),
where the second inequality holds because

[β-(β-x)•(1+γ)]-[x-βx(β-x)] = (β-x)(βx-γ) ≥ 0.
The claim then follows.

In the next claim, d i,j is the jth smallest t ∈ T for which

x t ∈ D i , or ∞ if no such t exists. Claim B.4. For i 2 < i ≤ i 3 and j ≥ 1, let d i,j = min{t ∈ T : t > d i,j-1 , x t ∈ D i } ∪ {∞}, where d i,0 = -1. Let also f i = |{1 ≤ j ≤ log n : d i,j < ∞, x di,j +2 > left(D i )}|.

Then, for s

i = γ log n/(1 + γ) 2(i3-i) , Pr[f i < s i ] = 1 -O(1/n).
Proof. Suppose that d i,j < ∞, and recall that left

(D i ) = β -z 0 /(1 + γ) i-1 . As in the proof of Claim B.3, for any x ∈ D i , Pr[x di,j +2 ≤ β -z 0 /(1 + γ) i-1 | x di,j = x] ≥ 1 -2e -cnx(β-x) 2 . Since x > β/2 and β -x ≥ z 0 /(1 + γ) i = z 2 (1 + γ) i3-i ≥ z 2 (1 + γ) i3-i , 2e -cnx(β-x) 2 ≤ 2e -cn(β/2)(1+γ) 2(i 3 -i) α/n = 2e -(1+γ) 2(i 3 -i) ln 8/γ ≤ 4 -(1+γ) 2(i 3 -i) /γ . Therefore, Pr[x di,j +2 ≤ left(D i ) | x di,j = x] ≥ 1 -4 -(1+γ) 2(i 3 -i) /γ . For 1 ≤ j ≤ log n, let Y j = 1, if d i,j < ∞ and x di,j +2 > left(D i ); Y j = 0 otherwise. From the above, Pr[Y j = 1 | Y 1 , . . . , Y j-1 ] ≤ Pr[x di,j +2 > left(D i ) | Y 1 , . . . , Y j-1 ; d i,j < ∞] ≤ 4 -(1+γ) 2(i 3 -i) /γ . It follows that Y = 1≤j≤log n Y j is dominated by the binomial B log n, 4 -(1+γ) 2(i 3 -i) /γ . Thus Pr[Y ≥ s i ] ≤ log n s i • 4 -(1+γ) 2(i 3 -i) /γ si ≤ 2 log n • 4 -log n = 1/n.
The claim then follows, since f i = Y .

Claim B.5. For j ≥ 1, let g j = min{t ∈ T : t > g j-1 , x t ∈ G} ∪ {∞}, where g 0 = -1. Let also

h κ = |{1 ≤ j ≤ κ log n : g j < ∞, x gj +1 > left(G)}|.
Then, there is a constant κ such that

Pr[h κ ≤ (κ -1) log n] = 1 -O(1/n).
Proof. Suppose that g j < ∞, and recall left(G) = β-z 2 . We consider two cases, x gj ≥ β + z 2 and x gj < β + z 2 , and use Lemma B.7 and Lemma B.5, respectively. For

any β + z 2 ≤ x < 1, Pr[x gj +1 ≤ β -z 2 | x gj = x] ≥ Pr[x gj +1 ≤ 2β -x | x gj = x]
≥ 1 -e -cn(1-x)(x-β) 2 , by Lemma B.7

≥ c 1 ,
for some constant c 1 > 0, because in the range β + z 2 ≤ x < 1, the value of f (x) = cn(1-x)(x-β) 2 is minimized at one of the two extreme points, x = β + z 2 or x = 1 -1/n. For these points, f (β + z 2 ) = cn(1 -β + z 2 )(z 2 ) 2 ≥ c(1 -β + z 2 )α, and f (1 -1/n) = c(1 -1/n -β) 2 , thus at both points, f (x) is bounded away from 0. Next, for any β -z 2 < x < β + z 2 , and for δ = (2β -1)(1 + γ)α 1/2 ≥ (2β -1)z 2 n 1/2 , 1 - To complete the proof it suffices to show that: E implies x t ∈ {0, 1} for all t ≥ ĉ ln n, for some ĉ.

x 2 -δn -1/2 ≤ 1 -(β -z 2 ) 2 -δn -1/2 ≤ 1 -β 2 + 2βz 2 -δn -1/2 ≤ β -z 2 .
Let I be the set of the intervals in which we partitioned (0, 1) at the beginning of the analysis, i.e., I = {A} ∪ {B i : 1 ≤ i ≤ i 1 } ∪ {D i : 1 ≤ i ≤ i 3 } ∪ {G}. For each t ∈ T , either x t ∈ {0, 1}, or x t ∈ I for some I ∈ I; and t + 1 / ∈ T if and only if t ∈ I for some I ∈ I \ {G}. We use the following terminology. If x t ∈ I and I ∈ I \ {G}, we say t is a success at I if x t+2 ≤ left(I), and a failure if x t+2 > left(I). Similarly, if x t ∈ G, t is a success at G if x t+1 ≤ left(G), and a failure if x t+1 > left(G). For each I ∈ I, S(I) and F (I) denote the total number of successes and failures at I, respectively, and F -(I) = I <I F (I ), where I < I denotes that x < x for any x ∈ I , x ∈ I. Proof. The claim follows from the next two observations. First, if x t ∈ {0, 1} then x t ∈ {0, 1} for all t > t.

Second, if t is a success at interval I , then x t ≤ left(I ) for the next point t ∈ T , i.e., for t = t + 1 if I = G, or t = t + 2 otherwise. Therefore, if t 1 is a success at I, and t 2 is the next success or failure at I, then there exists a failure t 3 ∈ (t 1 , t 2 ) at some I < I.

Claim B.7. Suppose that event E holds. Proof. We prove (a) by contradiction. Suppose (a) does not hold, and let I be the leftmost interval (i.e., the one closest to 0) for which F (I) > 0. Then, F -(I) = 0. Let t be the first failure at I, and let t * ≤ t be the first success or failure at I. From E, t * is a success, thus t > t * . From Claim B.6(a), S(I) ≤ F -(I) + 1 = 1, thus S(I) = 1 since there is at least one success at I, namely t * . Then, from Claim B.6(b), the last failure at I must precede t * , which contradicts t > t * . The proof of (b) is similar. Suppose, for contradiction, that (b) does not hold, and let i > i 2 be the smaller index for which F (D i ) ≥ s i . Then,

F -(D i ) ≤ i2<i <i (s i -1) ≤ i2<i <i γ log n/(1 + γ) 2(i3-i ) ≤ γ log n • j≥1 1/(1 + γ) 2j = γ log n • 1 (1 + γ) 2 -1 < log n/2.
From Claim B.6(a),

S(D i ) ≤ F -(D i ) + 1 < log n/2 + 1 < log n -γ log i ≤ log n -s i .
But, from E, we have that S(D i ) < log n -s i implies F (D i ) < s i , which is a contradiction. Since x t ∈ {0, 1} for all t ≥ T , it follows from Claim B.8 that if E occurs, then x t ∈ {0, 1} for all t ≥ ĉ ln n, for some constant ĉ. This completes the proof of Lemma B.8.

Finally, to complete the proof of Theorem B.1, we just apply Lemma B.8 repeatedly, for a constant number of times, to obtain that, with the desired high probability, x t ∈ {0, 1} for all t ≥ c log n, for a large enough constant c .

Algorithm 1 :foreach round t do 2 if b = 1 4 b ← b 5 b ← 1 -b // increment clock mod 2 5 4 ClockTheorem 5 . 1 .

 1214512451 Binary clock synchronization protocol. state: b ∈ {0, 1} // binary clock value 1 then // copy the clock of a random agent 3 sample an agent v u.a.r., and let b be v's state prior to round t Modulo Next we present a mod 4 clock synchronization protocol. The pseudocode is given in Algorithm 2. The state of each agent consists of two bits b 1 , b 0 . These correspond to the bits in the binary representation of the modulo 4 clock, with b 1 being the most significant bit. Thus the clock value is 2b 1 + b 0 . In each round, first, every agent u with b 1 = 1 samples a random agent v, and if v's most significant bit is 0, then u flips both its bits (thus the message function is m(b 1 , b 0 ) = b 1 ). After that, every agent increases its clock modulo 4. The algorithm satisfies the state space and message size requirements of Theorem 1.2. Below we prove the logarithmic bound on the convergence time. Starting from any initial configuration, Algorithm 2 synchronizes all modulo 4 clocks in O(log n) rounds w.h.p.

1 foreach round t do 2 if b1 = 1 then 3 sample 4 if b 1 5 b1 ← 1 -

 234151 state: b1, b0 ∈ {0, 1} // clock value: 2b1 + b0 an agent v u.a.r., and let b 1 be v's most significant state bit prior to round t = 0 then // flip both bits b1; b0 ← 1 -b0 6 b1b0 ← incr(b1b0) // increment clock mod 4

Algorithm 3 :← µ2 12 C

 312 Modulo T = 2 k clock synchronization protocol. state: clock C = b k-1 . . . b0, also represented by the sub-clocks Q h , . . . , Q1, where Qi = bs i -1 . . . bs i-1 , for 1 ≤ i ≤ h msg function: m(C) is the 2-bit string b1b π(C) if π(C) = ⊥, and b10 otherwise 1 foreach round t do 2 sample an agent v u.a.r., and let µ1µ2 be the 2-bit message received from v // sync. mod 4 clock Q1 = b1b0 using µ1 3 if µ1 = 0 and b1 = 1 then 4 b1 ← 1 -b1; b0 ← 1 -b0 5 p ← π(C) // index of bit to sync. 6 if p = ⊥ then // i is the same as in Line 14 7 let i be such that p ∈ [si, si+1 -1] // condition for updating bp 8 if (si = p and bp = 1) or 9 (si < p and bp ⊕ bs i = 1 and 10 b p = 0 for some si ≤ p < p) then 11 bp ← incr(C) 13 function π(C) // i : index of first non-zero sub-clock 14 i ← min{i ≥ 1 : val(Qi) = 0} ∪ {+∞} 15 if i < h and val (Qi) ≤ li+1 then 16 return si + val (Qi) -1 17 else return ⊥

6. 4 Lemma 6 . 1 .

 461 Analysis. The mod 4 clocks Q u 1 = b u 1 b u 0 are synchronized after at most O(log n) rounds, w.h.p., and stay synchronized thereafter.

  4 and another application of a union bound, we have that the clocks are synchronized in O((z + 1) • 2 s h-1 • log n) rounds, w.h.p. By Claim 6.1, z = O(log log(nT )) and 2 s h-1 = O(log T •(log log T ) 3 ), and the proof is complete by substituting these values. 7 Simulator with Message Space of Size 3 In Algorithm 4, we present a simple protocol for simulating, in the standard model, any protocol A for the 2-clocked model that uses 1-bit messages. It is based on the modulo 4 clock synchronization protocol from Algorithm 2. Each agent stores the two bits b 1 , b 0 of the modulo 4 clock, plus the complete state s of the simulated algorithm A. The message function m of the simulator equals 0 if b 1 = 0, and m

Algorithm 4 :foreach round t do 2 if b1 = 1 then 3 sample 4 if µ = 0 then 5 b1 ← 1 - 6 else // execute a round of A 7 s

 42345167 Simulation in the standard model with message space size 3, of any protocol A for the 2-clocked model with 1-bit messages.state: b1, b0 ∈ {0, 1}; s: state of A msg function: m(b1, b0, s):= b1 • (1 + mA(s)),where mA is A's msg function 1 an agent v u.a.r., and let µ be the message received from v b1; b0 ← 1 -b0 ← A(s, b0, µ -1) 8 b1b0 ← incr(b1b0)

Theorem 7 . 1 .

 71 The simulator in Algorithm 4 has delay O(log n) w.h.p., and slowdown 2 : 4. Proof. By comparing Algorithm 4 with Algorithm 2, we observe that the algorithm for updating variables b 1 , b 0 is identical in the two protocols. Note, in particular, that in Algorithm 4, µ = 0 if and only if b 1 = 0 for the most significant bit of the sampled agent v. It follows from Theorem 5.1, that the two bit clock b 1 b 0

Algorithm 5 : 3 if φ = 0 then 4 if 6 b1 ← 1 - 7 ← 0 // reset level 8 else if < * then 9 ← + 1 // increase level 10 else // move to phase 1 & reset c1c0 11 φ ← 1 ; c1c0 ← 00 12 else // φ = 1 in this case 13 if b1 = 1 14 φ 19 c1 ← 1 - 21 s

 534617089110111121311419121 Simulation in the standard model with 1-bit messages, of any protocol A for the 2-clocked model with 1-bit messages. state: // two 2-bit clocks, b1b0 and c1c0 b1, b0, c1, c0 ∈ {0, 1} // phase and level counters φ ∈ {0, 1}; ∈ {0, . . . , * }, where * = Θ(ln n) s: state of A msg function: m := (b1 +φb0c1 +φ(1-b0)c1 •mA(s) > 0) ? 1 : 0, where mA is A's binary msg function 1 foreach round t do2 sample an agent v u.a.r., and let µ be the message received from v b1 = 1 and µ = 0 then 5 if < * /2 then // modify clock b1b0 b1; b0 ← 1 -b0 and µ = 0 then // move back to middle of phase 0 ← 0; ← * /2 15 else if b1 = b0 = 1 then // increment clock c1c0 16 c1c0 ← incr(c1c0) 17 else if b1 = 0 and b0 = 1 then // modify clock c1c0; 0 and 1 are switched in update condition 18 if c1 = 0 and µ = 1 then c1; c0 ← 1 -c0 20 else if b1 = b0 = 0 and c1 = 1 then // execute a round of A ← A(s, c0, µ) 22 b1b0 ← incr(b1b0) // increment clock b1b0 phase 1, and only every 4 rounds, whenever b 1 b 0 = 11. Thus, in phase 1, the two clocks constitute a modulo 16 clock, c 1 c 0 b 1 b 0 . In phase 1, an agent also simulates protocol A, twice every 16 rounds: an even round of A is executed when c 1 c 0 b 1 b 0 = 1000, and an odd round when c 1 c 0 b 1 b 0 = 1100.

Theorem 8 . 1 .

 81 The simulator in Algorithm 5 has delay O(log n) w.h.p., and slowdown 2 : 16.

5 = c 2 ,

 52 ThenPr[x gj +1 ≤ β -z 2 | x gj = x] ≥ Pr[x gj +1 ≤ 1 -x 2 -δn -1/2 | x gj = x] ≥ 0.62 • δe -48δ 2, by Lemma B.where c 2 > 0 is a constant. Combining the two cases above we obtain that, for any x ∈ G,Pr[x gj +1 ≤ left(G) | x gj = x] ≥ c 3 = min{c 1 , c 2 }. Let κ = 4/c 3 . For 1 ≤ j ≤ κ, let Y j = 1, if g j = ∞ or x gj +1 ≤ β -z 2 ; Y j = 0, otherwise. Then Pr[Y j = 1 | Y 1 , . . . , Y j-1 ] ≥ Pr[x gj +1 ≤ left(G) | Y 1 , . . . , Y j-1 ; g j < ∞] ≥ c 3 . It follows that Y = 1≤j≤κ log n Y j dominates the binomial distribution B(κ log n, c 3 ). Thus Pr[Y ≥ log n] ≥ Pr[B(κ log n, 4/κ) ≥ log n] ≥ 1-O(1/n),by a standard Chernoff bound. The claim then follows, ash k = κ log n -Y .Combining the previous claims we show the following lemma, which bounds the convergence time, i.e., the number of rounds before x t ∈ {0, 1}.Lemma B.8.There is a constant ĉ > 0, such that for any x ∈ (0, 1) and k ≥ ĉ ln n,Pr[x t+k ∈ {0, 1} | x t = x] = 1 -O(ln 4 n/n).Proof. W.l.o.g., we assume that t = 0, and x 0 = x. The following event E is the intersection of all events considered in Claims B.1 to B.5,E = {a = ∞} ∪ {x a+2 = 0} ∩ 1≤i≤i1 {b i = ∞} ∪ {x bi+2 ≤ left(B i )} ∩ 1≤i≤i2 {d i = ∞} ∪ {x di+2 ≤ left(D i )} ∩ i2<i≤i3 {f i < s i } ∩ {h κ ≤ (κ -1) log n}.From the claims above and a union bound, we get Pr[E] = 1 -O(ln 4 n/n).

Claim B. 6 .

 6 For any I ∈ I, (a) S(I) ≤ F -(I) + 1. (b) If S(I) = F -(I) + 1 and F (I) > 0, then the last failure at I precedes the last success at I.

  (a) For anyI ∈ {A} ∪ {B i ; 1 ≤ i ≤ i 1 } ∪ {D i ; 1 ≤ i ≤ i 2 }, F (I) = 0. (b) For i 2 < i ≤ i 3 , F (D i ) ≤ s i -1, where s i is defined in Claim B.4.(c) F (G) ≤ (κ -1) log n, where κ is the constant from Claim B.5.

Finally 1 ≤F

 1 , for (c) we have from Claim B.6(a),S(G) ≤ F -(G) + 1 = F -(D i3 ) + F (D i3 ) + log n/2 + s i3 + 1 < log n, and from E, S(G) < log n implies that F (G) ≤ (1 -κ) • log n. Let T = min{t : x t ∈ {0, 1}}. Claim B.8. If event E holds, then T = O(log n).Proof. Since T contains at least every other t ∈ N,T ≤ 2 • I∈I (S(I) + F (I)) ≤ 2 • I∈I (F -(I) + F (I) + 1) = 2 • I∈I F (I) • (|{I : I < I }| + 1) + 2 • |I|,where the second inequality was obtained using Claim B.6. From Claim B.7,I∈I F (I) • (|{I : I < I }| + 1) = i2<i≤i3 (D i ) • (i 3 -i + 1) + F (G) ≤ i2<i≤i3 (s i -1) • (i 3 -i + 1) + (κ -1) log n. Also i2<i≤i3 (s i -1) • (i 3 -i + 1) ≤ i2<i≤i3 γ log n/(1 + γ) 2(i3-i) • (i 3 -i + 1) = γ log n • 0≤j<i3-i2 (j + 1)/(1 + γ) 2j = O(log n).Last, we have |I| = 2 + i 1 + i 3 = O(log n). Combining all the above yields T = O(log n).

  samples an agent from N t 00 ∪ N t 01 , and u ∈ N t+1 00 otherwise. Let Z t+1 be the set of agents u ∈ N t 10 ∪ N t Claim 5.1. Let y t = |N t 10 ∪ N t 11 |/n. W.h.p., y t ∈ {0, 1} for all t ≥ c log n, for some constant c.

	11 that sample 01 in round t + 1. It follows 00 ∪ N t an agent from N t
	(5.1)	N t+1 01 ∪ N t+1 10 = N t 00 ∪ N t 01 ∪ Z t+1 N t+1 10 ∪ N t+1 11 = N t 01 ∪ N t 10 .

3. If u ∈ N t 10 , then u ∈ N t+1 10 if u samples an agent from N t 00 ∪ N t 01 , and u ∈ N t+1 11 otherwise. 4. If u ∈ N t 11 , then u ∈ N t+1 01 if u

  If y t = y t+1 = 0, then the above equations imply that|N t 10 | = |N t 11 | = |N t 01 | = 0, thus |N t 00 | = n. If y t = y t+1 = 1, then |N t 00 ∪ N t 01 | = n(1 -y t ) = 0 and |N t 11 ∪ N t 00 | = n(1 -y t-1 ) = 0,thus |N t 10 | = n. Similarly, if y t = 0, y t+1 = 1 we obtain |N t 01 | = n, and if y t = 1, y t+1 = 0 then |N t 11 | = n.

	From Claims 5.1 and 5.2, there is a t = Θ(log n)
	such that |N t ij | = n w.h.p. A simple inductive argument
	shows that for all t > t, no agent with b 1 = 0 is sampled
	in round t , and all clocks have value 2i+j+(t -t) mod 4
	after the round. The theorem then follows.
	6 Modulo T Clock

Since the sequences (x t ) t≥0 and (y 2t ) t≥0 are Markov chains, the equation above implies they have the same distribution, if they start from the same initial state. From Theorem 1.1, we have that w.h.p. x t = {0, 1} for all t ≥ c log n, for some constant c , and any initial configuration. It follows y 2t = {0, 1} for all t ≥ c log n, w.h.p., for any initial configuration. Moreover by taking as initial configuration the one reached after the first round, we obtain also that y 2t+1 = {0, 1} for all t ≥ c log n, w.h.p. Therefore, by a union bound, w.h.p., y t = {0, 1} for all t ≥ 2c log n + 1. Claim 5.2. If y t ∈ {0, 1} and y t+1 ∈ {0, 1}, then |N t ij | = n for some pair i, j. Proof. We have |N t 10 ∪ N t 11 | = ny t , and from (5.1), |N t 01 ∪ N t 10 | = |N t+1 10 ∪ N t+1 11 | = ny t+1 .

With high probability (w.h.p.) means with probability at least 1-O(n -c ), for a constant c > 0 that can be made arbitrarily large at the cost of the other constants involved (e.g., the constant factor in the logarithmic number of rounds, in the case above).

The tilde notation hides factors that are at most polynomial in log log T and log log n.

Having some knowledge of n is a common assumption in the literature, e.g., the final synchronization algorithm of[START_REF] Boczkowski | Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits[END_REF] also uses an upper bound on log n.

The coefficient 3 can be made arbitrarily close to 1, by using a more refined argument. This implies that the factor (log log T ) 3 in the bound of Theorem 6.1 can be improved to almost log log T .

The reason is that the possible state transitions for clock c 1 c 0 (after un update and increment) are: 00 → {00, 01}, 01 → {10, 11}, 10 → 11, and 11 → 00, thus from any state, c 1 = 0 after at most two transitions.

The proof of this lemma relies on the fact that the update condition for modifying clock c 1 c 2 , in Line 18, is the symmetric of that in Line 4, with the roles of 0 and 1 swapped.

Acknowledgements. We are deeply indebted to Emanuele Natale for introducing the problem to us, for helping us to devise the binary clock protocol, for pointing out related work, and for helpful discussions through the course of this project.

Partially

supported by ANR Projects PAMELA (ANR-16-CE23-0016-01) and DESCARTES (ANR-16-CE40-0023).

University of Cambridge, UK. Supported by Gates Cambridge programme.

the first t ≥ 0 rounds. By µ u,t we denote the message that u receives in round t ≥ 1, i.e., µ u,t = m v,t-1 , if u samples agent v in round t.

We assume * = Θ(log n) is a multiple of 8. For any t ≥ 0, i, j ∈ {0, 1}, and 0 ≤ k ≤ * , we define the following sets of agents,

Also, for t ≥ 1,

and note that Z t1,t2 = L t2 t2-t1 if t 2 -t 1 < * /2, and Z t1,t2 ⊆ L t2 t2-t1 if t 2 -t 1 ≤ * .

8.4 Analysis. All lemmas below hold for any given round t ≥ 0, and any fixed value for the configuration C t of the agents' states after that round. The first lemma says that once all clocks b 1 b 0 get synchronized, they stay in sync forever.

Lemma 8.1.

Proof. Suppose, for contradiction, that B t ij = N , and u / ∈ B t+1 incr(ij) for some u. Consider round t + 1, and let v be the agent that u samples in that round. Since u increments b 1 b 0 in Line 22, but u / ∈ B t+1 incr(ij) , it follows that u executes Line 6 (which is the only other line where the clock is modified). Thus, the conditions in Line 4 hold, i.e., b u,t 1 = 1 and µ u,t+1 = 0. Since u, v ∈ B t ij and b u,t 1 = 1, it follows b v,t 1 = 1, and thus m v,t = 1. Then µ u,t+1 = m v,t = 1, which contradicts µ u,t+1 = 0.

Next we give a simple lower bound on the number of agents u ∈ B, for a given set B ⊆ B t 1 , that receive message 1 in round t + 1. Proof. Since m u,t = 1 for any u ∈ B t 1 , |B \ U t+1 | is lower bounded by the number of agents u ∈ B that sample an agent from B t 1 in round t + 1. Given |B| = k 1 and |B t 1 | = k 2 , the expected number of those agents is k 1 • (k 2 /n). The claim then follows by a standard Chernoff bound.

Roughly speaking, the next lemma implies that for any interval of 12 rounds and any agent u, either m u,t = 0 for at least two consecutive rounds t in that interval, or u ∈ U t for some t in the interval. 6 Lemma 8.3.

(a) If u ∈ B t 00 ∩ (Φ t 0 ∪ C t 0 ), then m u,t = m u,t+1 = 0. (b) For any u, if τ 1 = min{t ≥ t : u ∈ B t 00 ∩ (Φ t 0 ∪ C t 0 )}, and τ 2 = min{t > t : u ∈ U t }, then min{τ 1 , τ 2 } ≤ t + 11.

Proof. We show (a) first. Equation m u,t = 0 follows from the definition of the message function, and assumption u ∈ B t 00 ∩(Φ t 0 ∪C t 0 ). We now consider m u,t+1 . Since u ∈ B t 00 we have u ∈ B t+1 01 , as b u,t 1 = 0 and thus Line 6 is not executed in round t+1. Then, from the definition of the message function, m u,t+1 = 0 if u ∈ Φ t+1 0 , and

, u moved from phase 0 to phase 1 in round t + 1, then it must have executed Line 11 in round t + 1, thus c u,t+1 1 = 0, as desired. So, suppose that u ∈ Φ t 1 . Then, from the assumption that u ∈ B t 00 ∩ (Φ t 0 ∪ C t 0 ), it follows that u ∈ C t 0 . Since u does not change clock c 1 c 0 in round t + 1, as u ∈ B t 00 , it follows c u,t+1 1 = c u,t 1 = 0. This completes the proof of (a).

Next we prove (b). Suppose u ∈ B t ij . Suppose also that for all t < t ≤ t + 11, u / ∈ U t (otherwise (b) holds). This implies that u does not execute Line 6 in any round t ∈ {t + 1, . . . , t + 11}. Then, due to Line 22, u's clock b 1 b 0 is incremented by exactly one in each of these rounds.

Let

Suppose now that u ∈ Φ t0 1 . Then u ∈ Φ t 1 for al t 0 < t ≤ t + 11, as u does not execute Line 14 at any of those rounds t . Let t 1 = t 0 + 4 and t 2 = t 0 + 8 ≤ t + 11. Then u ∈ B t 00 for all t ∈ {t 0 , t 1 , t 2 }. Thus, to prove (b), it suffices to show that u ∈ C t 0 = 0, for some t ∈ {t 0 , t 1 , t 2 }.

Suppose that c u,t0 1 = 1, otherwise the claim above holds. If u ∈ C t0 11 then u ∈ C t1 00 , because u does not execute Line 18 in round t 0 + 2 as c u,t0+1

10 then u ∈ C t1 11 , and also u ∈ C t2 00 ; thus c u,t2 1 = 0. This completes the proof of the claim that c u,t 1 = 0, for some t ∈ {t 0 , t 1 , t 2 }, and the proof of (b).

Proof.

then v does not execute Line 6 in any of the rounds t+1 up to t+r, thus v' clock b 1 b 0 is incremented by exactly one in each of those rounds. Note also that if A r ⊆ B t+r 0 , i.e., b 1 = 0 for the agents in A r after round t + r, then A r+1 = A r ; while if A r ⊆ B t+r 1 , then Lemma 8.2 implies that for any 0 < δ < 1,

By applying this iteratively, and using a union bound, we obtain

We use Lemma 8.4 to prove Lemmas 8.5 and 8.6 below. Roughly speaking, the two lemmas say that, w.h.p., all agents that do not reach level 0 during an interval of Θ(log n) rounds have synchronized b 1 b 0 clocks with each other, and also with a (1 -)-fraction of all agents. Recall that Z t1,t2 = t1≤t≤t2 L t 0 .

Lemma 8.5. There are constants α, λ > 0 such that if

Proof. Let u 1 , u 2 be any pair of agents such that (b u1,t ). We partition all rounds t > t into intervals of length 13, and for each interval define a 0-1 random variable X k as follows. For every k ≥ 0, X k is the indicator random variable of the event

where 2 is the constant provided from Lemma 8.4 for 1 = 1/2, and C t is the configuration after round t .

It follows Pr

By applying a standard Chernoff bound to X = 0≤k<κ X k , where κ = 12 -1 2 ln n , we obtain

for all 0 ≤ k < κ, because the inequality holds for k = 0, and the b 1 b 0 clock of each u 1 , u 2 is incremented by exactly one in each round t ∈ {t + 1, . . . , t * }, by the assumption that u 1 , u 2 / ∈ Z t,t * which implies the agents do not execute Line 7 and thus neither Line 6. Then, from X ≥ 3, it follows that some u ∈ {u 1 , u 2 } belongs to two sets U t1 and U t2 , where t < t 1 < t 2 ≤ t * . This means that in round t 1 , u executes either Lines 5 to 7, or Line 14. Since u does not execute Line 7 (otherwise u ∈ L t1 0 ), it must execute Line 14, thus u's phase is 0 and its level is * /2 after round t 1 . Then, since t 2 -t 1 < t * -t ≤ * /2, it follows that in round t 2 the level of u is less than * , thus u executes Lines 5 to 7, and in particular, Line 7, which is a contradiction.

Combining the above result with (8.8), we obtain that for any pair u 1 , u 2 of agents for which

. By a union bound, the statement is true for all pairs u 1 , u 2 simultaneously with probability at least 1 -n -1 . By contrapositive, with probability at least 1 -n -1 , for every pair

), and thus (b

, which proves the first part of the lemma.

For the second part, suppose

, u does not execute Line 7 in round t + 1, thus neither Line 6. From that and u ∈ B t ij , it follows u ∈ B t +1 incr(ij) .

Lemma 8.6. For any constant 0 < < 1, there are constants α, λ > 0 such that for any i, j ∈ {0, 1} and

Proof. The proof is similar to that of Lemma 8.5. Let u ∈ B t ij . We partition all rounds t > t into intervals of length 16, and for each interval define a 0-1 random variable Y k as follows. For every k ≥ 0, Y k is the indicator random variable of the event

where 2 is the constant provided from Lemma 8.4 for

, and u's b 1 b 0 clock is incremented by exactly one in each round t ∈ {t + 1, . . . , t * }, since the assumption that (i) does not hold implies u does not execute Line 7 and thus neither Line 6. Combing that with the assumption that (ii) does not hold, we obtain that Y ≥ 2 implies that u belongs to two sets U t1 and U t2 , where t < t 1 < t 2 ≤ t * . Then by the same argument as that used in the proof of Lemma 8.5, we conclude that u executes Line 7 in step t 1 or step t 2 , contradicting (i).

From the above result and (8.9), we obtain that for any u ∈ B t ij , at least one of (i) and (ii) holds, with probability at least 1 -n -2 . By a union bound, the statement is true for all u ∈ B t ij simultaneously, with probability at least 1 -n -1 . It follows that, with probability at least 1 -n -1 , either (i) holds for all u ∈ B t ij , or (ii) holds for at least one u. In the case where (i) holds for all u ∈ B t ij , we have R t ≤ t * as B t ij ⊆ Z t,t * . In the case where (ii) holds for some u, we have The next two results, Lemma 8.8 and Lemma 8.9, are used to prove Lemma 8.10. Roughly speaking, Lemma 8.10 shows that, when case (II) above applies, after a constant number of rounds (multiple of 4), |B t 1 | decreases by at least a constant factor in expectation, while at the same time it remains small w.h.p. Lemma 8.8. For any 0 < 1 < 1 and 0

, and

Proof. Similarly to the analysis of Algorithm 2 in the proof of Theorem 5.1, we can argue that for any r ≥ 0, 7 (8.10)

where U r+1 ∩ L r * /2-1 is the set of agents that modify their clock b 1 b 0 in round r + 1 (by executing Line 6). It follows

.12) 7 Recall that Br 0 = B r 01 ∪ B r 10 and Br

We use these formulas to upper bound first |B t+2 0 |, and then

From (8.11), B t+2 0 = B t 1 \ U t+1 , and thus

From (8.12), we have B t+4

The unconditional expectation of |B t+4 1 | is then

where in the second inequality we used

This completes the proof of (a).

Next we show (b). Since |U t+1 | is a sum of independent 0-1 random variables, a Chernoff bound gives Pr n) , and by (8.15),

0 | + |Z|, and using also the bounds on |U t+1 |, |Z| we fixed above, we obtain

The right side is maximized by using the lower bound of |U t+1 |. That, and some calculations give

Part (b) then follows, as the bounds we used for |U t+1 |, |Z| hold with probability 1 -e -Ω(n) .

Lemma 8.9. For any round t, there is a round ρ = t+4k, where k ∈ {0, . . . , 3}, such that

Proof. For any k ≥ 0, let t k = t + 4k. To prove the lemma, it suffices to show that for any u ∈ B t 0 , there is a round (8.16) holds trivially, for t u = t 0 = t. The remaining case is when

In this case, from Lemma 8.3(b), there is some

Proof. If B t 1 = ∅ then ρ = 0 and B t+4 1 = ∅, by (8.10), thus the lemma holds. Next we assume B t 1 = ∅. For any k ≥ 0, let t k = t + 4k. Then, ρ is a random variable that takes values in {t 0 , t 1 , t 2 , t 3 }. We use the following trick which allows us to argue about the fixed round t 3 instead of round ρ. If ρ = t k = t 3 , then we replace rounds t k + 1 up to t 3 by "dummy" rounds in which agents do nothing (in particular, they do not change their state). Assuming this modification, it suffices to show (a) and (b) using t 3 in place of ρ, which is what we do in the rest of the proof.

For any k ≥ 0, given configuration

, then Lemma 8.8 applied for any 2 and any constant 3 > 0 yields (8.17)

, for any 2 ≥ 0. Equations (8.17) are also trivially true if rounds t k + 1 up to t k+1 are dummy rounds.

We fix ε 1 = 0.1. We also define shorthand notation

. By applying (8.17) for all k ∈ {0, 1, 2, 3}, using a small enough constant 3 > 0, we obtain

By the union bound,

Using the above bounds for x 3 , we can bound x 4 by applying Lemma 8.8 once more. Form Lemma 8.9, we have

where the last inequality holds for all large enough n, because the assumption B t 1 = ∅ implies x 0 ≥ 1. This completes the proof of (a). From Lemma 8.8(b),

Since 0.103n • 0.973 < 0.1n = ε 1 n, combining the above inequality and Pr [x 3 > 0.1025n] ≤ 3 • e -Ω(n) , we obtain Pr [x 4 > ε 1 n] ≤ 4 • e -Ω(n) , which implies (b).

We use Lemma 8.10 to show the following counterpart of Lemma 8.7.

Lemma 8.11. There are constants ε, λ > 0 such that if * ≥ λ ln n, N \L t * /4 ⊆ B t 00 , and

Using that, we can argue similarly to the analysis of Algorithm 2 that Pr[T > t

From (8.10), it follows that for all t ≥ T d with t ≡ T d (mod 4),

From that, and fact T 1 ≡ T 0 + 1 (mod 4), we obtain that if

0 , which implies B T0 00 = N . Hence, in both cases T ≤ max{T 0 , T 1 }. The claim then follows from (8.18), using a union bound.

It remains to prove (8.18). We consider T 0 first. We partition all rounds t > t into intervals of variable lengths, with the set of possible lengths being {4, 8, 12, 16}. The kth such interval is the set of rounds {s k-1 + 1, . . . , s k }, where s 0 = t, s k = ρ s k-1 + 4 for k ≥ 1, and ρ t denotes the smallest round ρ predicted by Lemma 8.9 for a given round t , i.e., t ≤ ρ t ≡ t (mod 4), and |B

, where ε 1 , ε 2 are the constants of Lemma 8.10.

For any k ≥ 1, let X k be a non-negative integer random variable, where

Then, for any k in the above range, Lemma 8.10(a) implies

For κ = ε -1 2 ln(ε 1 n 2 ) ≤ * /(4 • 16), the above gives E[X κ ] ≤ 1/n, and by Markov's inequality

Moreover, from Lemma 8.10(b), it follows

Combining the last two results above, yields Pr[|B sκ 1 | = 0] = O(1/n). Since s κ ≤ t + * /4, this implies (8.18) for d = 0.

The proof of (8.18) for d = 1 is the same except that we replace t by t+1, and observe that, from the lemma's assumptions

* /4+1 . The last two inequalities allow us to apply Lemma 8.10 in the same way we did for the case of d = 0 above.

Proof of Theorem 8.1. First we upper bound T = min{t : B t ij = N, for some i, j}, i.e., the first round when all clocks b 1 b 0 are synchronized.

From Lemma 8.5, there exists some constant λ 1 such that if * ≥ λ 1 ln n, then the round

We can amplify the above probability

APPENDIX A Formal Definition of Simulations

An execution E A of some protocol A is a sequence C 0 , I 1 , C 1 , I 2 , C 2 . . . , where C t , for t ≥ 0, is the configuration (i.e., the vector of states of all agents) after the first t rounds, and I t , for t ≥ 1, is the communication pattern in round t, describing which agent v is sampled by each u.

For any integers k ≥ 0 and ≥ 1, and any set S ⊆ {0, 1, . . . , -1}, we denote by J(k, , S) an infinite subsequence of (k, k + 1, k + 2, . . .), where i ∈ J(k, , S) if and only if i = k, or i > k and (i -k) mod ∈ S.

A protocol B simulates protocol A if there is an integer ≥ 1, a set S ⊆ {0, 1, . . . , -1}, and a function F from the state space of an agent in B to the state space of an agent in A, 9 such that the following is true: For a random execution C 0 , I 1 , C 1 , I 2 , C 2 . . . of B with an arbitrary initial configuration C 0 , there is some d (which is a random variable that depends on C 0 and the communication patterns up to d), such that F (C j0 ), I j1 , F (C j1 ), I j2 , F (C j2 ), . . . is an execution of A, where (j 0 , j 1 , . . .) = J(d, , S). We call B a simulator of A, and refer to d and the ratio |S| : as the delay and slowdown of the simulation, respectively.

B Analysis of Binary Clock

We prove the following statement. Proof. The state transitions in round t+1 are as follows:

(1) if u ∈ N \ X t then u ∈ X t+1 ; and (2) if u ∈ X t then u ∈ X t+1 if u samples an agents from N \ X t in round t + 1, and u ∈ N \ X t+1 otherwise. It follows that X t+1 = (N \X t )∪Z, where Z is the set of agents u ∈ X t that sample some agent from N \ X t in round t where in the last line we applied a standard Chernoff upper bound. The proof of (B.4) is similar, and uses the Chernoff lower bound Pr[B(nx, 1-x) < (1-δ)nx(1-x)] < e -δ 2 nx(1-x)/2 .

The next simple bound is useful when x t is small.

Proof. In order to have x t+1 = 1, every agent u ∈ X t must sample an agent from set N \ X t in round t + 1. When x t = x, the probability that a given u ∈ X t samples some agent from N \ X t is 1 -x, thus a union bound over all the |X t | = nx agents u ∈ X t proves the claim.

The following bound on the binomial distribution is obtained using Stirling's approximation. Proof. We use Stirling's approximation formula, √ 2πn(n/e) n < n! < e √ n(n/e) n .