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., ℓ = log2(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.

Given any task $Π$, Brandt's speedup theorem (PODC 2019) provides a mechanical way to design another task~$Π'$ on the same input-set as $Π$ such that, for any $t\geq 1$, $Π$ is solvable in $t$ rounds if and only if $Π'$ is solvable in $t-1$ rounds. The theorem applies to the anonymous variant of the LOCAL model, in graphs with sufficiently large girth, and to locally checkable labeling (LCL) tasks. In this paper, using combinatorial topology applied to distributed computing, we dissect the construction in Brandt's speedup theorem for expressing it in the broader framework of round-based models supporting full information protocols, which includes models as different as wait-free shared-memory computing with iterated immediate snapshots, and synchronous failure-free network computing. In particular, we provide general definitions for notions such as local checkability and local independence, in our broader framework. In this way, we are able to identify the hypotheses on the computing model, and on the tasks, that are sufficient for Brandt's speedup theorem to apply. More precisely, we identify which hypotheses are sufficient for the each direction of the if-and-only-if condition. Interestingly, these hypotheses are of different natures. Our general approach enables to extend Brandt's speedup theorem from LOCAL to directed networks, to hypergraphs, to dynamic networks, and even to graphs including short cyclic dependencies between processes (i.e., the large girth condition is, to some extend, not necessary). The theorem can even be extended to shared-memory wait-free computing. In particular, we provide new impossibility proofs for consensus and perfect renaming in 2-process systems.