Self-stabilising approximate clock synchronisation needs linear time

Self-stabilising approximate clock synchronisation requires linear time

Distributed, Parallel, and Cluster Computing

Summary

Synchronising clocks in distributed computer systems is challenging, especially when processes can start in any state and some may be faulty. The authors show that even to synchronise clocks approximately, it takes time proportional to the number of faulty processes when ensuring the system self-recovers from any initial errors. This means that making clock synchronisation tolerant of both transient and persistent faults is fundamentally slow. Their proof relies on a new method using topological arguments in the self-stabilising setting.

What this means in practice

  • For distributed system architects: Design distributed protocols with awareness that fast self-recovery and approximate clock synchronisation together require time linear in faults.
  • For network protocol engineers: Account for inherent delay proportional to faulty nodes when implementing self-stabilising clock synchronisation in message-passing networks.

A theory result. No direct application yet.

Authors

Joel Rybicki

Abstract

Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $Θ(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $Ω(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.