Self-stabilising approximate clock synchronisation requires linear time

Self-stabilising approximate clock synchronisation requires linear time

arXiv:2611.04725v1 [cs.DC] 3 Nov 2026

Joel Rybicki · joel.rybicki@hu-berlin.de · Humboldt-Universität zu Berlin, Germany

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 (selfstabilisation) and up to f processes may be non-transiently faulty. It is well known that synchronising clocks exactly is at least as hard as consensus and requires Θ(f ) time. In contrast, without self-stabilisation, clocks can be synchronised 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 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.

Contents 1 Introduction 1.1 The setting: clock synchronisation with extreme fault tolerance . . . . . . . . . . . . 1.2 The question: is approximate self-stabilising clock synchronisation hard? . . . . . . .

1 1 2

2 Overview of results 2.1 Lower bound for pulse synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Lower bounds for approximate counting tasks . . . . . . . . . . . . . . . . . . . . . . 2.2.1 The first attempt: Approximate counting . . . . . . . . . . . . . . . . . . . . 2.2.2 The hard problem: Non-trivial counting . . . . . . . . . . . . . . . . . . . . . 2.3 Reductions from non-trivial counting . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Main challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 4 5 6 8

3 The high-level argument and main ideas 3.1 Background: topology of synchronous computing . . . . . . . . . . . . . . . . . . . . 3.2 Warmup: lower bound for exact non-trivial counting . . . . . . . . . . . . . . . . . . 3.3 The lower bound idea for approximate counting . . . . . . . . . . . . . . . . . . . . . 3.4 Tightness of the lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Outline of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 9 10 10 12 13

4 Further related work

13

5 Topological preliminaries 5.1 Abstract simplicial complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Connectivity of abstract simplicial complexes . . . . . . . . . . . . . . . . . . . . . . 5.3 Synchronous protocol complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14 14 14 16

6 Lower bound for non-trivial counting tasks 6.1 Setting up the two synchronous protocol complexes . . . . . . . . . . . . . . . . . . . 6.2 Clock offsets are edge gradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Clock offset consistency across rounds . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 19 21

7 Upper bound for approximate counting 23 7.1 The approximate counting protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 8 Conclusions

26

1

Introduction

Keeping accurate time reliably is a fundamental problem in distributed systems [Lam78]. Many distributed algorithms assume some degree of global synchronisation among processes [Lyn96]. However, establishing and maintaining such synchronisation can in itself be a highly challenging task: it is not feasible to predict all possible failure and attack patterns that may occur. For example, unexpected transient failures can corrupt the state of the system, whereas non-transient failures caused by malfunctioning hardware or compromised software can alter the behaviour of processes. Distributed algorithms that tolerate arbitrary non-transient failures are called Byzantinetolerant [PSL80, LSP82]. Algorithms that recover from arbitrary transient failures are called selfstabilising [Dij74, Dol00]. Clock synchronisation tasks have been widely studied in both Byzantinetolerant [DHS+95, DHS86, LL84, LM85, ST87, WL88, BLR19, LL22] and self-stabilising [GH90, ADG91, CFG92, AKM+07, BKN17, FKS20, BGS21, DNS+21, EK21] settings.

1.1

The setting: clock synchronisation with extreme fault tolerance

Disruptive events often cause both transient and non-transient failures simultaneously, so a truly resilient algorithm has to cope with both. Remarkably, Dolev and Welch [DW04] showed that it is possible to obtain clock synchronisation algorithms that recover from both arbitrary transient faults (self-stabilisation) and tolerate f < n/3 arbitrary non-transient faults in message-passing systems with n processes. While the algorithms of Dolev and Welch used 2O(f ) expected time to stabilise, subsequent work has gradually improved the performance of both randomised and deterministic algorithms for many self-stabilising synchronisation tasks. In this line of research, the focus has been on two main problem variants: synchronous counting (also known as digital clock synchronisation) [DW04, HDD06, BDH08, DHJ+16, LRS17, LR19a, LL26] and pulse synchronisation [DDP03, DDP04, DH07, DFS+14, LR19b, KL19]. The problems are closely related, but typically studied in different timing models. While in this work we consider only crash faults, as we aim to prove a strong lower bound, prior work on these problems has predominantly focused on upper bounds under the Byzantine fault setting. Pulse synchronisation. The pulse synchronisation problem [DDP03, DFS+14] is studied in the bounded-delay model, where the message delivery times and local clock drift of processes are bounded by known constants, but adversarially controlled. The goal is to synchronise the local clocks of processes so that all non-faulty processes produce an infinite sequence of synchronised pulses (i.e., logical clock ticks) such that eventually after a finite stabilisation phase (i) all non-faulty processes generate a pulse at roughly the same time, and (ii) the pulses are generated at a controlled frequency so that they are sufficiently far apart. The idea is that the pulses delimit logical synchronised rounds so that a synchronous system can be simulated. See Figure 1a for an illustration. With self-stabilisation, state-of-the-art deterministic algorithms can stabilise in O(f ) time and randomised algorithms in polylog f time [LR19b]. The challenge in pulse synchronisation comes from the combination of arbitrary initial states and non-transient faults. If self-stabilisation is not required, i.e., the system is always cleanly initialised, then the problem is easy to solve in constant time. Srikanth and Toueg [ST87] gave a simple algorithm with optimal skew and frequency while tolerating the optimal number f < n/3 of arbitrary non-transient faults. If local clocks are initially closely synchronised, Welch and Lynch [WL88] showed that approximate synchronisation can be efficiently maintained by using approximate agreement over reals [DLP+86] to correct local clocks fast. 1

stabilisation

pulsing

stabilisation

counting

1

1

2

0

3

1

0

1

2

3

0

1

2

2

2

1

1

0

0

0

1

2

3

0

1

2

3

3

3

2

2

2

0

1

2

3

0

1

2

4

0

3

0

T (b) exact synchronous counting

4 t

≤σ 0

>σ

t T (a) pulse synchronisation

Figure 1: Two self-stabilising synchronisation tasks under crash faults. The grey regions indicate the stabilisation phase during which outputs may be inconsistent. After this, outputs must satisfy the requirements of the task. In both examples, process 4 crashes during stabilisation. (a) In pulse synchronisation, the non-faulty processes output synchronised pulses in groups, each within a time window of length σ, and consecutive groups are sufficiently far apart. (b) In synchronous counting, processes must agree exactly on labels that are incremented by one modulo q in each round. Synchronous counting. In the exact synchronous counting problem [DW04], the assumption is that globally synchronous logical clock ticks are available (e.g., from an underlying pulse synchronisation algorithm), but these clock ticks need to be labelled in a consistent manner to obtain round numbers. More precisely, for a given integer q ≥ 2, the constraints are that after stabilisation (i) exact agreement: the outputs of any two non-faulty processes are equal in each round, and (ii) progress: non-faulty processes increment their outputs by one modulo q each round. Figure 1b illustrates the problem. Synchronous counting has deterministic time complexity of Θ(f ) rounds [HDD06, DHJ+16], and with randomisation it can be solved in O(1) expected rounds similarly to consensus [BDH08]. Indeed, given that the problem requires exact synchronisation, there exist reductions between consensus and synchronous counting both ways [HDD06, DFL+15, DHJ+16]. Subsequently, several papers have studied communication-efficient reductions to consensus in order to reduce the communication overhead of counting protocols [LRS17, LR19a, LL26].

1.2

The question: is approximate self-stabilising clock synchronisation hard?

Unlike synchronous counting, whose time complexity matches that of consensus [FL82, AT99], no time lower bounds are known for pulse synchronisation. Despite the long line of work improving the upper bounds for pulse synchronisation [DDP03, DW04, DH07, DFS+14, DFL+15, LR19b], the progress has essentially been stuck at a seeming linear-in-f deterministic stabilisation time barrier. The pulse synchronisation problem only asks for approximate agreement on time, whereas synchronous counting requires exact agreement. Given that without self-stabilisation approximate clock synchronisation can be solved much faster [ST87, WL88], this raises the question whether self-stabilising approximate clock synchronisation could be as easy as approximate agreement over reals [DLP+86, Fek90, Coa88, AAD05]. In this work, we finally settle the following question [LR19b]: “Is pulse synchronisation at least as hard as synchronous consensus?” The answer turns out to be somewhat subtle. We show that pulse synchronisation and related approximate self-stabilising synchronisation tasks require Ω(f ) deterministic time to stabilise even in the crash-fault model. However, these self-stabilising tasks are slightly easier than consensus: they 2

have roughly the same time complexity as 2-set agreement and cycle agreement, both of which require ⌊f /2⌋ + O(1) rounds [CHL+00, AER23]. This is less than the f + 1 rounds required for consensus. Since Byzantine faults subsume crash faults, the lower bound for crash faults also applies to the previously studied Byzantine setting. In particular, this establishes the asymptotic time-optimality of existing deterministic Byzantine-tolerant algorithms for pulse synchronisation [DDP03, LR19b].

2

Overview of results

We prove our lower bounds in a strong model of computing. We assume a fully connected and synchronous message-passing system, where processes can only fail by crashing. That is, the local clocks have no clock drift and the message delays are always bounded by a known constant. Each process has a unique identifier and these identifiers cannot be affected by transient faults. All processes start with an arbitrary initial state, taken from a finite set of allowed states defined by the protocol. In every communication round, each process (1) sends its current state to all processes, (2) receives the states from all non-crashed processes, and (3) updates its local state and outputs a value. Processes that crash in a round fail to send their messages to an adversarially chosen subset of processes. In all subsequent rounds, crashed processes never send any messages. A process is non-faulty in an execution if it never crashes in the execution.

2.1

Lower bound for pulse synchronisation

The pulse synchronisation problem has been previously investigated in the bounded-delay model with Byzantine faults [DDP04, DFS+14, LR19b]. As we prove a lower bound, we consider a simpler synchronous variant with crash faults that is at least as easy as the general non-synchronous version. This is because executions in the bounded-delay model can also behave completely synchronously, and Byzantine faults subsume crash faults. The output of a pulse synchronisation protocol is a binary indicator for each round t that denotes for each process whether the process generates a pulse in round t or not. For integers a ≤ b, we write [a, b] = {a, . . . , b} for a closed interval and (a, b) = {a + 1, . . . , b − 1} for an open interval. Definition 1 (Pulse synchronisation). Let σ ≥ 1 and T ∈ N. A protocol is an f -resilient pulse synchronisation protocol with skew σ that stabilises in T rounds if every execution with at most f crashes has an infinite sequence of intervals [a0 , b0 ], [a1 , b1 ], . . . with a0 ≤ T such that for all k ∈ N (P1) bounded skew: bk − ak ≤ σ, and each non-faulty process pulses exactly once in [ak , bk ], and (P2) pulse separation: ak+1 > bk + σ, and no non-faulty process pulses in (bk , ak+1 ). Figure 1a illustrates the problem for σ = 1 in an execution that stabilises in four rounds. The above problem relaxes the standard pulse synchronisation problem, see, e.g., [LR19b]. In our relaxation, the pulse separation condition (P2) only asks for a lower bound on when a new pulse can be generated; we do not require an upper bound for the time to generate a new pulse, apart from the first pulse, which must happen by round T . Our main result is a lower bound of Ω(f ) for the stabilisation time of any pulse synchronisation protocol: Theorem 2. Let σ > 0 and n > f + 2. There is no f -resilient finite-state pulse synchronisation protocol with skew σ that stabilises in ⌊f /2⌋ − 2σ rounds. For σ = 1, the lower bound is tight up to an additive O(1) term in the crash-fault setting, as shown later in Section 7.

3

stabilisation

4

0

3

1 2

lift

1

3

1

0

2

3

4

0

1

2

3

1

2

3

4

5

6

7

8

2

2

4

1

1

2

3

4

0

1

2

2

1

2

3

4

5

6

7

3

0

0

3

3

4

0

1

2

3

4

3

3

4

5

6

7

8

9

4

4

2

t (a) a 2-path

counting

0

4 t T (b) outputs

T (c) a 2-lift

Figure 2: Approximate counting for q = 5 and σ = 2. (a) The cycle Z5 with the 2-path {4, 0, 1}. (b) An execution of a protocol that stabilises in round T = 3. Process 4 crashes during stabilisation. After stabilisation, the outputs lie on a σ-path on Zq . The outputs in the blue column correspond to the σ-path given in the first panel. (c) A 2-lift of the outputs from Z5 to Z.

2.2

Lower bounds for approximate counting tasks

We prove the lower bound for pulse synchronisation by a reduction from a certain approximate relaxation of synchronous counting. As this relaxation is somewhat technical, we build our intuition with perhaps the most obvious relaxation of synchronous counting. While this will not be precisely the problem we use for the reduction, it almost captures everything we need. 2.2.1

