CS Paper Radar

Self-stabilising approximate clock synchronisation requires linear time

Joel Rybicki

cs.DC ·submitted 2026-11-03 11:44 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On Latency-Optimal Implementations of the Timestamp Object

cs.DC ·2026-10-23 ·Aurojit Panda, Scott Shenker, Sam Toueg, Wen Zhang
similarity 0.69
Abstract

Timestamps are widely used in distributed algorithms to order operations. In this paper, we study the timestamp object (TS), which provides a single operation that returns strictly increasing integers. We ask two questions: What is the maximum resilience and the minimum latency of TS implementations in asynchronous message-passing systems, where latency is measured by worst-case message delay? We answer these questions under various types of failure: crash failures, and Byzantine failures with and without digital signatures. To do so, we give lower bounds and algorithms that determine (1) the optimal resilience of TS implementations under each type of failure, and (2) the optimal latency in all cases but one. Along the way, we introduce a new lower-bound proof technique called a cyclic chain argument, which constructs a cycle of indistinguishable schedules along which the returned timestamps must strictly increase, yielding a contradiction.

0.19

Efficient Heuristics and Machine Learning Approach for Fault Characterization in Distributed Self-Stabilizing Programs

cs.DC ·2026-10-07 ·Amit Garu, Duong Nguyen
similarity 0.62
Abstract · 11 pages, 9 figures

Modern large-scale systems rely on distributed protocols to maximize efficiency while preserving the correctness guarantees of single-process execution. However, designing such protocols is non-trivial: adding resources to a system inherently increases its complexity, which in turn introduces faults that must be addressed during design. One such fault class, arising in systems that use distributed shared memory (e.g., replicated databases), is consistency violating fault (cvf), a fault in which a process accessing shared memory reads stale data previously written by another process. Cvfs are inherent to systems that prioritize availability over strict consistency. Prior work has shown that self-stabilizing programs remain correct under high availability, provided such faults stay within a tolerable bound. Characterizing the behavior of self-stabilizing programs in the presence of cvfs can therefore help system designers build systems that are both correct and efficient. In this paper, we study self-stabilizing programs under cvfs to understand when and where such faults occur, enabling runtime measures that improve computational efficiency. Since exhaustive state-space exploration does not scale, it suffers from state-space explosion; our study investigates two complementary approaches: a conflict-based state-space exploration technique for monotonically stabilizing $(Δ + 1)$-Graph Coloring programs, and a machine-learning-based approach for a Maximal Independent Set program. We propose a conflicting-edges-based state-space exploration algorithm alongside a rigorously validated ML model, evaluated on an out-of-distribution dataset through structural consistency checks against known graph invariants.

0.36

Two barriers for minimal time firing squads, with applications to four and five states

cs.FL nlin.CG ·2026-11-08 ·Kia Keng Giam
publishedtheory similarity 0.60
Abstract · 34 pages, 18 figures, accepted (awaiting print) at the Journal of Cellular Automata

A minimal-time solution of the firing squad synchronization problem synchronizes every line of n cells at time 2n minus 2. Six states suffice; whether five do has been open since 1987. Every line agrees with the half line until its right ends echo returns. For minimal time solutions with any number of states, we prove that cells at distance j behind the half lines front become time-periodic only after time (1.5 minus epsilon)j, for every epsilon greater than 0 and infinitely many j, and that the half line is never periodic in time and space on a wedge at its left border, hence not eventually regular in our sense. With certified satisfiability checks, we exclude four states using the lines of lengths 2 to 5 and parts of the next five, and show that every five state minimal time solution uses at least 15 non quiescent neighbourhoods on its half lines first 78 anti-diagonals. We give five state rules synchronizing exactly the lengths 2 to 14.

0.47

Computation with Backward Feedback: Power, Observation, and Cost

cs.CC ·2026-11-12 ·Saman Farhat, Farzad Didehvar
similarity 0.58
Abstract

How much can a computation gain by passing information back to an earlier stage, and how soon can an observer obtain the answer? We study deterministic programs whose runs are accessed at randomly selected stages. A program keeps a register, a finite block of memory. A random clock selects the current stage; each tick takes a random step, with a law fixed independently of input, program and register. When the clock moves backward, the register contents at the stage it leaves start a new run, and the clock continues where it lands. Equilibrium readout requires a distribution of clock position and register that one tick leaves unchanged, and a correct final answer under every such distribution. For bounded steps in both directions with negative average, we obtain an exact classification at each polynomial scale s. If running time and register length are both O(s), feedback gives exactly nondeterministic space O(s); without transmission the class is deterministic time O(s), which is strictly smaller. An observer that starts at stage zero with an all-zero register, reads sequentially and never accepts a nonmember sees, with fewer ticks than any exponential, only languages fixed by a bounded input prefix. Exponentially many ticks reveal every linear-time language. For a clock moving one step up or down, we bound the wait for useful backward moves and the rate of random erasures a stored counter tolerates. The results separate the power of feedback at equilibrium, observation from a fixed start, and the cost of obtaining and keeping information.

0.21

Time-Invariant Control Barrier Functions for Bounded STL Safety

eess.SY ·2026-08-28 ·Avinash Malik
theory similarity 0.58
Abstract · 6 pages, 3 figures