The first attempt: Approximate counting

For q ∈ N, we write Zq = {0, 1, . . . , q − 1}. For σ ∈ N, we say that I ⊆ Zq is a σ-path if I = {c + k mod q : 0 ≤ k ≤ σ} for some c ∈ Zq . If we interpret Zq as the q-cycle graph, where there is an edge (u, v) whenever v = u + 1 mod q, then a σ-path is simply a path of length σ on this cycle; see Figure 2a. We define σ-approximate q-counting as follows. Definition 3. Let σ ∈ N and q > max{2σ, 1}. Consider a protocol with outputs ϕ(i, t) ∈ Zq and let Φ(t) be the set of outputs of non-faulty processes in round t. We say that the protocol is an f -resilient σ-approximate q-counting protocol that stabilises in T rounds if every execution with at most f crashes satisfies for all t ≥ T the following properties: (A1) σ-agreement: Φ(t) is contained in some σ-path of Zq , and (A2) progress: ϕ(i, t + 1) = ϕ(i, t) + 1 mod q for every non-faulty process i. Figure 2b illustrates the problem. As in pulse synchronisation, the parameter σ controls the skew of the outputs. For σ = 0 and any q ≥ 2, we get the exact counting problem. For σ ≥ 1 and q > 2σ, the approximate counting problem can be seen as a “self-stabilising” version of the cycle agreement problem, that is, approximate agreement on a cycle graph, which requires ⌊f /2⌋ + 1 rounds [ACF+19, AER23, RV26]. The condition q > 2σ ensures that the shortest path between two outputs at distance at most σ is unique, and we can determine which processes are “ahead” and which are “behind”. Given that synchronous counting lower bounds are obtained by reductions from consensus, one might expect that a similar reduction from cycle agreement to approximate counting would immediately give us a matching time lower bound. Unfortunately, as explained later in Section 2.4, such simple reductions fail due to issues related to self-stabilisation. Another problem is that the separation property (P2) of pulse synchronisation allows the pulse gaps to “vary” by sometimes 4

stabilisation

counting

lift

1

3

1

0

2

3

4

0

1

0

1

2

2

3

1

2

3

4

6

7 12 13 14 14 15

2

2

4

1

3

4

4

0

1

0

2

2

2

3

2

3

4

4

6

7 12 14 14 14 15

3

0

0

3

2

3

0

1

2

0

1

1

2

4

3

2

3

6

7

8 12 13 13 14 16

4

4

2

t

0

4 t T

T (a) outputs in Z6

(b) a 2-lift

Figure 3: Non-trivial counting with q = 6 and σ = 2. (a) An execution that stabilises in round T = 3. Process 4 is faulty. In the orange rounds, the outputs switch to 0. (b) A σ-lift of the outputs from round T onwards. When the outputs reset to 0, the lift jumps to the next multiple of q. being longer and sometimes shorter. Hence, the progress condition of approximate counting is too strict for a naive reduction to work out. We remedy this by considering a further relaxation of the counting problem that still remains hard. 2.2.2

The hard problem: Non-trivial counting

We now introduce a new problem called non-trivial counting. This is a fairly abstract-looking problem, but it captures the hardness of most natural variants of self-stabilising approximate clock synchronisation problems, including σ-approximate counting and pulse synchronisation. We start by defining the notion of a σ-lift that “unwraps” the outputs of non-faulty processes from Zq to Z while preserving in Z the relative distances between the original outputs. Definition 4. Let σ ∈ N and q > max{2σ, 1}. Consider an execution with outputs ϕ(i, t) ∈ Zq and the set P of non-faulty processes. We say that the map ϕ⋆ : P × Z → Z is a σ-lift of the outputs from round T onwards if all rounds t ≥ T and non-faulty processes i and j satisfy (L1) compatibility: ϕ(i, t) = ϕ⋆ (i, t) mod q, (L2) σ-agreement: |ϕ⋆ (i, t) − ϕ⋆ (j, t)| ≤ σ, and (L3) bounded increments: 0 ≤ ϕ⋆ (i, t + 1) − ϕ⋆ (i, t) < q. That is, the lifted outputs agree with the original outputs modulo q, stay within distance σ of each other, and never decrease, increasing by less than q per round. Figure 2c illustrates a σ-lift for the approximate counting example. Compared to approximate counting, non-trivial counting is a much more relaxed problem: after stabilisation, the outputs of non-faulty processes are allowed to, e.g., reset to 0, jump ahead by more than one, or stall arbitrarily long, as long as they have a σ-lift. Formally, the problem is defined as follows. Definition 5. Let σ ∈ N and q > max{2σ, 1}. We say that a protocol with outputs ϕ(·) ∈ Zq is an f -resilient non-trivial σ-approximate q-counting protocol that stabilises in T rounds if (N1) every execution with at most f crashes has a σ-lift of the outputs from round T , and (N2) in some crash-free execution, the output of some process changes infinitely often. Figure 3a illustrates outputs allowed by non-trivial counting and Figure 3b gives a corresponding σ-lift. We will again call σ the skew of the protocol. Observe that the above problem requires 5

only very weak guarantees for the outputs. Condition (N1) asks that the (lifted) outputs remain at distance at most σ and the outputs can increment each round by at most q − 1 in executions with at most f crashes. In particular, protocols can have outputs that in some rounds stall for arbitrarily long or “jump” by incrementing their outputs by more than one. To ensure that such protocols have non-trivial outputs, Condition (N2) only asks that in some crash-free execution we can find a process that keeps making progress by changing its output. We show the following result. Theorem 6. Let σ ∈ N, q > max{2σ, 1}, n > f + 2 and f > 0. There is no f -resilient finite-state protocol for non-trivial σ-approximate q-counting that stabilises in ⌊f /2⌋ rounds. As non-trivial counting reduces to both pulse synchronisation and approximate counting, we obtain an Ω(f ) time lower bound for these (and other) tasks.

2.3

Reductions from non-trivial counting

We now show the reductions for both approximate counting and pulse synchronisation. We start with approximate counting, where the reduction is almost immediate. Non-trivial counting reduces to approximate counting. Suppose we have an approximate counting protocol that stabilises in T rounds. By the σ-agreement property (A1), we have that the outputs of non-faulty processes lie on some σ-path I = {c + k mod q : 0 ≤ k ≤ σ} of Zq . For each non-faulty process i with output ϕ(i, T ) = c + ki mod q, where ki ∈ {0, . . . , σ}, we define the lift as ( c + ki if t + 1 ≤ T
ϕ⋆ (i, t + 1) := (1) ⋆ ϕ (i, t) + ϕ(i, t + 1) − ϕ(i, t) mod q otherwise. The lift satisfies (L1) and (L3) by construction. To verify that ϕ⋆ gives a σ-lift of the outputs starting from round T on, it only remains to check that (L2) is satisfied. By the σ-agreement property (A1), the outputs of any two non-faulty processes i and j, and hence also the lifts, start at most distance σ apart in round T . By the progress property (A2) of approximate counting, we get that ϕ(i, t + 1) − ϕ(i, t) mod q = 1, and both processes increment their outputs by one each round and the respective lifts keep their difference. Thus, (N1) of non-trivial counting is satisfied. Moreover, by the progress property (A2) of approximate counting, it follows that in any crashfree execution the outputs increment by one each round; hence, property (N2) is satisfied. As the approximate counting protocol solves non-trivial counting, Theorem 6 implies the following. Corollary 7. Let σ ∈ N, q > max{2σ, 1}, n > f + 2 and f > 0. Then there is no f -resilient finite-state σ-approximate q-counting protocol that stabilises in ⌊f /2⌋ rounds. Non-trivial counting reduces to pulse synchronisation. Suppose we have a pulse synchronisation protocol with skew σ that stabilises in T rounds. Recall that the output of a pulse synchronisation protocol indicates whether a pulse was generated in the given round or not. We construct a non-trivial counting protocol with q = 2σ + 1. The output ϕ(i, 0) in the initial configuration is 0 if the pulse synchronisation protocol starts in a state where process i generates a pulse. Otherwise, ϕ(i, 0) is arbitrary. In each round t + 1 > 0, every process i performs the following: – If process i generates a pulse in round t + 1, then set ϕ(i, t + 1) := 0. – Otherwise, set ϕ(i, t + 1) := min{2σ, ϕ(i, t) + 1}. 6

The above protocol solves a variant of approximate counting, where the non-faulty processes may in each round (a) increment their outputs by exactly one modulo q, (b) stall at the output q − 1 = 2σ for an arbitrarily long time (waiting for the next pulse) or (c) reset their outputs to 0. It is easy to verify that because non-faulty processes generate a pulse infinitely often, the counting protocol satisfies condition (N2): if a pulse is generated, the counter is reset to 0, and by (P2), it is 1 in the next round. It remains to show the property (N1). This step is a slightly tedious case analysis. Lemma 8. Any execution of the counting protocol with at most f crashes has a σ-lift from round T + 2σ onwards. Proof. For a non-faulty process i, let τi (k) ∈ [ak , bk ] be the round when i generates a pulse in the interval [ak , bk ], and define τi (−1) := T . The properties (P1) and (P2) of pulse synchronisation give (i) |τi (k) − τj (k)| ≤ bk − ak ≤ σ, and (ii) τi (k + 1) − τj (k) ≥ ak+1 − bk > σ for all k ≥ 0 and non-faulty processes i and j. By (P1) and (P2), the rounds τi (0) < τi (1) < · · · are exactly the rounds t ≥ a0 in which process i generates a pulse. For t ≥ a0 , let Ni (t) be the number of pulses generated by a non-faulty process i in the interval [a0 , t]. Since the counters are reset when a pulse is generated, and the counters increment only up to 2σ, we have for all t ≥ T + 2σ that ϕ(i, t) = min{t − τi (Ni (t) − 1), 2σ}.

(2)

The above is 2σ whenever Ni (t) = 0: in this case, process i does not generate a pulse in the interval [a0 , t], and t − a0 ≥ t − T ≥ 2σ. Hence, the counter of i is not reset for at least 2σ rounds, and the right-hand side of Eq. (2) is min{t − T, 2σ} = 2σ. For all t ≥ T + 2σ, define the lift as ϕ⋆ (i, t) := qNi (t) + ϕ(i, t). Since ϕ⋆ (i, t) mod q = ϕ(i, t), (L1) is satisfied. If there is a pulse in round t + 1, the lift ϕ⋆ (i, ·) increases by q − ϕ(i, t) < q, as non-faulty i cannot pulse in two consecutive rounds by (ii). Otherwise, it increases by at most one. Thus, (L3) holds. To check (L2), consider two non-faulty processes i and j in round t ≥ T + 2σ. There are three cases to consider: (1) Suppose Ni (t) = Nj (t) = k. Note that | min{a, c} − min{b, c}| ≤ |a − b| for any a, b, c ∈ Z. Using this and the definition of ϕ⋆ yields |ϕ⋆ (i, t) − ϕ⋆ (j, t)| = |ϕ(i, t) − ϕ(j, t)| = | min{t − τi (k − 1), 2σ} − min{t − τj (k − 1), 2σ}| ≤ |t − τi (k − 1) − t + τj (k − 1)| ≤ σ, where the last inequality is trivial for k = 0 and otherwise follows from (i). Thus, (L2) holds. (2) Suppose Ni (t) = Nj (t) + 1 and let k = Nj (t). Note that t < τj (k), so by (i) m := t − τi (k) < τj (k) − τi (k) ≤ σ. Hence ϕ(i, t) = m by Eq. (2). If k > 0, then (ii) gives t − τj (k − 1) = m − τj (k − 1) + τi (k) > m + σ. Otherwise, if k = 0, then t − τj (−1) = t − T ≥ 2σ > m + σ. Since m + σ + 1 ≤ 2σ, we get ϕ(j, t) > m + σ by Eq. (2). Using the definition of ϕ⋆ yields ϕ⋆ (i, t) − ϕ⋆ (j, t) = q + ϕ(i, t) − ϕ(j, t) < q + m − (m + σ) = q − σ = σ + 1. Since ϕ(i, t) ≥ 0 and ϕ(j, t) ≤ 2σ < q, we also have ϕ⋆ (i, t) > ϕ⋆ (j, t), so (L2) follows. 7

(3) Suppose Ni (t) − Nj (t) ≥ 2 and let k := Nj (t). Then τi (k + 1) ≤ t. By (ii), we have τj (k) < τi (k + 1). Thus, Nj (t) ≥ k + 1, a contradiction, so this case cannot happen. The other cases with roles of i and j swapped are symmetric. With the above technical lemma, we are ready to show the pulse synchronisation lower bound. Theorem 2. Let σ > 0 and n > f + 2. There is no f -resilient finite-state pulse synchronisation protocol with skew σ that stabilises in ⌊f /2⌋ − 2σ rounds. Proof. By assumption, the pulse synchronisation protocol stabilises in T rounds. Lemma 8 implies that there is a σ-lift from round T + 2σ onwards, so (N1) of non-trivial counting is satisfied. By Theorem 6, we get that T + 2σ > ⌊f /2⌋, which gives the claimed lower bound.

2.4

Main challenges

As we have seen above, natural approximate synchronisation tasks have reductions from non-trivial counting. Before we proceed to the proof outline of Theorem 6, we discuss why the lower bounds for pulse synchronisation and non-trivial counting do not easily follow from existing standard arguments used for self-stabilising synchronous counting and for terminating approximate agreement tasks. Challenge 1: Simple reductions fail. A promising strategy is to (1) reduce the approximate counting problem to pulse synchronisation, and then, (2) reduce cycle agreement to approximate counting in order to get the desired lower bound. This was essentially one motivation for studying round complexity lower bounds for cycle agreement [NR19, AER23]. As we saw, the first step works out by choosing an appropriate relaxation of approximate counting, but the second provides a more serious obstacle. To see why, recall the standard reduction of consensus to exact counting [DHJ+16]: (1) Assume A is an exact q-counting protocol that stabilises in T rounds. (b)

(b)

(b)

(2) Take stabilised configurations C (b) = (C1 , . . . , Cn ) for each b ∈ {0, 1}, where Ci state of process i and in the configuration C (b) all processes output b.

is the

(3) To solve binary consensus, each process i with input b ∈ {0, 1} initialises its state in A to be (b) Ci and simulates A for T rounds. If A outputs yi ∈ Zq for process i at the end of round T , then process i sets zi := yi − T mod q and outputs zi mod 2. It is easy to verify that this satisfies agreement and validity of binary consensus, and hence, we get that T ≥ f + 1 from standard consensus lower bounds, e.g., [FL82, AT99, CHL+00]. Why does the same approach fail when trying to reduce, e.g., cycle agreement to 1-approximate counting? We could now try to define stabilised configurations C (0) , . . . , C (q−1) , where the outputs agree. Suppose now that the inputs lie on an edge {0, 1}, so that agreement is satisfied (outputs are within distance one on a cycle) and we must maintain validity of cycle agreement (outputs are a subset of the inputs). If we do the same simulation argument, where some processes initialise their state by taking values from C (0) and others by taking their state from C (1) , then this is no longer necessarily a stabilised configuration with outputs {0, 1}. The reason is that arbitrarily “gluing” states from different stabilised configurations is not guaranteed to yield a stabilised configuration. Hence, when started on an initial configuration constructed this way, the approximate counting protocol may stabilise in T rounds onto any possible edge, and we cannot map it back to the input edge. This violates validity of cycle agreement. One can try to wiggle out of this issue by choosing a larger set of stabilised configurations, such as those with outputs in {0, 1}, {1, 2}, . . . from which to 8

choose the inputs, but then it is unclear which configurations to use when initialising the simulation. Thus, the reduction is faced with essentially needing to solve 2-set agreement before the simulation. Challenge 2: Lack of topological tools for self-stabilisation. If one conjectures that approximate counting or pulse synchronisation behave similarly to 2-set agreement or cycle agreement, then one might be persuaded to learn and extend the tools used to prove lower bounds for these tasks. As it turns out, essentially all such techniques boil down to using arguments from combinatorial topology one way or another [CHL+00, HS99, SZ00, HKR14, ACF+19, AER23, HRT09, AAE+23]. Unfortunately, unlike for classic terminating agreement problems, such as consensus, set agreement and cycle agreement, there are no readily available tools for characterising solvability or complexity of self-stabilising tasks for which protocols can never terminate. For terminating tasks, one can always obtain the protocol complex describing the entire execution after applying finitely many topological operations (e.g., barycentric or chromatic subdivisions) to the input complex. But what is even the right topological object to look at for self-stabilising tasks where the protocols have infinite executions? The most relevant recent work uses techniques based on point-set topology to characterise solvability of stabilising consensus tasks in infinite executions [SFR26]. However, these do not seem to easily extend to the self-stabilising setting, where the initial states can be arbitrary. Furthermore, unlike for stabilising consensus, where the outputs have to eventually agree on a single common value, in clock synchronisation the outputs have to change over time to guarantee progress.

3

The high-level argument and main ideas

Our general approach is to use the combinatorial topology framework of distributed computing [HKR14]. We now explain the main ingredients of the lower bound proof that allow us to extend topological arguments to the self-stabilising setting with crash faults. We assume finite-state protocols, and without loss of generality, assume that the state encodes the identity of the process. To keep things simple, we now outline the argument in the special case of approximate counting. The general lower bound for non-trivial counting follows essentially the same approach; the generalisation mostly involves more careful bookkeeping and some additional technical details that need to be handled when the clocks may stall or jump ahead rather than incrementing by one in each round.

3.1

Background: topology of synchronous computing

A reader who is not familiar with the language of combinatorial topology may find it useful to skip ahead and read the topological preliminaries given in Section 5 before reading the outline. An abstract simplicial complex X is a collection of finite subsets of a set V (X) with the property that if A ∈ X, then B ∈ X for all ∅ = ̸ B ⊆ A. The elements of V (X) are called the vertices of X and the elements of X the simplices of X. Herlihy, Rajsbaum and Tuttle [HRT09] defined the synchronous full-information protocol complex R(r, k) for r-round executions with at most k crashes per round. Each vertex of this complex is an r-round view of the full-information protocol (i.e., the history of the messages received by a process). The simplices of this complex are (sub)configurations that are reachable in some r-round execution. Formally, this complex is a union of combinatorial pseudospheres; see Section 5.3. While Herlihy, Rajsbaum and Tuttle [HRT09] considered terminating protocols, the synchronous full-information protocol complex can be adapted to the self-stabilising setting. The main issue with self-stabilising protocols is that we do not have inputs per se. However, we treat the initial

9

state of the process as its input for the full-information protocol. Hence, the allowed inputs are simply all possible initial configurations. Herlihy, Rajsbaum and Tuttle bounded the homotopical connectivity of the complex R(r, k). The main topological result we need follows from their work. Theorem 9 (Herlihy, Rajsbaum and Tuttle [HRT09]). If n > (r + 1)k, then the synchronous full-information protocol complex R(r, k) is homotopically (k − 1)-connected. We only need the case when the complexes are path connected (0-connected) and simply connected (1-connected). Path connectivity means that the underlying graph (V (X), E(X)) of X given by the edge set E(X) = {e ∈ X : |e| = 2} is connected in the graph-theoretic sense. Simple connectivity means that the complex is path connected and every edge loop (i.e., a closed walk in the underlying graph) can be contracted to a single vertex. The precise definitions appear in Section 5.

3.2

Warmup: lower bound for exact non-trivial counting

As a gentle warmup, let us sketch a time lower bound for exact non-trivial counting, that is, the variant with skew σ = 0. This relaxes synchronous counting by allowing outputs to stall or increment possibly by more than one but less than q steps. However, the outputs must always agree exactly. Theorem 10. Let q ≥ 2, f > 0 and n > f + 1. There is no f -resilient protocol for exact non-trivial counting that stabilises in f rounds. Proof. Suppose there exists a non-trivial counting protocol with skew σ = 0 that stabilises in T := f rounds. Let X := R(T, 1) be the synchronous full-information protocol complex whose vertices consist of T -round views in executions where at most one process crashes per round. By assumption the protocol stabilises in T rounds. Hence, each simplex corresponds to a stabilised (sub)configuration that may occur in an execution of the protocol. We write out(v) ∈ Zq for the output of any process i with view v ∈ V (X). The 0-agreement property (L2) implies that out(u) = out(v)

(3)

for any {u, v} ∈ X. In particular, this holds for any edge {u, v} ∈ E(X). By Theorem 9, the synchronous full-information protocol complex X is path connected, because n > T + 1 = f + 1. Hence, we get that out(·) is constant on V (X), as the outputs agree along any path of X. Consider an infinite crash-free execution (ρt )t≥0 and a process i given by (N2). Let v be the T -round view of process i in the crash-free execution started from ρ0 . By (N2) there exists a round t > T when process i changes its output for the first time after round T . Let v ′ be the T -round view of i in the crash-free execution started from the configuration at time t − T . Since both v and v ′ are T -round views of the process i, they are vertices of X. Now out(v) ̸= out(v ′ ), contradicting that out(·) is constant on V (X).

3.3

The lower bound idea for approximate counting

Let us now consider how the lower bound works for σ-approximate q-counting, a special case of non-trivial counting. me we have an f -resilient protocol for approximate counting that stabilises in T := ⌊f /2⌋ rounds. Let X := R(T, 2) be the synchronous full-information protocol complex. By Theorem 9, the complex X is simply connected, as n > f + 2 ≥ 2(T + 1). The vertices of X consist of all the possible T -round views that can occur in executions with at most two crashes per round. Technically, the vertices of X are not the states in which processes are after T rounds, but the states are a function of these views. Since the state space and T are finite, the complex X is finite. 10

processes

i

j

0

k

2

3

0

1

2

3

0

1

2

3

0

1

1

+1 Pyi

Syi

0

1

3

0

3

2

0 Pyj

1 Syj

3

2

(a)

+1

(b)

(c)

Figure 4: Clock offsets for σ = 1 and q = 4. Vertices are T -round views, coloured by process and labelled by output; filled triangles are configurations. Edges are oriented from u to v if D(u, v) = 1 and unoriented if D(u, v) = 0. (a) A simply connected protocol subcomplex, where the clock offsets give an edge gradient: offsets on any loop, such as the highlighted one, sum to 0. (b) A subcomplex that is not simply connected: the offsets on the highlighted loop sum to 4, so the clock offsets do not give an edge gradient. (c) The outputs of the prefix Pyj and suffix Syj of a (T + 1)-round view yj of process j differ by one (dashed arrows): in approximate counting, both processes advance their outputs by exactly one modulo q. This gives D(Pyi , Pyj ) = D(Syi , Syj ) in the complex X. The simplices of X correspond to (sub)configurations reachable in T -round executions in which at most 2 processes crash per round. Since 2T ≤ f , the protocol stabilises in any such execution. Hence, every simplex represents a stabilised (sub)configuration. Since all configurations are stabilised, the outputs {out(v) : v ∈ ρ} for any simplex ρ ∈ X lie on a σ-path of Zq . In particular, they are at most distance σ apart on the q-cycle Zq by the σ-agreement property (A1) of approximate counting. Step 1: Clock offsets give edge gradients. We define for every {u, v} ∈ X the clock offset D(u, v) as the signed distance from out(u) to out(v) on the q-cycle Zq so that the sign is positive if the shortest path goes clockwise (increasing values), and negative otherwise. Since {u, v} ∈ X is contained in a stabilised configuration, we get that D(u, v) ∈ {−σ, . . . , σ} by the σ-agreement property (A1). This is well-defined: as q > 2σ, the shortest path between outputs is unique. We also show that the map D satisfies a triangle property, i.e., that D(u, v) + D(v, w) = D(u, w) for any {u, v, w} ∈ X. This is because the outputs on any triangle lie on a σ-path, and summing their offsets adds up to 0. Recall that by Theorem 9, the complex X is simply connected. Since the map D satisfies the triangle property, this implies that D is an edge gradient of the complex X (i.e., a simplicial 1-coboundary); see Lemma 11. This simply means that there exists a map ϑ : V (X) → Z such that D(u, v) = ϑ(v) − ϑ(u). Such a map ϑ is commonly called a potential. Figure 4a illustrates an edge gradient and Figure 4b illustrates a complex where clock offsets do not give an edge gradient. Since X is also path connected, we show how to find a nice potential ℓ : V (X) → Z that lifts the outputs from Zq to Z in the sense that the map satisfies D(u, v) = ℓ(v) − ℓ(u)

and

ℓ(v) ≡ out(v)

(mod q)

(4)

for all {u, v} ∈ X. The key step is to constrain how these clock offsets behave using another complex. Step 2: The clock offsets have to be globally consistent. For approximate counting, the progress condition (A2) forces the outputs of the processes to behave predictably: the output in round T + 1 is the output in round T incremented by one modulo q. 11

We now come to one of the key new ideas of the lower bound proof. To get access to the temporal behaviour of the self-stabilising protocol, we construct another complex Y = R(T + 1, 1), whose vertices are (T + 1)-round views of executions in which at most one process crashes per round. Since T + 1 ≤ f , these executions have at most f crashes, so the simplices of Y are also stabilised subconfigurations. We link Y to X as follows. For any vertex y ∈ V (Y ), we define its prefix Py as the T -round view without the (T + 1)th round. Similarly, we define the suffix Sy of y as the T -round view without the first round. The formal definitions are in Section 5. Both the prefix Py and the suffix Sy are T -round views, and hence, vertices of the complex X we constructed above. In fact, the prefix and suffix operations give chromatic simplicial maps from Y to X. This means that for any simplex τ ∈ Y , the sets {Pv : v ∈ τ } and {Sv : v ∈ τ } are simplices of X. The progress condition (A2) of approximate counting ensures that the clock offsets of two processes i and j have to be globally consistent in the sense that D(Pyi , Pyj ) = D(Syi , Syj ) for any {yi , yj } ∈ Y ; see Figure 4c. Writing ϵ(y) := ℓ(Sy) − ℓ(Py) − 1 and using Eq. (4) yields ϵ(yi ) − ϵ(yj ) = D(Pyi , Pyj ) − D(Syi , Syj ) = 0. In particular, ϵ is a constant map on V (Y ), since the complex Y is path connected by Theorem 9. By the second condition of Eq. (4) and the fact that out(Sy) = out(Py) + 1 mod q, we get that ϵ ≡ 0 (mod q). Consequently, there exists some constant c ∈ Z such that the lift ℓ satisfies ℓ(Sy) − ℓ(Py) = 1 + ϵ(y) = 1 + qc.

(5)

Step 3: Global consistency implies an infinite complex. Finally, we look at what a fixed process i does in an infinite crash-free execution. For all t ≥ 0, let xt be the T -round view of process i when starting the execution from the configuration at time t. Since the vertices of the complex X are all possible T -round views of the protocol in executions with at most two crashes per round, which include crash-free executions, we get that each xt ∈ V (X). Now we have an infinite sequence (xt )t≥0 of T -round views. Of course, since X is finite, some vertices are repeated in (xt )t≥0 . Since each xt+1 and xt are the suffix and prefix of some (T + 1)-round view, we get from Eq. (5) and some algebraic manipulation that ℓ(xt ) = ℓ(x0 ) + (1 + qc) t. No matter the value of c ∈ Z, ℓ(xt ) diverges as t → ∞, because q ≥ 2. Thus, the map ℓ : V (X) → Z takes on infinitely many different values, which contradicts the finiteness of the complex X. This is essentially the whole argument for the lower bound construction. Extending this argument to cover non-trivial counting requires mainly a more careful handling of the clock offsets and their increments in the second step. The full details appear in Section 6.

3.4

Tightness of the lower bounds

Existing deterministic Byzantine-tolerant exact synchronous counting protocols solve approximate counting in asymptotically optimal Θ(f ) rounds [HDD06, LR19a]. Moreover, it is not too hard to come up with a protocol that matches Corollary 7 up to an O(log q) additive term, so the lower bound cannot be improved much in our synchronous setting with crash faults. The general idea is as follows. If any round has at most one crash, then the processes receive at most two different sets of messages in that round; by the pigeonhole principle, this happens within the first ⌊f /2⌋ + 1 rounds. Afterwards, there are at most three output values and they lie on a 12

short path of the cycle, and running approximate agreement on a path halves the distance between outputs in every round. The details are in Section 7. This construction shows that with q = 4 and σ = 1, we obtain an approximate counting protocol that exactly matches the lower bound of Corollary 7 for any even f . We can now solve pulse synchronisation by generating a pulse whenever the output is congruent to 0 modulo 4. This matches Theorem 2 up to an additive O(1) term.

3.5

Outline of the paper

The remainder of the paper is organised as follows. Section 4 discusses further related work. Section 5 introduces the topological tools used to prove the lower bound. We favour simple “combinatorial” definitions and elementary arguments, rather than invoking geometric realisations of topological objects or cohomology theory. We hope this makes the proof easy to follow for readers with limited background in algebraic topology. Section 6 gives the general lower bound for non-trivial counting. Section 7 discusses upper bounds. Section 8 concludes the paper.

4

Further related work

Combinatorial and algebraic topology plays a key role in characterising the solvability and complexity of fault-tolerant terminating distributed agreement tasks [HKR14]. Topological arguments are the main tool for tasks where exact agreement is not required, such as set agreement [CHL+00, SZ00, HS99, FNP+25], loop agreement [HR03, LXP09], and approximate agreement on graphs and simplicial complexes [ACF+19, AER23, Liu23, RV26, AR26]. Synchronous topology. Fraigniaud, Nguyen, Paz, Schmid, and Rincon-Galeana [FNP+25] extended the homotopical connectivity-based analysis of synchronous k-set agreement in [HKR14, Chapter 13] to arbitrary communication networks, while correcting a gap in the carrier-map framework. Their techniques may prove useful for extending the clock synchronisation bounds to general communication networks. However, their construction uses executions with exactly k crashes per round, whereas we use the complexes of [HRT09] that permit at most k crashes per round. In our proof, we need to access crash-free executions as well. Schmid, Felber, and Rincon Galeana [SFR26] investigated stabilising consensus using a pointset topology that captures infinite executions under message adversaries. However, in stabilising consensus, the initial states are not arbitrary. Moreover, stabilising consensus requires eventual agreement on a stable common value, whereas our tasks only need approximate agreement but require that the outputs change infinitely often (in some execution). Gradients and cohomological approaches. The general idea of clock offsets being gradients already appears in prior work [BPV08, HTR+23]. For example, Boulinier, Petit, and Villain [BPV08] studied self-stabilising clock synchronisation without non-transient faults. They essentially gave the same local offset identity as we use in building the gradient, and similarly used the sums of gradients across paths. However, they define gradients on the communication network. In our proof, the edge gradient is defined over the protocol complex that captures all executions of the protocol. Only a few explicit cohomological approaches have been proposed for distributed agreement tasks. Recently, Felber, Hummes Flores, and Rincon-Galeana [FHR25] introduced a sheaf-theoretic approach to characterising solvability of terminating tasks. Hylton, Tsuei, Ronnenberg, Hwang, Mallery, Quartin, Levaunt, Quail, and Curry [HTR+23] identified an interesting connection between

13

algebraic topology and clock synchronisation: similarly, they interpret clock offsets using cochains (edge cocycles) and coboundaries (edge gradients). They also discuss a sheaf-theoretic approach to time synchronisation. However, their work does not consider time complexity lower bounds. Moreover, our work only requires the elementary notions of edge cocycles and edge coboundaries. Cai and Ghrist [CG14] and Gravner, Lyu, and Sivakoff [GLS18] studied synchronisation phenomena of generalised cellular automata on arbitrary graphs. Both analyses of the Greenberg–Hastings model used a similar edge gradient and path integration (i.e., summing the gradient over a walk) approach. While our lower bound argument uses a similar idea, it does so in the protocol complex. Moreover, unlike the analyses on networks, we ensure compatibility of clocks over time by using two protocol complexes that are related by chromatic simplicial maps.

5

Topological preliminaries

5.1

Abstract simplicial complexes

Let X be a finite collection of finite sets. We say that X is an abstract simplicial complex if ρ ∈ X =⇒ τ ∈ X for all non-empty τ ⊆ ρ. That is, X is closed under taking non-empty subsets. An element ρ ∈ X is called a simplex of X. The dimension of a simplex ρ ∈ X is |ρ| − 1. Simplices of dimension zero correspond to vertices of X. We write V (X) = {v : {v} ∈ X} for the set of vertices of X. A simplex of dimension one is an edge. We write E(X) for the set of edges of X. A simplex of dimension two is a triangle. The graph (V (X), E(X)) is the underlying graph of X. For a collection of sets Y , we say that {τ : ∅ = ̸ τ ⊆ ρ, ρ ∈ Y } is the simplicial complex generated by Y . For two simplicial complexes X and Y , we say that a map F : V (Y ) → V (X) is simplicial if for any simplex ρ ∈ Y we have F (ρ) ∈ X, where F (ρ) = {F (v) : v ∈ ρ}.

5.2

Connectivity of abstract simplicial complexes

The homotopical connectivity of an abstract simplicial complex X is defined in terms of the homotopy groups of the geometric realisation of X as follows: an abstract simplicial complex X is k-connected if the first k + 1 homotopy groups of the geometric realisation of X are trivial [Arm83, Hat02]. However, for our proof, it suffices to only work with lower orders of connectivity, namely path connectedness (0-connectivity) and simple connectedness (1-connectivity), which can be defined combinatorially without needing to introduce homotopy theory. We opt for this approach. Edge paths and edge loops. Let X be an abstract simplicial complex. An edge path in X is a sequence α = (v0 , . . . , vk ) of (possibly repeated) vertices such that {vi , vi+1 } ∈ X for all 0 ≤ i < k. If v0 = vk , then we say that α is an edge loop. A contraction of the edge path α is an edge path β obtained by removing vertices using the following rules: (R1) If vi = vi+1 , then β = (v0 , . . . , vi , vi+2 , . . . , vk ) is a contraction of α. (R2) If {vi , vi+1 , vi+2 } ∈ X, then β = (v0 , . . . , vi , vi+2 , . . . , vk ) is a contraction of α. Two edge paths α and β are equivalent if we can get from one to the other using a finite sequence of contractions or their inverses. An edge loop starting from v0 is contractible (that is, topologically, null-homotopic) if it is equivalent to the edge path consisting only of the vertex v0 . Connectivity. A complex X is path connected (0-connected) if for any two vertices u, v ∈ V (X) there is an edge path between u and v. That is, the underlying graph of the complex is connected in the graph-theoretic sense. A path connected simplicial complex X is simply connected (1-connected) 14

if every edge loop of X is contractible. This is equivalent to the condition that the geometric realisation of X has a trivial fundamental group [Arm83, Theorem 6.10]. Edge gradients. An edge cocycle of X is a map ω that assigns an integer ω(u, v) to every ordered pair (u, v) of vertices, where {u, v} ∈ X, so that the following triangle property ω(u, v) + ω(v, w) = ω(u, w)

(▲)

is satisfied for all {u, v, w} ∈ X. This implies that ω(u, u) = 0 and that ω is antisymmetric, i.e., ω(u, v) = −ω(v, u). We say that ω is an edge gradient if there exists some ϑ : V (X) → Z such that ω(u, v) = ϑ(v) − ϑ(u) for all {u, v} ∈ X. The map ϑ is called a potential of ω. Those well-versed in the parlance of algebraic topology may see that an edge cocycle is a simplicial 1-cocycle and an edge gradient is a simplicial 1-coboundary [Hat02, Chapter 3]. We only need the following standard fact, which can be proven using a simple argument without the need for any further (cohomological) machinery. Lemma 11. Let X be a simply connected complex. If ω is an edge cocycle of X, then ω is an edge gradient of X. Proof. Consider an edge loop α = (v0 , . . . , vk ). We show that k X

ω(vi−1 , vi ) = 0.

i=1

If α consists of a single vertex, the claim is immediate, since the sum is empty. We next show that neither contractions nor their inverses change the sum. Consider a contraction β of α. If β is obtained by Rule (R1), then deleting the vertex vi+1 does not change the sum as ω(vi , vi+1 ) = 0. If β is obtained using Rule (R2), then some vertex vi+1 is removed from the edge loop. Since ω is a cocycle, it satisfies the triangle property Eq. (▲), and we have ω(vi , vi+2 ) = ω(vi , vi+1 )+ω(vi+1 , vi+2 ), so the sums do not change. Since X is simply connected, the edge loop α can be contracted to a single vertex using contractions and their inverses, and so the sum has to equal zero by induction. Next, we define a potential ϑ for ω, which shows that it is an edge gradient. Fix a base vertex b ∈ V (X). Since X is simply connected, it is also path connected. Hence, for each v ∈ V (X), there exists some edge path γ(v) = (u0 = b, . . . , uk = v) from b to v. Define ϑ(v) :=

k X

ω(ui−1 , ui ).

i=1

Consider any edge {u, v} ∈ X. Let α = (v0 , . . . , vk ) be the edge loop obtained by going along γ(u), going from u to v, and returning along the reversal of γ(v). Since ω is antisymmetric, we get ω(u, v) + ϑ(u) − ϑ(v) =

k X

ω(vi−1 , vi ) = 0.

i=1

This establishes that ϑ is a potential for ω, so ω is an edge gradient as claimed.

15

5.3

Synchronous protocol complexes

We now explain how executions of synchronous message-passing protocols can be modelled using simplicial complexes, following the axiomatisation of Herlihy, Rajsbaum, and Tuttle [HRT09, HRT01]. The general idea is that we will construct a simplicial complex whose vertices correspond to r-round views of some process and simplices correspond to views that can occur in the same configuration after r communication rounds. To define executions of protocols, we will use the notions of pseudospheres, failure operators and round operators. These are simply convenient ways to express how the execution can unfold using the language of combinatorial topology. Configurations and protocols. For each process i, a self-stabilising protocol specifies a finite set Si of states which the process i can take. We assume that S1 , . . . , Sn are pairwise disjoint. This means that the identity of the process is encoded in its state. We write S for the union of S1 , . . . , Sn . Let C be the family of sets that contain at most one element from each Si , that is, C := {ρ ⊆ S : |ρ ∩ Si | ≤ 1 for each process i} . Each ρ ∈ C is a configuration of the system. Any τ ⊆ ρ is a subconfiguration of ρ. The set of initial configurations is S := {ρ ∈ C : |ρ| = n}, that is, all configurations where there are initially no crashed processes. Processes that crash before the start of the protocol can, without loss of generality, be assumed to crash in the first round before sending any messages. The set C also defines all possible sets of messages that can be received by a process during the execution of the protocol, as processes always send their current state in each round. Formally, a protocol defines for each process i a state transition map Γi : C → Si and an output map outi that maps the current state s ∈ Si to an output value outi (s). For counting tasks, we use Zq as the set of outputs. For pulse synchronisation, the set of outputs will be {0, 1} whose values indicate whether a pulse is generated or not. Pseudospheres. Let M be a set of values. A labelling of a simplex ρ with M is a map g : ρ → M . We equivalently treat such a map as the simplex {(x, g(x)) : x ∈ ρ}. For a simplex ρ and a set M of values, the pseudosphere M ρ is the set of all labellings of ρ with M , where each map g ∈ M ρ is interpreted as a simplex. A pseudosphere generates a simplicial complex [HRT09]. The failure and round operators.

For k ∈ N, the k-failure operator is defined as

Fk (ρ) := {τ ⊆ ρ : |ρ \ τ | ≤ k}, that is, the family of the subsets of ρ with at most k vertices removed. The idea is that if ρ consists of the views of non-crashed processes at the start of a round, then Fk (ρ) gives the different sets of views that can influence a process in this round. A simplex ρ is between simplices τ and τ ′ if τ ⊆ ρ ⊆ τ ′ . We write [τ : τ ′ ] for the set of all simplices between τ and τ ′ . The synchronous round operator is a union of pseudospheres given by [ Rk (ρ) := [τ : ρ]τ . τ ∈Fk (ρ)

16

S For a set A of simplices, we write Rk (A) := ρ∈A Rk (ρ), and R0k is the identity map. The iterated (r + 1)-round operator is Rr+1 := Rk ◦ Rrk for all r ≥ 0. The round operator is used to construct k views and configurations that can occur during the execution of a protocol. The set of r-round views in executions with at most k crashes per round is precisely the set of vertices in Rrk (S). Views and executions. A 0-round view of process i is an element of Si , as without communication, the process has only information about its own state. A t-round view is a vertex of a simplex in Rtk (ρ) for some ρ ∈ C and k ≥ 0. Thus, for t ≥ 0, a (t + 1)-round view is a pair (v, M ) of a t-round view v and the set M of t-round views received in round t + 1. A view s ∈ Si belongs to process i, and (v, M ) belongs to the same process as v. The state µ(v) of process i with view v is given recursively by µ(s) := s for s ∈ S and µ((v, M )) := Γi (µ(M )), where µ(M ) := {µ(m) : m ∈ M }. The output of a view v of process i is out(v) := outi (µ(v)). For a view (v, M ), its prefix is P(v, M ) := v, and its suffix is ( µ((v, M )) if v is a 0-round view, S(v, M ) := (S(v), S(M )) otherwise, where S(M ) = {S(w) : w ∈ M }. For brevity, we often drop the parentheses when applying the prefix and suffix operations, that is, we write Pv and Sv. Note that for any (t + 1)-round view v of process i, both its prefix Pv and its suffix Sv are t-round views for the same process. An execution with at most k crashes per round is a (possibly infinite) sequence ρ0 , ρ1 , . . . such that ρ0 ∈ S and ρt+1 ∈ Rk (ρt ). The vertices of ρt are t-round views of the processes that have not crashed by round t. An execution has at most f crashes in total if |ρt | ≥ n − f for all t ≥ 0. Note that a process can crash only once. An execution is crash-free if it has zero crashes in total. With a slight abuse of terminology, we also refer to the collection ρt of views as a configuration, while technically, µ(ρt ) ∈ C is the corresponding configuration of states. Recall that Si is the set of states process i can take. If µ(ρt ) ∩ Si = ∅, then the process i is crashed by round t. We say that a process is non-faulty in an execution if it never crashes. Clearly, any finite execution ρ0 , . . . , ρt can be extended to an infinite execution with no further crashes, in which all processes with views in ρt remain non-faulty. The synchronous protocol complex. The r-round full-information protocol complex R(r, k) with at most k crashes per round is the simplicial complex generated by Rrk (S), that is, the iterated round operator applied to the set of possible initial configurations. The vertices of R(r, k) correspond to r-round views of the processes and simplices to reachable configurations and their subconfigurations in executions with at most k crashes per round. This is the topological object we work with. Herlihy, Rajsbaum and Tuttle [HRT01, HRT09] showed that the round operator preserves high connectivity. The r-round views of self-stabilising protocols correspond to the execution of a non-self-stabilising full-information protocol with input configurations from S. Theorem 9 follows from [HRT09, Theorem 4.10] in the same way as it is applied to the synchronous round operator in the proof of [HRT09, Theorem 5.10]. (Note that [HRT09] consider n + 1 processes, whereas we have n processes.) The main property to verify is that the set S of initial configurations is an absorbing poset in the sense of [HRT09, Definition 3.1]. This follows by ordering S by the lexicographic order ≺ on the vectors (s1 , . . . , sn ) ∈ S1 × · · · × Sn . If ρ = {s1 , . . . , sn } ≺ τ = {s′1 , . . . , s′n } and i is the smallest index with si ̸= s′i , then τρ := (τ \ {s′i }) ∪ {si } satisfies the required conditions.

17

Bounded-delay model. Finally, a subtle technical remark: although the bounded-delay model used for pulse synchronisation protocols in prior work [DW04, DFS+14, LR19b] usually models local clocks as being real-valued, their numerical values are not accessible to the processes. Instead, the local clocks are used to trigger local state transitions. We can restrict attention to admissible synchronous executions in which all state transitions occur at discrete time steps and messages always arrive in unit time. Under this restriction, the new state of a process depends only on its current state and the messages received in the round. Hence, any finite-state protocol in this bounded-delay model gives a finite-state synchronous protocol in our setting.

6

Lower bound for non-trivial counting tasks

We now prove that any non-trivial counting protocol with q > 2σ requires more than ⌊f /2⌋ rounds.

6.1

Setting up the two synchronous protocol complexes

Let σ ≥ 0 and q > max{2σ, 1}. Suppose that we have a finite-state protocol for non-trivial σapproximate q-counting that stabilises in T := ⌊f /2⌋ rounds. The case f = 0 is trivial, so we assume f > 0. We consider the two synchronous protocol complexes X := R(T, 2)

and

Y := R(T + 1, 1).

Since n > f + 2 ≥ 2(T + 1) for X and n > T + 2 for Y , Theorem 9 implies that the complex X is simply connected and the complex Y is path connected. Moreover, since the state space of the protocol is finite, both complexes are finite. This will be important. Every simplex of X or Y is contained in a configuration reached in an execution with at most 2T ≤ f or T + 1 ≤ f crashes, respectively. Since non-trivial counting only constrains processes that never crash, we can always extend such an execution without further crashes; then every process in the configuration is non-faulty, and the property (N1) of non-trivial counting applies to all of them. We say that F : V (Y ) → V (X) is chromatic if for any y ∈ V (Y ) the views y and F (y) belong to the same process. Recall the prefix and suffix maps defined in Section 5.3. We now establish some useful properties of these maps. Lemma 12. The prefix P : V (Y ) → V (X) and suffix S : V (Y ) → V (X) maps satisfy the following: (a) The prefix P and suffix S maps are chromatic simplicial maps from Y to X. (b) For any y ∈ V (Y ), the output of a suffix satisfies out(Sy) = out(y). (c) If ρ0 , . . . , ρT +1 is a crash-free execution, then PρT +1 = ρT , and Sρ1 , . . . , SρT +1 is the crash-free execution starting from the configuration µ(ρ1 ). Proof. Consider a simplex τ ∈ Y . Let ρ0 , . . . , ρT +1 be a (T + 1)-round execution with at most one crash per round such that τ ⊆ ρT +1 . The prefixes Pτ = {Pv : v ∈ τ } are views of the T -round execution ρ0 , . . . , ρT . Hence, these are views of X and Pτ ∈ X. Now consider the suffix operation. If T = 0, then by definition Sv = µ(v) for each 1-round view v ∈ τ . Thus, Sτ ⊆ µ(ρ1 ) is a subconfiguration of some initial configuration, and hence, a simplex of X. Therefore, assume that T ≥ 1. Let Q1 be the set of processes that crash in the first round and Q2 the set of processes that crash in the second round in the execution. Consider the configuration µ(ρ1 ) = {µ(v) : v ∈ ρ1 } consisting of the states of processes that did not crash in the first round. If

18

Q1 is non-empty, it consists of one process i. Choose an arbitrary state si ∈ Si for i ∈ Q1 and let ρ′1 := µ(ρ1 ) ∪ {si : i ∈ Q1 } to get an initial configuration where no process has crashed. Consider a new execution starting from the configuration ρ′1 in which all processes in Q1 crash immediately before sending any messages. The states in µ(ρ1 ) ⊆ ρ′1 are obtained by applying µ to each 1-round view v ∈ ρ1 , as in this case µ simply applies the state transition function to the set of messages received by the process with view v. Hence, letting a process in Q1 crash before sending any messages in the new execution loses no information, as the information received from Q1 is already reflected in the state µ(v). Now repeat everything as in the second round of the original execution, including crashing the processes in Q2 . Finally, simulate the remaining rounds 3, . . . , T + 1 as in the original execution. This gives an execution ρ′1 , . . . , ρ′T +1 in which at most two processes crash in the first round and at most one process crashes in every subsequent round. Thus, ρ′T +1 ∈ X by definition of X. By construction, the suffix of each (T + 1)-round view in ρT +1 is a T -round view in ρ′T +1 . Since X is closed under taking subsets, we have that {Sv : v ∈ τ } ∈ X. Thus, Pτ ∈ X and Sτ ∈ X, so the maps are simplicial. Each view is uniquely associated with exactly one process, as states encode the identities of processes. Therefore, the prefix and suffix maps are chromatic. This gives (a). The claims (b) and (c) follow easily from the definitions. Recall that for a view v ∈ V (X), we write out(v) ∈ Zq for the output of a process with view v. Next we observe a simple fact that says the outputs in any simplex ρ ∈ X lie on a σ-path of Zq . Lemma 13. Let ρ ∈ X. Then the outputs out(ρ) lie on a σ-path of Zq . Proof. A simplex ρ ∈ X is a subconfiguration that can be reached in some T -round execution with at most two crashes per round. In total, there are at most 2T ≤ f crashes. Let ϕ(i, T ) be the output of process i for each process whose view is in ρ. By the property (N1) of the protocol, there exists a σ-lift ϕ⋆ from round T onwards. By (L1), we have ϕ(i, T ) = ϕ⋆ (i, T ) mod q. By (L2), we have that |ϕ⋆ (i, T ) − ϕ⋆ (j, T )| ≤ σ. Since out(v) = ϕ(i, T ) for any process i that has view v ∈ ρ, we get that out(ρ) ⊆ {c mod q, . . . , (c + σ) mod q} for c := mini {ϕ⋆ (i, T )}. Hence, the outputs lie on a σ-path of Zq .

6.2

Clock offsets are edge gradients

Recall that we use the shorthand [a, b] = {a, . . . , b} for integers a ≤ b. Let a, b ∈ Zq lie on a σ-path of Zq . The offset between a and b is the unique integer d(a, b) that satisfies (O1) d(a, b) ∈ [−σ, σ], and (O2) d(a, b) ≡ b − a (mod q). This is the “signed” length of the shortest path from a to b on the q-cycle graph, where going clockwise gives a positive sign and going counter-clockwise a negative sign; see Figure 5 for an illustration. This integer is unique because two integers in [−σ, σ] that are congruent modulo q differ by at most 2σ < q. Put otherwise, on the q-cycle, there is only one shortest path between any two values that are distance at most σ apart. For any {u, v} ∈ X, we define the clock offset of two views u and v as D(u, v) := d(out(u), out(v)), 19

(6)

−2 4

0

4

0

+2 3

1

−2

3

+2

1

2

2

(a) a = 4, b = 1

(b) a = 2, b = 4

Figure 5: Offsets for q = 5 and σ = 2. Moving clockwise gives a positive offset, moving counterclockwise a negative offset. The dashed line marks the wraparound point between q − 1 and 0. (a) The path between a = 4 and b = 1 crosses the wraparound point. Hence, d(a, b) = b − a + q = 2. (b) The path between a = 2 and b = 4 does not cross the wraparound point, so d(a, b) = b − a = 2. that is, the offset between their outputs. This is well-defined by Lemma 13, since the outputs lie on a σ-path. In the following, we show that the map D is an edge gradient of X with values in [−σ, σ]. We start by showing that D is an edge cocycle. Lemma 14. The map D is an edge cocycle of the complex X. Proof. We need to show the triangle property (▲). Let {u, v, w} ∈ X. By Lemma 13, the outputs out(u), out(v), out(w) lie on some σ-path {c mod q, . . . , (c + σ) mod q} of Zq . For each view x ∈ {u, v, w}, choose an integer x⋆ ∈ [c, c + σ] ⊆ Z such that x⋆ ≡ out(x) (mod q). By definition of D(x, y) in Eq. (6), the clock offset D(x, y) is the only integer in [−σ, σ] satisfying D(x, y) ≡ out(y) − out(x) (mod q). Since x⋆ , y ⋆ ∈ [c, c + σ], we have y ⋆ − x⋆ ∈ [−σ, σ], and y ⋆ − x⋆ ≡ out(y) − out(x) (mod q). Therefore, D(x, y) = y ⋆ − x⋆ . This gives the triangle property: D(u, v) + D(v, w) = v ⋆ − u⋆ + w⋆ − v ⋆ = w⋆ − u⋆ = D(u, w). We now use the fact that on a simply connected complex X, an edge cocycle is an edge gradient. This allows us to find a potential ℓ : V (X) → Z that lifts the output values from Zq to Z. Lemma 15. There exists a map ℓ : V (X) → Z such that (a) ℓ(v) − ℓ(u) = D(u, v) for all {u, v} ∈ E(X), (b) out(u) = ℓ(u) mod q for all u ∈ V (X). Proof. By Lemma 14, the map D is an edge cocycle of X. Since X is simply connected, Lemma 11 implies that D is an edge gradient, that is, there exists a map ϑ : V (X) → Z such that D(u, v) = ϑ(v) − ϑ(u). Fix an arbitrary vertex b ∈ V (X). For each u ∈ V (X), define ℓ(u) := ϑ(u) − ϑ(b) + out(b). Now for any edge {u, v} ∈ E(X), we have that ℓ(v) − ℓ(u) = ϑ(v) − ϑ(u) = D(u, v). This gives claim (a). 20

(7)

round T process i

∆(yi )

ϕ(i, T )

round T + 1

round T

round T + 1 +1

ϕ(i, T + 1)

4

0

D(Pyi , Pyj ) process j

D(Syi , Syj )

ϕ(j, T )

+1

ϕ(j, T + 1)

+2 0

2 +2

∆(yj ) (a)

(b)

Figure 6: Offset consistency. (a) The outputs of process i (view yi ) and process j (view yj ) in rounds T and T + 1. The dashed arrows are the clock advancements and the solid arrows the clock offsets from i to j. (b) An example with q = 5 and σ = 2, with vertices coloured by process as in Figure 4. Here, process i outputs 4 in round T and advances its clock by one to output 0 in round T + 1. Process j outputs 0 in round T and then advances its clock by two to output 2 in round T + 1. Note the difference with Figure 4c, where approximate counting guaranteed ∆(·) = 1. We now show claim (b). Fix u ∈ V (X). Since X is path connected, there exists some edge path α = (u0 = b, . . . , uk = u) from b to u. By Eq. (7), we have ℓ(u) − ℓ(b) =

k X

k
X ℓ(ui ) − ℓ(ui−1 ) = D(ui−1 , ui ).

i=1

i=1

By definition of D, we have that D(ui−1 , ui ) ≡ out(ui ) − out(ui−1 ) (mod q). Hence, we get k X

D(ui−1 , ui ) ≡

i=1

k X

out(ui ) − out(ui−1 )

(mod q).

i=1

The sum on the right-hand side telescopes, so putting the above together yields

⇐⇒

ℓ(u) − ℓ(b) ≡ out(u) − out(b)

(mod q)

ℓ(u) ≡ out(u)

(mod q),

where the equivalence follows from ℓ(b) = out(b). This gives claim (b).

6.3

Clock offset consistency across rounds

By Lemma 12, the prefix P and suffix S maps take vertices from Y to X. For any (T + 1)-round view y ∈ V (Y ), the advancement is the difference
∆(y) := out(Sy) − out(Py) mod q, (8) which measures how much the process with view y advanced its clock between rounds T and T + 1. We show that this difference must be consistent with the clock offsets in the complex X; see Figure 6. Lemma 16. For any {yi , yj } ∈ E(Y ), we have D(Syi , Syj ) + ∆(yi ) = D(Pyi , Pyj ) + ∆(yj ). 21

Proof. By definition of Y , the vertices yi and yj of the edge correspond to the (T + 1)-round views of non-crashed processes i and j in some execution with at most f crashes. Fix this execution. Let ϕ(i, ·) and ϕ(j, ·) be the outputs of these processes in this execution; we only consider the outputs in rounds T and T + 1. By Lemma 12(a), Pyi and Syi are vertices of the complex X. Moreover, out(Pyi ) = ϕ(i, T )

and

out(Syi ) = ϕ(i, T + 1),

(9)

where the first equality is by definition and the second holds by Lemma 12(b). The same holds analogously for yj . Since the protocol solves non-trivial counting, by property (N1) in Definition 5, there exists a σlift ϕ⋆ of the outputs of this execution from round T onwards. Fix ϕ⋆ and let δ := ϕ⋆ (j, T ) − ϕ⋆ (i, T ). Observe now that – By (L1), we have δ ≡ ϕ(j, T ) − ϕ(i, T ) (mod q). – By (L2), we have δ ∈ [−σ, σ]. Since δ satisfies the above two properties, by definition of d, we get that δ = d(ϕ(i, T ), ϕ(j, T )). Hence, D(Pyi , Pyj ) = d(ϕ(i, T ), ϕ(j, T )) = δ = ϕ⋆ (j, T ) − ϕ⋆ (i, T ). Analogously, we also get the identity D(Syi , Syj ) = ϕ⋆ (j, T + 1) − ϕ⋆ (i, T + 1). Consider ∆(yi ) and let η := ϕ⋆ (i, T + 1) − ϕ⋆ (i, T ). Now – By (L1), we have η ≡ ϕ(i, T + 1) − ϕ(i, T ) (mod q). – By (L3), we have η ∈ [0, q − 1]. Hence, we get that η = (ϕ(i, T + 1) − ϕ(i, T )) mod q. Now from Eq. (8) and Eq. (9), we get
∆(yi ) = out(Syi ) − out(Pyi ) mod q = (ϕ(i, T + 1) − ϕ(i, T )) mod q = ϕ⋆ (i, T + 1) − ϕ⋆ (i, T ). The identity for ∆(yj ) is analogous. Combining the above, we get     D(Syi , Syj ) − D(Pyi , Pyj ) = ϕ⋆ (j, T + 1) − ϕ⋆ (i, T + 1) − ϕ⋆ (j, T ) − ϕ⋆ (i, T )     = ϕ⋆ (j, T + 1) − ϕ⋆ (j, T ) − ϕ⋆ (i, T + 1) − ϕ⋆ (i, T ) = ∆(yj ) − ∆(yi ). Rearranging gives the claim. Lemma 17. Let ℓ be the map from Lemma 15. There exists c ∈ Z such that for all y ∈ V (Y ), ℓ(Sy) − ℓ(Py) = ∆(y) + qc. Proof. Define the map ϵ : V (Y ) → Z as ϵ(y) := ℓ(Sy) − ℓ(Py) − ∆(y).

22

By Lemma 15(b) and Eq. (8), we get that ϵ(y) ≡ 0 (mod q). We now show that ϵ is constant on V (Y ). Let {yi , yj } ∈ E(Y ). Since P and S are chromatic simplicial maps from Y to X, we get that {Pyi , Pyj }, {Syi , Syj } ∈ E(X). Rearranging and invoking Lemma 15(a) gives h i h i ϵ(yi ) − ϵ(yj ) = ℓ(Syi ) − ℓ(Pyi ) − ∆(yi ) − ℓ(Syj ) − ℓ(Pyj ) − ∆(yj ) = D(Syj , Syi ) − D(Pyj , Pyi ) + ∆(yj ) − ∆(yi ) = 0, where the last equality follows from Lemma 16. Since the complex Y is path connected, we get that ϵ is constant on V (Y ). Since also ϵ ≡ 0 (mod q), the claim follows. We are finally ready to prove Theorem 6. Theorem 6. Let σ ∈ N, q > max{2σ, 1}, n > f + 2 and f > 0. There is no f -resilient finite-state protocol for non-trivial σ-approximate q-counting that stabilises in ⌊f /2⌋ rounds. Proof. Suppose that such a protocol exists. Let ℓ : V (X) → Z be the map given by Lemma 15 and c ∈ Z be the constant from Lemma 17. By (N2), there exists a crash-free execution (ρt )t≥0 where some process i changes its output infinitely often. For all t ≥ 0, let xt ∈ V (X) be the T -round view of i in the crash-free execution started from configuration µ(ρt ), and yt ∈ V (Y ) be the (T + 1)-round view of i in the crash-free execution started from configuration µ(ρt ). Observe that Pyt = xt and Syt = xt+1 by Lemma 12(c). Define ∆t := ∆(yt ) and note that ∆t ∈ {0, 1, . . . , q − 1}. From Lemma 17, we get that ℓ(xt+1 ) − ℓ(xt ) = ∆t + qc. Rewriting yields ℓ(xt ) = ℓ(x0 ) +

t−1 X

∆r + qc .

(10)

r=0

By property (N2), we get that ∆t ≥ 1 for infinitely many t, because the output out(xt ) of i changes infinitely often in the execution (ρt )t≥0 . Now consider two cases: – If c ≥ 0, then the sum on the right-hand side tends to ∞ as t → ∞. – If c ≤ −1, then qc + ∆r ≤ −1, and the sum on the right-hand side tends to −∞ as t → ∞. By Eq. (10), this means that ℓ : V (X) → Z takes infinitely many values. However, the complex X is finite, which is a contradiction.

7

Upper bound for approximate counting

In this section, for the sake of completeness, we show an upper bound of ⌈f /2⌉ + O(log q) rounds for 1-approximate q-counting for q ≥ 4. For q = 4, we get stabilisation in ⌈f /2⌉ + 1 rounds, which matches exactly the lower bound given in Corollary 7 for any even f > 0. One attempt at obtaining the bound is to use a direct reduction to cycle agreement via the pipelining construction of Daliot and Dolev [DD05] and a terminating T -round cycle agreement protocol [AER23]. However, this would give a protocol that stabilises in 2T rounds, which is not tight, as T > ⌊f /2⌋ for any deterministic cycle agreement protocol. Instead, we construct essentially a self-stabilising version of cycle agreement, where outputs advance by one modulo q each round. However, unlike in terminating cycle agreement, we cannot first run 2-set agreement, and then switch to approximate agreement on a path (because this would require agreement on time).

23

7.1

The approximate counting protocol

Let ϕ(i, t) ∈ Zq be the state and output of process i at the end of round t. Since we are considering a self-stabilising protocol, the values ϕ(i, 0) are arbitrary. We now treat Zq as the vertices of a q-cycle graph. For a set M ⊆ Zq , choose a canonical shortest path a0 , . . . , ak , where ah = a0 + h mod q, that spans the vertices in M . Let s(M ) be the length of this path and c(M ) = a0 + ⌊k/2⌋ mod q be the vertex in the center of this path. The values in M lie on an edge if s(M ) ≤ 1. The protocol. For each t ≥ 0, let M (t) be the set consisting of the outputs ϕ(i, t) for each process i that does not crash by the end of round t. In each round t + 1, every non-crashed process i sends its previous output ϕ(i, t) to all processes, including itself, and receives a set M (i, t) ⊆ M (t). Then (1) if M (i, t) does not lie on an edge, set ϕ(i, t + 1) := c(M (i, t)) + 1 mod q, and (2) otherwise, set ϕ(i, t + 1) := ϕ(i, t) + 1 mod q. That is, if the received values do not lie on an edge, then go to the center of the shortest path spanning the vertices received. Otherwise, the values look fine, and the process increments its value by one modulo q. The last rule ensures that stabilisation persists once reached. We will call the first rule the “center rule” and the latter the “edge rule”. The analysis. The analysis is close to the standard cycle agreement analysis [AER23] adapted to the self-stabilising setting. Within ⌈f /2⌉ + 1 rounds, there will be a round with at most one crash. Once this happens, there can be only two distinct sets of received messages among the non-crashed processes, and hence, at the start of the next round there will be at most three values in play. However, these values will be close to one another. We say that M ⊆ Zq is good if s(M ) ≤ ⌈q/4⌉. Lemma 18. Let q ≥ 4. There exists a round t ≤ ⌈f /2⌉ + 1 such that M (t) is good. Proof. Consider the first round t0 with at most one crash. Let χ ∈ {0, 1} be the number of crashes in round t0 . As every earlier round has at least two crashes, we have 2(t0 − 1) + χ ≤ f , and hence t0 + χ ≤ ⌈f /2⌉ + 1. We show that M (t) is good for some t ≤ t0 + χ. Since t0 has at most one crash, there are two message sets A, B such that A ⊆ B ⊆ M (t0 − 1) received by the processes. The value of any process that does not crash in the round is in A. If t0 is crash-free, then A = B. If t0 had one crash, then B = A ∪ {v}. Consider the following three cases: (1) Suppose B lies on an edge. Then A lies on an edge and all processes apply the edge rule, and M (t0 ) is good. (2) Suppose A lies on an edge and B does not. Let b0 , . . . , bk be vertices on the fixed shortest path spanning B. Now A ⊆ {b0 , b1 } or A ⊆ {bk−1 , bk }. Of the two paths from v to A, the longer has length at least ⌈(q − 1)/2⌉. Hence, k ≤ q − ⌈(q − 1)/2⌉ ≤ ⌈q/2⌉. The processes that receive message set B choose their output to be b⌊k/2⌋+1 by the center rule. By the edge rule, the outputs of processes that receive the message set A will be either in {b1 , b2 } or {bk , bk+1 }, where bk+1 ̸= bk−1 is the other vertex adjacent to bk . Thus, the distance between the new output values is at most ⌈k/2⌉ ≤ ⌈q/4⌉. Hence, M (t0 ) is good. (3) Suppose A does not lie on an edge. Then B does not lie on an edge, and all processes apply the center rule. If M (t0 ) has exactly one value, then it is good. Suppose there are two distinct values in M (t0 ) = {a, b}. This means that round t0 had a crash, so χ = 1. Any two processes i and j that do not crash in round t0 + 1 will always receive each other’s values. Hence, the only two possible message sets are {a} and {a, b}, without loss of generality. 24

If {a, b} lies on an edge, all processes apply the edge rule, and so the new outputs lie on an edge. Otherwise, let x be the vertex in the center of the canonical shortest path from a to b. Then the outputs are contained in {a + 1 mod q, x + 1 mod q}. Since a and b are at most distance d ≤ ⌈q/2⌉ apart, x is at distance at most ⌈d/2⌉ from a. Hence, the outputs are within distance at most ⌈q/4⌉ from one another, so M (t0 + 1) is good. Once we reach a round with a good M (t), we are now essentially running approximate agreement on a path and the argument is standard. More precisely, we have the following property. Lemma 19. Let t ≥ 0 and q ≥ 4. If M (t) is good, then   s(M (t)) . s(M (t + 1)) ≤ 2 Moreover, M (t + 1) is good as well. Proof. Let I = {a0 , . . . , ak } be vertices on the fixed shortest path spanning M (t). By definition, vertices in M (t) lie on this path. Since M (t) is good, we have k ≤ ⌈q/4⌉ < q/2. Therefore, any shortest path between any two vertices in I also lies in I. Consider two processes i and j that do not crash in round t + 1. Let xi , xj ∈ M (t) be their values at the end of round t. Let yi , yj ∈ M (t + 1) be their values at the end of round t + 1. The message sets received by i and j both contain xi , xj , as i and j did not crash by round t + 1. Now we have three cases: (1) If both processes used the edge rule, then xi , xj lie on an edge, and so do yi and yj . (2) Suppose that process i used the center rule and process j did not. Since yi − 1 mod q is in the center of the shortest path spanning M (i, t), which contains xj , we get that yi is within distance at most ⌈k/2⌉ from yj . (3) Suppose that both processes used the center rule. Then the spanning subpaths used by i and j intersect and contain xi , and hence, yi − 1 and yj − 1 are at most ⌈k/2⌉ apart, as they are both centers of their respective subpaths. Hence, s(M (t + 1)) ≤ ⌈k/2⌉ ≤ k and M (t + 1) is good. Theorem 20. Let q ≥ 4. There is a 1-approximate q-counting protocol that stabilises by round ⌈f /2⌉ + ⌈log2 q⌉ − 1. Proof. By Lemma 18, there is some round t ≤ ⌈f /2⌉ + 1 when M (t) is good. Then apply Lemma 19 K := ⌈log2 q⌉ − 2 times. Since s(M (t)) ≤ ⌈q/4⌉, for T = t + K, we get l q m s(M (T )) ≤ K+2 ≤ 1, 2 so M (T ) lies on an edge and remains on an edge, and all processes apply the edge rule for all future rounds by induction. Hence, the protocol stabilises in T rounds, which gives the claim.

25

8

Conclusions

In this work, we proved the first non-trivial and asymptotically tight lower bound of Ω(f ) rounds for approximate clock synchronisation tasks that guarantee both transient and non-transient fault tolerance. The lower bound holds in a strong model: processes have perfect local clocks without drift, communication is synchronous, and the only non-transient faults are crashes. Existing upper bounds work even when the non-transient faults are Byzantine, providing very high levels of resilience. Approximate clock synchronisation tasks that require only Byzantine fault tolerance or only self-stabilisation, but not both, have been known to be considerably easier to solve. Our results show that achieving a higher level of resilience by combining both types of fault tolerance necessarily comes with a high price in worst-case stabilisation time – at least for deterministic algorithms. To the best of our knowledge, this is the first use of the topological framework of distributed computing to prove lower bounds for self-stabilising tasks. For accessibility, we kept the exposition combinatorial, but in topological terms, the proof is a covering-space argument: as simply connected complexes have “vanishing first cohomology” (i.e., every 1-cocycle is a 1-coboundary), we can lift the output map from the protocol complex to the universal cover Z of the q-cycle Zq . The prefix and suffix maps then show that the lifted outputs of any process in two consecutive rounds differ by its clock increment plus a multiple of q that is the same for all processes and executions. In a crash-free execution in which some process changes its output infinitely often, the lifted outputs of this process diverge, contradicting the finiteness of the protocol complex. This leads to a few further questions. First, are there network-dependent lower bounds for clock synchronisation in general communication networks, analogous to those for k-set agreement [FNP+25]? Second, what is the broader role of cohomology in the topology of distributed computing [FHR25, HTR+23]? Finally, are there topological characterisations of the solvability of self-stabilising tasks, analogous to those known for terminating tasks [HKR14]?

Acknowledgements The author is grateful to Faith Ellen for many useful discussions and her insightful observations, which helped clarify the main ideas and the approach taken in this work. The author also thanks Yaroslav Verbitsky for his helpful feedback on an earlier draft of the manuscript.

AI methodology The author used GPT-6 and Claude Opus 5.5 to assist with finding and developing the lower bound construction, drawing illustrations, and improving the presentation. The tools materially affected drafting and streamlining technical parts of Sections 2 and 5 to 7. The text has been written by the author, but copyediting has been done using AI tools. The idea of reducing pulse synchronisation to relaxations of approximate counting is by the author. In particular, there was a weaker gluing-based lower bound for a restricted class of crash-tolerant protocols that predates the use of AI tools. The author first posed the question of whether set agreement and cycle agreement lower bounds extend to self-stabilising variants under crash faults. Then the author posed the same question for the approximate counting task. For the latter question, GPT-6 eventually supplied the first prefix– suffix construction, which compared overlapping execution windows, using the two synchronous full-information protocol complexes obtained from [HRT09]. The original construction used a more involved covering-space argument. Claude Opus 5.5 was used to verify and simplify the construction. Further simplifications, and the non-trivial counting generalisation used for the pulse synchronisation reduction, were developed interactively with both AI tools. The author verified the correctness and originality of all content, including references, and takes full responsibility for any errors. 26

References [AAD05]

Ittai Abraham, Yonatan Amit, and Danny Dolev. “Optimal resilience asynchronous approximate agreement”. In: Proc. International Conference on Principles of Distributed Systems (OPODIS 2004). 2005, pp. 229–239. doi: 10.1007/11516798 17.

[AT99]

Marcos Kawazoe Aguilera and Sam Toueg. “A simple bivalency proof that t-resilient consensus requires t + 1 rounds”. In: Information Processing Letters 71.3–4 (1999), pp. 155–158. doi: 10.1016/S0020-0190(99)00100-3.

[AR26]

Augustin Albert and Sergio Rajsbaum. “Solving approximate agreement on continuous and discrete spaces”. In: Proc. International Colloquium on Theoretical Aspects of Computing (ICTAC 2026). To Appear. 2026. doi: 10.48550/arXiv.2606.23260.

[ACF+19]

Manuel Alcántara, Armando Castañeda, David Flores-Peñaloza, and Sergio Rajsbaum. “The topology of look-compute-move robot wait-free algorithms with hard termination”. In: Distributed Computing 32.3 (2019), pp. 235–255. doi: 10.1007/s00446-018-0345-3.

[AAE+23]

Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why extension-based proofs fail”. In: SIAM Journal on Computing 52.4 (2023), pp. 913–944. doi: 10.1137/20M1375851.

[AER23]

Dan Alistarh, Faith Ellen, and Joel Rybicki. “Wait-free approximate agreement on graphs”. In: Theoretical Computer Science 948, 113733 (2023). doi: 10.1016/j.tcs.2023. 113733.

[Arm83]

M. A. Armstrong. Basic topology. Undergraduate Texts in Mathematics. Springer, 1983. doi: 10.1007/978-1-4757-1793-8.

[ADG91]

Anish Arora, Shlomi Dolev, and Mohamed G. Gouda. “Maintaining digital clocks in step”. In: Parallel Processing Letters 1.1 (1991), pp. 11–18. doi: 10.1142/S0129626491000161.

[AKM+07] Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George Varghese. “A time-optimal self-stabilizing synchronizer using a phase clock”. In: IEEE Transactions on Dependable and Secure Computing 4.3 (2007), pp. 180–190. doi: 10.1109/tdsc.2007.1007. [BGS21]

Paul Bastide, George Giakkoupis, and Hayk Saribekyan. “Self-stabilizing clock synchronization with 1-bit messages”. In: Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2021). 2021, pp. 2154–2173. doi: 10.1137/1.9781611976465.129.

[BDH08]

Michael Ben-Or, Danny Dolev, and Ezra N. Hoch. “Fast self-stabilizing Byzantine tolerant digital clock synchronization”. In: Proc. ACM Symposium on Principles of Distributed Computing (PODC 2008). 2008, pp. 385–394. doi: 10.1145/1400751.1400802.

[BKN17]

Lucas Boczkowski, Amos Korman, and Emanuele Natale. “Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits”. In: Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2017). 2017, pp. 2540–2559. doi: 10.1137/1.9781611974782.168.

[BPV08]

Christian Boulinier, Franck Petit, and Vincent Villain. “Synchronous vs. asynchronous unison”. In: Algorithmica 51.1 (2008), pp. 61–80. doi: 10.1007/s00453-007-9066-x.

[BLR19]

Johannes Bund, Christoph Lenzen, and Will Rosenbaum. “Fault tolerant gradient clock synchronization”. In: Proc. ACM Symposium on Principles of Distributed Computing (PODC 2019). 2019, pp. 357–365. doi: 10.1145/3293611.3331637.

27

[CG14]

Yiqing Cai and Robert Ghrist. “Cyclic network automata and cohomological waves”. In: Proc. International Symposium on Information Processing in Sensor Networks (IPSN 2014). 2014, pp. 215–224. doi: 10.1109/ipsn.2014.6846754.

[CHL+00]

Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, and Mark R. Tuttle. “Tight bounds for k-set agreement”. In: Journal of the ACM 47.5 (2000), pp. 912–943. doi: 10.1145/355483.355489.

[Coa88]

B. A. Coan. “A compiler that increases the fault tolerance of asynchronous protocols”. In: IEEE Transactions on Computers 37.12 (1988), pp. 1541–1553. doi: 10.1109/12.9732.

[CFG92]

Jean-Michel Couvreur, Nissim Francez, and Mohamed G. Gouda. “Asynchronous unison (extended abstract)”. In: Proc. International Conference on Distributed Computing Systems (ICDCS 1992). 1992, pp. 486–493. doi: 10.1109/ICDCS.1992.235005.

[DD05]

Ariel Daliot and Danny Dolev. “Self-stabilization of Byzantine protocols”. In: Proc. International Symposium on Self-Stabilizing Systems (SSS 2005). 2005, pp. 48–67. doi: 10.1007/11577327 4.

[DDP03]

Ariel Daliot, Danny Dolev, and Hanna Parnas. “Self-stabilizing pulse synchronization inspired by biological pacemaker networks”. In: Proc. International Symposium on Self-Stabilizing Systems (SSS 2003). 2003, pp. 32–48. doi: 10.1007/3-540-45032-7 3.

[DDP04]

Ariel Daliot, Danny Dolev, and Hanna Parnas. “Linear time Byzantine self-stabilizing clock synchronization”. In: Proc. International Conference on Principles of Distributed Systems (OPODIS 2003). 2004, pp. 7–19. doi: 10.1007/978-3-540-27860-3 4.

[Dij74]

Edsger W. Dijkstra. “Self-stabilizing systems in spite of distributed control”. In: Communications of the ACM 17.11 (1974), pp. 643–644. doi: 10.1145/361179.361202.

[DFL+15]

Danny Dolev, Matthias Függer, Christoph Lenzen, Ulrich Schmid, and Andreas Steininger. “Fault-tolerant distributed systems in hardware”. In: Bulletin of the EATCS 116 (2015). url: https://bulletin.eatcs.org/index.php/beatcs/article/view/348.

[DFS+14]

Danny Dolev, Matthias Függer, Ulrich Schmid, and Christoph Lenzen. “Fault-tolerant algorithms for tick-generation in asynchronous logic: robust pulse generation”. In: Journal of the ACM 61.5, 30 (2014), 30:1–30:74. doi: 10.1145/2560561.

[DHS+95]

Danny Dolev, Joseph Y. Halpern, Barbara Simons, and Ray Strong. “Dynamic faulttolerant clock synchronization”. In: Journal of the ACM 42.1 (1995), pp. 143–185. doi: 10.1145/200836.200870.

[DHS86]

Danny Dolev, Joseph Y. Halpern, and H. Raymond Strong. “On the possibility and impossibility of achieving clock synchronization”. In: Journal of Computer and System Sciences 32.2 (1986), pp. 230–250. doi: 10.1016/0022-0000(86)90028-0.

[DHJ+16]

Danny Dolev, Keijo Heljanko, Matti Järvisalo, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, Jukka Suomela, and Siert Wieringa. “Synchronous counting and computational algorithm design”. In: Journal of Computer and System Sciences 82.2 (2016), pp. 310–332. doi: 10.1016/j.jcss.2015.09.002.

[DH07]

Danny Dolev and Ezra N. Hoch. “Byzantine self-stabilizing pulse in a bounded-delay model”. In: Proc. International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2007). 2007, pp. 234–252. doi: 10.1007/978-3-540-76627-8 19.