Enforcing finite-time persistence specifications in Signal Temporal Logic typically requires formulating Control Barrier Functions within an extended state-time space. This introduces strict mathematical assumptions on global clock synchronization, rendering multi-agent execution brittle under asynchronous network delays, clock skew, and non-monotonic jitter. In this paper, we prove that for bounded-time safety tasks, explicit time dependency can be mathematically eliminated for general continuous-time nonlinear systems. By leveraging the reciprocal integral of worst-case system dissipation, we systematically compile temporal specifications into static, lower-dimensional spatial invariants. We formally prove that this time-invariant realization is strictly sound, removes the need for heuristic time-varying envelope tuning, and guarantees robust forward invariance even under severe network desynchronization.

0.18

Optimistic Reliable Broadcast in Three Steps

cs.DC ·2026-10-04 ·Nikita Polyanskii
theory similarity 0.58
Abstract

We study the latency tradeoffs of signature-free asynchronous reliable broadcast with optimistic two-step delivery. We consider $n$ parties, of which at most $f$ are Byzantine. An optimistic fault budget $b\le f$ guarantees two-step delivery with an honest broadcaster and at most $b$ faults, while correctness tolerates $f$ faults. We write $(d_o,d_s,d_t)$ for optimistic latency, honest-broadcaster latency with up to $f$ faults, and totality delay-the elapsed time from first to last honest delivery. For $3f+1\le n<4f$, our first construction improves Opt-RBC's $(2,4,4)$ guarantees to $(2,3,4)$, preserving its maximal optimistic budget $b_*=\lfloor n/2\rfloor-f$. Thus maximal optimism is compatible with the optimal three-step good case. We prove a complementary lower bound: for $3f+1\le n<4f$, every deterministic reliable broadcast protocol in our asynchronous model with two-step optimistic budget $b\ge n-3f$ has totality delay at least three, even when the broadcaster is honest. Our second construction achieves $(2,3,3)$, matching this lower bound at maximal optimism when $f\ge2$ and $\lceil(10f-3)/3\rceil\le n<4f$. Both constructions use quadratic messages and tolerate adaptive corruption. In the matching range, maximal optimism therefore costs exactly one totality step relative to Bracha's $(3,3,2)$, without increasing good-case latency.

0.19

Byzantine-Tolerant Causal Unicast with Constant Message Space Overhead

cs.DC cs.DS ·2026-10-05 ·Purv Patel, Ajay D. Kshemkalyani
similarity 0.57
Abstract

Causal message ordering provides essential semantics for distributed applications, yet ensuring it within an asynchronous system subject to Byzantine failures presents fundamental theoretical and practical challenges. Prior research establishes that algorithms cannot guarantee both strong safety and liveness without using cryptography under these conditions. Existing Byzantine-tolerant solutions make synchrony assumptions or suffer from $O(n)$ message space overheads and $O(n^2)$ message complexity, where $n$ is the number of processes in the system, or use cryptography, but may not guarantee strong safety. In this paper, we present a novel Byzantine-tolerant causal ordering algorithm that achieves an optimal $O(1)$ application message space overhead for point-to-point messages. Our approach uses a Sender Permission to Send (SPS) invariant and an \textit{Isolated-Buffer Optimistic Model} for the memory management architecture. To circumvent Byzantine state-pinning and head-of-line blocking attacks, instead of unified causal buffers, we use isolated, per-peer queues equipped with event-driven \textit{Cascading Space Evictions}. We formally prove that our algorithm guarantees system-wide liveness and satisfies a weakened causal safety abstraction called \textit{Congestion-Relaxed Causal Delivery}. Under this model, weak causal safety is strictly preserved for all honest-to-honest communications unless extreme network latency or Byzantine withholding attacks exceed quantifiable local buffer capacities, forcing optimistic queue evictions. This formal guarantee successfully balances causal ordering with high throughput, constant message space overhead, low computational overhead, and strictly bounded local space.

0.03

The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly

cs.CG ·2026-10-12 ·Florent Becker, Phillip Drake, Benjamin Durbin, Nicolas Ollinger, Brent Orlina +1 more
publishedtheoryunusual similarity 0.57
Abstract · 112 pages, 52 figures, Submission to the 2027 ACM-SIAM Symposium on Discrete Algorithms (SODA27)

In this paper, we prove that the synchronicity provided by the syncTAM can be leveraged to perform two additional feats impossible in the asynchronous aTAM. The aTAM has long been known to be equivalent to finite automata in the one-dimensional case. For our first set of results, we prove that this still holds when a finite, fixed amount of space is available in the second dimension. Yet, surprisingly, in the synchronous setting, a small, fixed, width is enough to simulate a Turing Machine. This holds even in the non-cooperative setting. For our second set of main results we prove that there exists a single set of syncTAM tiles that can be used to simulate any syncTAM system simply by using those tiles to create a scaled version of the seed structure of the original system and then letting the tiles from that set self-assemble from the scaled seed structure. While it has been shown (FOCS 2012) that such a tile set also exists in the aTAM for simulating all aTAM systems, that "intrinsically universal" (IU) tile set requires cooperativity (and is impossible without cooperativity as shown in SODA 2014). We prove there exists an IU tile set in the syncTAM that works without cooperativity. Furthermore, there exists a tile set that is IU for the class of directed systems (i.e. systems which each have a single terminal assembly) while remaining directed during simulation. This was shown to be impossible in the aTAM (FOCS 2016).

0.40