[DLP+86]

Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. “Reaching approximate agreement in the presence of faults”. In: Journal of the ACM 33.3 (1986), pp. 499–516. doi: 10.1145/5925.5931. 28

[Dol00]

Shlomi Dolev. Self-stabilization. The MIT Press, 2000. doi: 10.7551/mitpress/6156.001.0001.

[DNS+21]

Shlomi Dolev, Ram Prasadh Narayanan, Christian Scheideler, and Christian Schindelhauer. “Logarithmic time MIMO based self-stabilizing clock synchronization”. In: Proc. ACM International Conference on Nanoscale Computing and Communication (NANOCOM 2021). 2021, 30, 30:1–30:2. doi: 10.1145/3477206.3477471.

[DW04]

Shlomi Dolev and Jennifer L. Welch. “Self-stabilizing clock synchronization in the presence of Byzantine faults”. In: Journal of the ACM 51.5 (2004), pp. 780–799. doi: 10.1145/1017460.1017463.

[EK21]

Yuval Emek and Eyal Keren. “A thin self-stabilizing asynchronous unison algorithm with applications to fault tolerant biological networks”. In: Proc. ACM Symposium on Principles of Distributed Computing (PODC 2021). 2021, pp. 93–102. doi: 10.1145/ 3465084.3467922.

[Fek90]

Alan David Fekete. “Asymptotically optimal algorithms for approximate agreement”. In: Distributed Computing 4.1 (1990), pp. 9–29. doi: 10.1007/BF01783662.

[FHR25]

Stephan Felber, Bernardo Hummes Flores, and Hugo Rincon-Galeana. “Brief announcement: a sheaf-theoretic characterization of tasks in distributed systems”. In: Proc. International Colloquium on Structural Information and Communication Complexity (SIROCCO 2025). 2025, pp. 425–430. doi: 10.1007/978-3-031-91736-3 26.

[FKS20]

Michael Feldmann, Ardalan Khazraei, and Christian Scheideler. “Time- and spaceoptimal discrete clock synchronization in the beeping model”. In: Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020). 2020, pp. 223–233. doi: 10.1145/3350755.3400246.

[FL82]

Michael J. Fischer and Nancy A. Lynch. “A lower bound for the time to assure interactive consistency”. In: Information Processing Letters 14.4 (1982), pp. 183–186. doi: 10.1016/0020-0190(82)90033-3.

[FNP+25]

Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz, Ulrich Schmid, and Hugo RinconGaleana. “Lower bounds for k-set agreement in fault-prone networks”. In: Proc. International Symposium on Distributed Computing (DISC 2025). 2025, 31:1–31:22. doi: 10.4230/LIPIcs.DISC.2025.31.

[GH90]

Mohamed G. Gouda and Ted Herman. “Stabilizing unison”. In: Information Processing Letters 35.4 (1990), pp. 171–175. doi: 10.1016/0020-0190(90)90020-X.

[GLS18]

Janko Gravner, Hanbaek Lyu, and David Sivakoff. “Limiting behavior of 3-color excitable media on arbitrary graphs”. In: The Annals of Applied Probability 28.6 (2018), pp. 3324–3357. doi: 10.1214/17-AAP1350.

[Hat02]

Allen Hatcher. Algebraic topology. Cambridge University Press, 2002. isbn: 9780521795401. url: https://pi.math.cornell.edu/∼hatcher/AT/ATpage.html.

[HKR14]

Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum. Distributed computing through combinatorial topology. Morgan Kaufmann, 2014. doi: 10.1016/C2011-0-07032-1.

[HR03]

Maurice Herlihy and Sergio Rajsbaum. “A classification of wait-free loop agreement tasks”. In: Theoretical Computer Science 291.1 (2003), pp. 55–77. doi: 10.1016/S03043975(01)00396-6.

[HRT01]

Maurice Herlihy, Sergio Rajsbaum, and Mark Tuttle. “A new synchronous lower bound for set agreement”. In: Proc. International Conference on Distributed Computing (DISC 2001). 2001, pp. 136–150. doi: 10.1007/3-540-45414-4 10. 29

[HRT09]

Maurice Herlihy, Sergio Rajsbaum, and Mark Tuttle. “An axiomatic approach to computing the connectivity of synchronous and asynchronous systems”. In: Electronic Notes in Theoretical Computer Science 230 (2009), pp. 79–102. doi: 10.1016/j.entcs.2009. 02.018.

[HS99]

Maurice Herlihy and Nir Shavit. “The topological structure of asynchronous computability”. In: Journal of the ACM 46.6 (1999), pp. 858–923. doi: 10.1145/331524.331529.

[HDD06]

Ezra N. Hoch, Danny Dolev, and Ariel Daliot. “Self-stabilizing Byzantine digital clock synchronization”. In: Proc. International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2006). 2006, pp. 350–362. doi: 10.1007/978-3-54049823-0 25.

[HTR+23]

Alan Hylton, Natalie Tsuei, Mark Ronnenberg, Jihun Hwang, Brendan Mallery, Jonathan Quartin, Colin Levaunt, Jeremy Quail, and Justin Curry. “Toward time synchronization in delay tolerant network based Solar System internetworking”. In: Proc. IEEE Aerospace Conference (AERO 2023). 2023, pp. 1–20. doi: 10.1109/AERO55745.2023. 10115764.

[KL19]

Pankaj Khanchandani and Christoph Lenzen. “Self-stabilizing Byzantine clock synchronization with optimal precision”. In: Theory of Computing Systems 63.2 (2019), pp. 261–305. doi: 10.1007/s00224-017-9840-3.

[Lam78]

Leslie Lamport. “Time, clocks, and the ordering of events in a distributed system”. In: Communications of the ACM 21.7 (1978), pp. 558–565. doi: 10.1145/359545.359563.

[LM85]

Leslie Lamport and P. M. Melliar-Smith. “Synchronizing clocks in the presence of faults”. In: Journal of the ACM 32.1 (1985), pp. 52–78. doi: 10.1145/2455.2457.

[LSP82]

Leslie Lamport, Robert Shostak, and Marshall Pease. “The Byzantine generals problem”. In: ACM Transactions on Programming Languages and Systems 4.3 (1982), pp. 382–401. doi: 10.1145/357172.357176.

[LL22]

Christoph Lenzen and Julian Loss. “Optimal clock synchronization with signatures”. In: Proc. ACM Symposium on Principles of Distributed Computing (PODC 2022). 2022, pp. 440–449. doi: 10.1145/3519270.3538444.

[LL26]

Christoph Lenzen and Julian Loss. “Early-stabilizing counting”. In: Proc. ACM Symposium on Principles of Distributed Computing (PODC 2026). 2026, pp. 121–131. doi: 10.1145/3796701.3815925.

[LR19a]

Christoph Lenzen and Joel Rybicki. “Near-optimal self-stabilising counting and firing squads”. In: Distributed Computing 32.4 (2019), pp. 339–360. doi: 10.1007/s00446-0180342-6.

[LR19b]

Christoph Lenzen and Joel Rybicki. “Self-stabilising Byzantine clock synchronisation is almost as easy as consensus”. In: Journal of the ACM 66.5, 32 (2019), 32:1–32:56. doi: 10.1145/3339471.

[LRS17]

Christoph Lenzen, Joel Rybicki, and Jukka Suomela. “Efficient counting with optimal resilience”. In: SIAM Journal on Computing 46.4 (2017), pp. 1473–1500. doi: 10.1137/ 16M107877X.

[Liu23]

Shihao Liu. “The impossibility of approximate agreement on a larger class of graphs”. In: Proc. International Conference on Principles of Distributed Systems (OPODIS 2022). 2023, pp. 22–1. doi: 10.4230/LIPIcs.OPODIS.2022.22.

30

[LXP09]

Xingwu Liu, Zhiwei Xu, and Jianzhong Pan. “Classifying rendezvous tasks of arbitrary dimension”. In: Theoretical Computer Science 410.21–23 (2009), pp. 2162–2173. doi: 10.1016/j.tcs.2009.01.033.

[LL84]

Jennifer Lundelius and Nancy Lynch. “An upper and lower bound for clock synchronization”. In: Information and Control 62.2–3 (1984), pp. 190–204. doi: 10.1016/s00199958(84)80033-9.

[Lyn96]

Nancy A. Lynch. Distributed algorithms. Morgan Kaufmann, 1996. isbn: 9781558603486.

[NR19]

Thomas Nowak and Joel Rybicki. “Byzantine approximate agreement on graphs”. In: Proc. International Symposium on Distributed Computing (DISC 2019). 2019, 29:1–29:17. doi: 10.4230/LIPIcs.DISC.2019.29.

[PSL80]

Marshall Pease, Robert Shostak, and Leslie Lamport. “Reaching agreement in the presence of faults”. In: Journal of the ACM 27.2 (1980), pp. 228–234. doi: 10.1145/ 322186.322188.

[RV26]

Joel Rybicki and Yaroslav Verbitsky. “Solvability of approximate agreement on graphs and simplicial complexes”. In: Proc. International Symposium on Distributed Computing (DISC 2026). 2026, 7:1–7:22. doi: 10.4230/LIPIcs.DISC.2026.7.

[SZ00]

Michael Saks and Fotios Zaharoglou. “Wait-free k-set agreement is impossible: the topology of public knowledge”. In: SIAM Journal on Computing 29.5 (2000), pp. 1449– 1483. doi: 10.1137/S0097539796307698.

[SFR26]

Ulrich Schmid, Stephan Felber, and Hugo Rincon Galeana. “A topological characterization of stabilizing consensus”. In: Distributed Computing 39.3, 17 (2026). doi: 10.1007/s00446-026-00508-z.

[ST87]

T. K. Srikanth and Sam Toueg. “Optimal clock synchronization”. In: Journal of the ACM 34.3 (1987), pp. 626–645. doi: 10.1145/28869.28876.

[WL88]

Jennifer Lundelius Welch and Nancy Lynch. “A new fault-tolerant algorithm for clock synchronization”. In: Information and Computation 77.1 (1988), pp. 1–36. doi: 10.1016/0890-5401(88)90043-0.

31

Related documents

• Lantern: Finding Committable Transactions via Back-Propagation on DAGs#925658
• Replication Error and Time Evolution of a Self-Replicating System#639131
• CVE-2026-109954 — HIGH 8.3#1347011
• Reliable Object Storage to Support Atomic Actions#472196
• The End of Approximate Computing_ RIC and the First Fully Deterministic Execution Substrate#108883