On Latency-Optimal Implementations of the Timestamp Object

On Latency-Optimal Implementations of the Timestamp Object Aurojit Panda∗

Scott Shenker†

Sam Toueg‡

Wen Zhang§

arXiv:2610.32844v1 [cs.DC] 23 Oct 2026

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

Contents 1 Introduction

3

2 System Model and Latency under Crash Failures 2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Worst-Case Message Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 4

3 The Timestamp Object

5

4 Results for Crash Failures 4.1 Maximum Resilience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Latency Upper Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Two-Delay Algorithm for f = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Three-Delay Algorithm for General f . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Latency Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Auxiliary Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 The Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 7 7 10 12 12 13 18

5 Adapting to Byzantine Failures 18 5.1 System Model and Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 Implementations of the Timestamp Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 ∗ New York University. Email: apanda@cs.nyu.edu.

† UC Berkeley and ICSI. Email: shenker@icsi.berkeley.edu. ‡ University of Toronto. Email: sam@cs.toronto.edu. § Google. Email: wnz@google.com.

1

6 Results for Byzantine Failures with Digital Signatures 20 6.1 Maximum Resilience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.2 Latency Upper Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.3 Latency Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 7 Results for Byzantine Failures without Digital Signatures 30 7.1 Maximum Resilience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 7.2 Latency Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 7.3 Latency Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7.3.1 Auxiliary Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7.3.2 The Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7.4 Summary and Open Question . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 8 Related Work

37

9 Conclusion

38

10 AI Methodology

38

A Auxiliary Notations

40

B Properties of Finite Worst-Case Message Delay 40 B.1 Finite Worst-Case Message Delay Implies Liveness . . . . . . . . . . . . . . . . . . . . . . . . 41 B.2 A Finite Worst-Case Message Delay Is an Integer . . . . . . . . . . . . . . . . . . . . . . . . . 41 C Auxiliary Results for Latency Lower Bounds 43 C.1 Proofs of the Loquacious-Transformation Lemmas . . . . . . . . . . . . . . . . . . . . . . . . 43 C.1.1 Crash Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 C.1.2 Byzantine Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 C.2 Weaker Timeliness Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 C.3 Proofs of the Completion Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 C.3.1 Crash Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 C.3.2 Byzantine Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 D Proof of the Two-Delay Lower Bound for Crash Failures

2

54

1

Introduction

The timestamp object (TS) provides a single operation, next(), which returns a positive integer called a timestamp. Each next() operation returns a timestamp larger than all previously returned ones; timestamps need not be consecutive. Many message-passing algorithms, notably implementations of atomic registers, generate ordered tags or timestamps internally (see Section 8). We instead study TS as an object in its own right, implemented in asynchronous message-passing systems subject to process failures. We ask two questions: What is the maximum resilience and the minimum latency of TS implementations? We focus on systems in which network communication, rather than local computation, dominates the time an operation takes. Accordingly, we measure latency in terms of worst-case message delay: intuitively, the longest time an operation can take when local computation is instantaneous and every message sent during the operation is received within one time unit (we define this precisely in Section 2.2). We answer these questions under various types of failure: crash failures, and Byzantine failures with and without digital signatures. To do so, we develop lower bounds and algorithms that determine (1) the optimal resilience of TS implementations under each type of failure, and (2) the optimal latency in all cases but one. Our results are summarized in Table 1, where n ≥ 2 is the number of processes in the system and 1 ≤ f < n is the maximum number of faulty processes. As the table shows, the optimal latency depends on whether more than one process may fail and, under Byzantine failures, on whether digital signatures are available. Only one case remains open: Byzantine failures without digital signatures when n > 4 and f = 1. There, we narrow the optimal latency down to either two or three message delays. We also introduce a new lower-bound technique, which we call a cyclic chain argument. The argument constructs a cycle of indistinguishable schedules along which the returned timestamps must strictly increase, yielding a contradiction. We defer the proofs of several auxiliary results to the appendices. Table 1: Summary of results on implementing the timestamp object (TS), where n ≥ 2 is the number of processes in the system and 1 ≤ f < n is the maximum number of faulty processes. When TS is implementable, we report a lower bound and an upper bound on the optimal latency of implementing TS, i.e., the smallest worst-case message delay of any implementation of TS. A check mark ✓ indicates that the lower and upper bounds match. References set in gray point to observations, which follow immediately from results elsewhere in the table. Optimal latency (in message delay units) Failure type Crash Byzantine with signatures

Byzantine

2

TS implementable iff

# of failures

Lower bound

Upper bound

Tight?

n > 2f

f ≥2

3 (Thm. 4.23)

3 (Alg. 2)

✓

(only if: Prop. 4.1)

f =1

2 (Prop. 4.22)

2 (Alg. 1)

✓

n > 3f

f ≥2

3 (Obs. 6.42)

3 (Obs. 6.2)

✓

(only if: Prop. 6.1)

f =1

2 (Obs. 6.41)

2 (Alg. 3)

✓

f ≥2

3 (Obs. 7.14)

n > 3f (only if: Obs. 7.1)

n = 4,

f =1

3 (Thm. 7.15)

n > 4,

f =1

2 (Obs. 7.13)

✓ 3 (Alg. 4)

✓

System Model and Latency under Crash Failures

We first define the system model and latency measure for crash failures; Section 5 adapts these definitions to systems with Byzantine processes.

3

2.1

System Model

The system consists of n ≥ 2 processes connected pairwise by reliable asynchronous channels. At most f processes may crash, where 1 ≤ f < n. Processes take steps asynchronously. In each step, a process may invoke an operation, receive and send finitely many messages, and return from an operation by producing a response. A process may invoke an operation in any step, provided its earlier operations have returned. An algorithm A assigns to each process p a deterministic automaton Ap . Each transition of Ap maps process p’s current state, an optional operation invocation, and the received messages to a new state, outgoing messages, and any response to p’s pending operation. A schedule S of A is an infinite sequence of steps, each taken according to A, in which at least n − f processes take infinitely many steps. The processes that take infinitely many steps are correct in S; all other processes are faulty. In a schedule, every message is received at most once and only if it was sent to its recipient in an earlier step, and every message sent to a process that takes infinitely many steps is eventually received. A schedule prefix σ of A is a finite prefix of a schedule of A. An operation consists of an invocation step and its corresponding return step, if any. An operation is complete if it returns and incomplete otherwise.

2.2

Worst-Case Message Delay

With the system model in place, we now turn to measuring the latency of algorithms. Defining such a measure can be subtle in asynchronous systems, where an algorithm’s running time is at the mercy of message and computation delays beyond its control. (See, for example, recent work by Bezerra et al. [BFKR25, Section 6] for a discussion of the subtleties involved.) Following convention, we measure an algorithm’s latency in units of message delay, an approach well suited to environments in which latency is dominated by communication rather than by local computation. Specifically, we study an algorithm’s worst-case message delay: intuitively, the longest duration an operation can take when local computation is instantaneous and every message sent during the operation is received within one unit of time. (A similar measure appears as early as Awerbuch [Awe85, Section 2.1]; see Attiya and Welch [AW04, Section 2.1.2] for a more detailed exposition.) A schedule records the order of steps but not the times at which they occur. To measure the latency of messages and operations, we assign a real time to each step. These times are used only for analysis and are not accessible to the processes. Definition 2.1 (Run). A run R = (S, T ) of A consists of a schedule S of A and a non-decreasing, unbounded sequence T of real numbers, where T [j] is the time of step S[j], such that: (1) if a message sent in step S[j] is received in step S[k], then T [j] < T [k]; and (2) if steps S[j] and S[k] with j < k are taken by the same process, then T [j] < T [k]. A process is correct in R if it is correct in S, and faulty otherwise. A run assigns a single time to each step, treating it as instantaneous even though it may perform an arbitrary finite amount of local computation. This choice reflects the intuitive notion of worst-case message delay described in Section 1, in which local computation takes no time. We now define the latency of a message and of an operation in a run R. Definition 2.2 (Message latency). In a run R = (S, T ), if a message m is sent in step S[j] and received in ∆ step S[k], then its latency in R is δR (m) = T [k] − T [j]. Definition 2.3 (Timely message). In a run, a message is timely if its latency is at most one unit of time. Definition 2.4. In a run R = (S, T ), let O be an operation invoked in step S[a].

4

• The time interval of O is ( [T [a], T [b]], if O returns in step S[b], IR (O) = [T [a], ∞), if O is incomplete. ∆

• The latency of O, denoted δR (O), is the length of IR (O). In particular, δR (O) = ∞ if O is incomplete. • A message is sent during O if its send time lies in IR (O). Definition 2.5. In a run R = (S, T ), let L be the set of processes that take infinitely many steps in S, and let O be an operation. We say that messages are timely during O if every message sent during O to a process in L is timely. All these notions are relative to a run, which we specify explicitly when needed. When the run R is clear from context, we omit it from the notation, writing I(O), δ(m), and δ(O). Definition 2.6 (Worst-case message delay). The worst-case message delay of an algorithm A is   R is a run of A,   ∆ . δ(A) = sup δR (O) O is an operation in R invoked by a correct process in R,   messages are timely during O If δ(A) is finite, two simple but useful consequences follow: Proposition 2.7. If δ(A) < ∞, then A satisfies liveness: In every schedule of A, every operation invoked by a correct process eventually returns. Proposition 2.8. If δ(A) < ∞, then δ(A) = k for some nonnegative integer k. Accordingly, whenever we refer to a worst-case message delay of k, we take k to be a nonnegative integer. Both propositions are intuitively clear, but their proofs require some technical care; we defer them to Appendix B.

3

The Timestamp Object

We now define the timestamp object and the requirements for implementing it. Definition 3.1 (Timestamp object). The timestamp object, denoted TS, has a single operation next() and the following (nondeterministic) sequential specification: State: last ∈ Z≥0 , initially 0. next(): choose any ∆ ∈ Z≥1 last ← last + ∆ return last Thus, the sequential specification of TS requires each next() operation to return a positive integer strictly larger than every value returned by an earlier operation. We require implementations of TS to satisfy linearizability with respect to this specification. Following Herlihy and Wing [HW90], a history is the sequence of operation invocations and responses in a schedule. In a history, an operation precedes another if its response occurs before the other’s invocation. Intuitively, a history H is (crash) linearizable with respect to TS if, after discarding some incomplete operations and appending responses to the remaining incomplete operations, the resulting operations can be arranged into a sequential history H ′ that (1) satisfies the sequential specification of TS and (2) preserves the precedence of operations in H. 5

Definition 3.2 (TS implementation). Let A be an algorithm whose next() operation returns positive integers. We say that A implements TS in a system with crash failures if every schedule S of A, with corresponding history H, satisfies the following conditions: (CT1) Safety: H is linearizable with respect to TS. (CT2) Liveness: Every operation invoked by a correct process in S eventually returns. We call such an algorithm A an implementation of TS. The following equivalent characterization of TS implementations replaces the linearizability condition with two conditions on the values returned by complete operations. Proposition 3.3 (Characterization of TS implementations). Let A be an algorithm whose next() operation returns positive integers. Then A implements TS in a system with crash failures if and only if every schedule S of A, with corresponding history H, satisfies the following conditions: (CT1a) Ordering: If a complete operation O1 precedes a complete operation O2 in H, then O1 returns a smaller value than O2 . (CT1b) Uniqueness: No two distinct complete operations in H return the same value. (CT2) Liveness: Every operation invoked by a correct process in S eventually returns. Proof. The liveness condition (CT2) is the same in Definition 3.2 and the proposition. It therefore suffices to show that, for the history of every schedule of A, (CT1) ⇐⇒ (CT1a) ∧ (CT1b). We prove the two directions separately, in a form that we will reuse for the Byzantine analogue (Proposition 5.3). Claim 3.4. For every history H, (CT1) =⇒ (CT1a) ∧ (CT1b). Proof. Suppose that H satisfies (CT1). Since H is linearizable with respect to TS, we can discard some incomplete operations from H, append responses to the remaining incomplete operations, and arrange the resulting operations into a sequential history H ′ that (1) satisfies the sequential specification of TS and (2) preserves the precedence of operations in H. Every complete operation in H therefore appears in H ′ with the same return value. By the sequential specification of TS, each next() operation increases last by some ∆ ≥ 1 and returns the new value of last. Hence, the values returned by successive operations in H ′ are strictly increasing. For (CT1a), suppose that a complete operation O1 precedes a complete operation O2 in H. Since H ′ preserves the precedence of operations in H, O1 appears before O2 in H ′ and therefore returns a smaller value. For (CT1b), let O1 and O2 be distinct complete operations in H. Both appear in H ′ with the same return values as in H. Since H ′ is sequential, one appears before the other; because return values strictly increase in H ′ , they return distinct values. Claim 3.4 Claim 3.5. For every history H whose complete operations return positive integers, (CT1a) ∧ (CT1b) =⇒ (CT1). Proof. Suppose that H satisfies (CT1a) and (CT1b). Discard all incomplete operations from H, and arrange the complete operations into a sequential history H ′ in increasing order of their return values.1 To show that H is linearizable with respect to TS, it remains to show that H ′ satisfies the sequential specification of TS and preserves the precedence of operations in H. The return values in H ′ are positive integers and, by construction and (CT1b), strictly increasing. Thus, H ′ satisfies the sequential specification of TS. 1 The history H ′ is well defined even if H contains infinitely many complete operations: The complete operations in H return positive integers and, by (CT1b), have distinct return values. Thus, an operation returning v has at most v − 1 complete operations with smaller return values, so the complete operations can be listed in increasing order of return value.

6

Next, suppose that a complete operation O1 precedes a complete operation O2 in H. By (CT1a), O1 returns a smaller value than O2 . Since H ′ orders operations by increasing return value, O1 appears before O2 in H ′ . Hence, H ′ preserves the precedence of operations in H. Therefore, H is linearizable with respect to TS. Claim 3.5 Since the next() operation of A returns positive integers, Claims 3.4 and 3.5 prove the proposition. Proposition 3.3

4

Results for Crash Failures

In this section, we consider implementations of TS in systems with crash failures. Recall that we assume there are n ≥ 2 processes in the system, of which at most f ≥ 1 may crash.

4.1

Maximum Resilience

Proposition 4.1. In a system with crash failures, there exists an implementation of TS only if n > 2f . Proof. By a standard partitioning argument.

4.2

Proposition 4.1

Latency Upper Bounds

We now give two upper bounds on the worst-case message delay of implementing TS under crash failures, first for f = 1 and then for general f . 4.2.1

Two-Delay Algorithm for f = 1

When f = 1, TS can be implemented in two message delays. Theorem 4.2. In a system with crash failures, if n > 2f and f = 1, then there exists an implementation of TS (Algorithm 1) whose worst-case message delay is two. Proof. We first establish some supporting properties of the algorithm.2 We then show that the algorithm implements TS by proving that it returns positive integers and satisfies ordering (CT1a), uniqueness (CT1b), and liveness (CT2). Finally, we show that its worst-case message delay is two. Claim 4.3. For every process pi , its local clock xi is non-decreasing. Proof. After initialization, only lines 13 and 20 assign to xi , and neither decreases it.

Claim 4.3

Claim 4.4. If an invocation of next() computes base timestamp t on line 19, then at the time of return, at least two distinct processes pj satisfy xj ≥ t. Proof. Let pi be the process performing the invocation. Write R = {j : ⟨j, −⟩ ∈ repliesi } when pi computes t on line 19. By line 18, |repliesi | = n − 2; by line 11, each sender contributes at most one element to repliesi , so |R| = n − 2 ≥ 1. Moreover, pi sends no request to itself (line 9) and therefore receives no reply from itself, so i ∈ / R. For each j ∈ R, let vj be the unique value such that ⟨j, vj ⟩ ∈ repliesi when pi computes t (line 19). Since t = maxj∈R vj , choose ℓ ∈ R such that vℓ = t. By lines 13 and 14, process pℓ has xℓ = vℓ = t when it sends its reply. By Claim 4.3, xℓ ≥ t still holds when pi returns. For the invoking process pi , line 20 sets xi ← max(xi , t) before line 23 returns. Hence, xi ≥ t at the time of return. Since ℓ ∈ R and i ∈ / R, the processes pℓ and pi are distinct, and the claim follows. Claim 4.4 2 In our pseudocode, upon blocks are uninterruptible: Each runs to completion before another begins.

7

Algorithm 1 A worst-case two-delay implementation of TS in a system with crash failures where n > 2f and f = 1. Code for process pi (0 ≤ i < n): 1: xi ← 0 ▷ pi ’s local clock. 2: seqi ← 0 ▷ Sequence number of pi ’s ongoing invocation, or of its next invocation when idle. 3: reqSeqi [j] ← −1 for each j ̸= i ▷ Largest q in a ⟨Req q, −⟩ received from pj . 4: phasei ← idle 5: repliesi ← ∅

▷ Whether pi is idle or has an ongoing invocation. ▷ Set of ⟨sender index, reply value⟩ received for pi ’s ongoing invocation.

6: upon invocation of next() do 7: repliesi ← ∅ 8: 9:

phasei ← ongoing send ⟨Req seqi , xi ⟩ to every process except pi

10: upon receive ⟨Req q, v⟩ from pj do 11: if q > reqSeqi [j] then 12: reqSeqi [j] ← q 13: 14:

xi ← max(xi , v) + 1 send ⟨Reply q, xi ⟩ to pj

15: upon receive ⟨Reply q, v⟩ from pj do 16: if phasei = ongoing and q = seqi then 17: repliesi ← repliesi ∪ {⟨j, v⟩} 18: if |repliesi | = n − 2 then 19: t ← max{v ′ : ⟨j ′ , v ′ ⟩ ∈ repliesi } 20: xi ← max(xi , t) 21: 22: 23:

▷ Base timestamp.

phasei ← idle seqi ← seqi + 1 return n · t + i

▷ Completes the next() invocation.

8

Claim 4.5. Let h be an integer, and suppose that when a process pi invokes next(), there are distinct processes pj and pk such that xj ≥ h and xk ≥ h. Then, if the invocation completes, its base timestamp t satisfies t > h. Proof. Let vi be the value of xi included in the Req message that pi sends for this invocation on line 9. When pi computes t on line 19, write R = {j : ⟨j, −⟩ ∈ repliesi }. As argued in the proof of Claim 4.4, |R| = n − 2 and i ∈ / R. If i ∈ {j, k}, then vi ≥ h by assumption and monotonicity (Claim 4.3). For each ℓ ∈ R, line 13 makes pℓ ’s reply value at least vi + 1 > h. Since t is the maximum of these reply values (line 19), we have t > h. Otherwise, i ∈ / {j, k}. Because |R| = n − 2 and i ∈ / R, the set R omits only one of the n − 1 indices other than i; hence j ∈ R or k ∈ R. Without loss of generality, assume j ∈ R. By Claim 4.3, xj ≥ h when pj receives the Req message from pi . Line 13 therefore makes pj ’s reply value greater than h. This value is among those whose maximum is t (line 19), so t > h. Claim 4.5 Claim 4.6 (Ordering for base timestamps). Suppose two next() operations compute base timestamps t and t′ on line 19, respectively. If the first returns before the second is invoked, then t < t′ . Proof. By Claim 4.4, when the first operation returns, there exist distinct processes pj and pk such that xj ≥ t and xk ≥ t. By Claim 4.3, both inequalities still hold when the second operation is invoked. Applying Claim 4.5 with h = t therefore shows that the second operation has base timestamp t′ > t. Claim 4.6 Claim 4.7 (Return values). Algorithm 1 returns positive integers from next() and satisfies ordering (CT1a) and uniqueness (CT1b). Proof. Local clocks xi start at 0 and never decrease (Claim 4.3), so by line 13, every value sent in a Reply message is a positive integer. Hence, every base timestamp t is a positive integer, and so is n · t + i. For (CT1a), suppose a complete operation at pi with base timestamp t precedes one at pj with base timestamp t′ . By Claim 4.6, t < t′ , so n · t + i < n · (t + 1) ≤ n · t′ + j. For (CT1b), timestamps returned by different processes differ modulo n, and those returned by the same process are distinct by (CT1a) since its operations are sequential. Claim 4.7 Claim 4.8 (Liveness). In Algorithm 1, every invocation by a correct process eventually returns. Proof. Let pi be a correct process that invokes next(). Line 9 sends a Req message to each of the other n−1 processes, at least n − 2 of which are correct. Each correct recipient eventually receives this fresh request, passes the check on line 11, and sends a Reply on line 14, which pi eventually receives. Thus line 17 eventually makes |repliesi | = n − 2, causing pi to pass the check on line 18 and return on line 23. Claim 4.8 Claim 4.9 (Latency). The worst-case message delay of Algorithm 1 is two. Proof sketch. An invocation follows one Req delay and one Reply delay, as illustrated below: Req

Reply

return

invoke next()

Claim 4.9

By Claims 4.7 and 4.8, Algorithm 1 satisfies the conditions of Proposition 3.3 and hence implements TS. By Claim 4.9, its worst-case message delay is two. Theorem 4.2

9

4.2.2

Three-Delay Algorithm for General f

In the general case, TS can be implemented in three message delays. Theorem 4.10. In a system with crash failures, if n > 2f , then there exists an implementation of TS (Algorithm 2) whose worst-case message delay is three. Proof. The algorithm adopts the “max-min technique” [DGLC04, Section 1.1] previously used to achieve worst-case three-delay reads for SWMR and MWMR atomic registers in message-passing systems [HNS17]. We first establish some supporting properties of the algorithm. We then show that the algorithm implements TS by proving that it returns positive integers and satisfies ordering (CT1a), uniqueness (CT1b), and liveness (CT2). Finally, we show that its worst-case message delay is three. Claim 4.11. For every process pi , its local clock xi is non-decreasing. Proof. After initialization, the only assignment to xi is on line 24, which cannot decrease xi .

Claim 4.11

Claim 4.12. For all processes pi and pj and every sequence number q, process pj sends at most one ⟨Prop ⟨i, q⟩, −⟩ message to each process and at most one ⟨Reply q, −⟩ message to pi . Proof. Process pj sends ⟨Prop ⟨i, q⟩, −⟩ on line 15 only upon receiving ⟨Req q⟩ from pi with q > reqSeqj [i], and it sets reqSeqj [i] ← q on line 14 before sending. As line 14 is the only assignment to reqSeqj [i] and never decreases it, the test q > reqSeqj [i] fails thereafter, so pj sends no further Prop message for ⟨i, q⟩. Process pj sends ⟨Reply q, −⟩ to pi on line 25 only when an insertion on line 21 brings |propsj [i]| to n − f while propSeqj [i] = q. Thereafter, the test on line 20 fails for every later ⟨Prop ⟨i, q⟩, −⟩ message received, so no further insertion—and hence no further reply—occurs while propSeqj [i] = q. Moreover, any later assignment to propSeqj [i] occurs on line 18, where it can only increase the value past q, so propSeqj [i] never equals q again. Claim 4.12 Claim 4.13. If an invocation of next() computes base timestamp t on line 30, then at the time of return, at least n − f processes pj satisfy xj ≥ t. Proof. Let pi be the process performing the invocation, and consider the time when pi executes line 30 before returning. Write R = {j : ⟨j, −⟩ ∈ repliesi }. Line 30 is reached only when |repliesi | = n − f (line 29). Every pair in repliesi comes from a Reply message with sequence number seqi , and by Claim 4.12 each process sends at most one such message to pi , so we have |R| = n − f . Fix an index j ∈ R, and let vj be the value with ⟨j, vj ⟩ ∈ repliesi . By line 30, t ≤ vj . Process pj had xj = vj when it sent this reply on line 25, so by Claim 4.11, xj ≥ vj ≥ t still holds when pi returns. As j ∈ R was arbitrary and |R| = n − f , the claim follows. Claim 4.13 Claim 4.14. Let h be an integer, and suppose that when a process pi invokes next(), at least n − f processes pk have xk ≥ h. Then, if the invocation completes, its base timestamp t satisfies t > h. Proof. Let A be a set of n − f indices such that xk ≥ h for every k ∈ A when the invocation begins. When pi executes line 30, write R = {j : ⟨j, −⟩ ∈ repliesi }. Fix an index j ∈ R, and let vj be the value with ⟨j, vj ⟩ ∈ repliesi . Before pj sends this reply on line 25, |propsj [i]| = n − f (line 22); by Claim 4.12, the pairs in propsj [i] carry distinct indices, so pj received Prop messages for this invocation from a set Pj of n − f process indices. Since |A|, |Pj | ≥ n − f and n > 2f , we have |A ∩ Pj | > 0. Fix some k ∈ A ∩ Pj . As k ∈ A, we have xk ≥ h when pi invoked next(). Process pk sent its Prop message on line 15 upon receiving pi ’s Req message from line 11, hence after the invocation began, so Claim 4.11 implies that its proposal value wk satisfies wk ≥ h. As k ∈ Pj , we have ⟨k, wk ⟩ ∈ propsj [i], so vmax ≥ wk ≥ h when pj executes line 24. After that line, we have xj ≥ vmax + 1 > h, and pj sends this value of xj as vj on line 25, so vj > h. Since j ∈ R was arbitrary, line 30 yields t = min{vj : j ∈ R} > h. Claim 4.14

10

Algorithm 2 A worst-case three-delay implementation of TS in a system with crash failures where n > 2f . Code for process pi (0 ≤ i < n): 1: xi ← 0 ▷ pi ’s local clock. 2: seqi ← 0 ▷ Sequence number of pi ’s ongoing invocation, or of its next invocation when idle. 3: reqSeqi [k] ← −1 for each k ▷ Largest q in a ⟨Req q⟩ received from pk . 4: propSeqi [k] ← −1 for each k ▷ Largest q in a received ⟨Prop ⟨k, q⟩, −⟩. 5: propsi [k] ← ∅ for each k

▷ Set of ⟨sender index, proposal value⟩ received for sequence number propSeqi [k] of pk . 6: phasei ← idle 7: repliesi ← ∅

▷ Whether pi is idle or has an ongoing invocation. ▷ Set of ⟨sender index, reply value⟩ received for pi ’s ongoing invocation.

8: upon invocation of next() do 9: repliesi ← ∅ 10: phasei ← ongoing 11: send ⟨Req seqi ⟩ to every process 12: upon receive ⟨Req q⟩ from pk do 13: if q > reqSeqi [k] then 14: reqSeqi [k] ← q 15: send ⟨Prop ⟨k, q⟩, xi ⟩ to every process 16: upon receive ⟨Prop ⟨k, q⟩, v⟩ from pj do 17: if q > propSeqi [k] then 18: propSeqi [k] ← q 19: 20: 21: 22: 23: 24: 25:

propsi [k] ← ∅ if q = propSeqi [k] and |propsi [k]| < n − f then propsi [k] ← propsi [k] ∪ {⟨j, v⟩} if |propsi [k]| = n − f then vmax ← max{v ′ : ⟨j ′ , v ′ ⟩ ∈ propsi [k]} xi ← max(xi , vmax ) + 1 send ⟨Reply q, xi ⟩ to pk

26: upon receive ⟨Reply q, v⟩ from pj do 27: if phasei = ongoing and q = seqi then 28: repliesi ← repliesi ∪ {⟨j, v⟩} 29: if |repliesi | = n − f then 30: t ← min{v ′ : ⟨j ′ , v ′ ⟩ ∈ repliesi } 31: phasei ← idle 32: 33:

▷ Base timestamp.

seqi ← seqi + 1 return n · t + i

▷ Completes the next() invocation.

11

Claim 4.15 (Ordering for base timestamps). Suppose two next() operations compute base timestamps t and t′ on line 30, respectively. If the first returns before the second is invoked, then t < t′ . Proof. By Claim 4.13, when the first operation returns, at least n − f processes pj satisfy xj ≥ t. By Claim 4.11, these inequalities still hold when the second operation is invoked. Applying Claim 4.14 with h = t therefore shows that the second operation has base timestamp t′ > t. Claim 4.15 Claim 4.16 (Return values). Algorithm 2 returns positive integers from next() and satisfies ordering (CT1a) and uniqueness (CT1b). Proof. Local clocks xi start at 0 and never decrease (Claim 4.11), so by line 24, every value sent in a Reply message is a positive integer. Hence, every base timestamp t is a positive integer, and so is n · t + i. For (CT1a), suppose a complete operation at pi with base timestamp t precedes one at pj with base timestamp t′ . By Claim 4.15, t < t′ , so n · t + i < n · (t + 1) ≤ n · t′ + j. For (CT1b), timestamps returned by different processes differ modulo n, and those returned by the same process are distinct by (CT1a) since its operations are sequential. Claim 4.16 Claim 4.17 (Liveness). In Algorithm 2, every invocation by a correct process eventually returns. Proof. Let pi be a correct process that invokes next(), and let q be the value of seqi during this invocation. Line 11 sends ⟨Req q⟩ to every process, at least n − f of which are correct. Each correct recipient eventually receives this fresh request, passes the check on line 13, and sends ⟨Prop ⟨i, q⟩, −⟩ to every process on line 15. Since pi sends no request with a higher sequence number before this invocation returns, each correct process pj eventually receives these Prop messages from at least n − f distinct processes while propSeqj [i] = q. Thus line 21 eventually makes |propsj [i]| = n − f , causing pj to pass the check on line 22 and send a Reply to pi on line 25, which pi eventually receives. Hence, line 28 eventually makes |repliesi | = n − f , causing pi to pass the check on line 29 and return on line 33. Claim 4.17 Claim 4.18 (Latency). The worst-case message delay of Algorithm 2 is three. Proof sketch. An invocation follows one Req delay, one Prop delay, and one Reply delay, as illustrated below: Req

Prop

Reply

return

invoke next()

Claim 4.18

By Claims 4.16 and 4.17, Algorithm 2 satisfies the conditions of Proposition 3.3 and hence implements TS. By Claim 4.18, its worst-case message delay is three. Theorem 4.10

4.3

Latency Lower Bounds

We now turn to lower bounds on the worst-case message delay of implementing TS under crash failures. 4.3.1

Auxiliary Lemmas

Definition 4.19 (Loquacious algorithm). An algorithm is loquacious if every step sends the same message to every process in the system (including the sender itself). We say that such a step broadcasts that message. The lower-bound proofs will use two auxiliary lemmas. The first provides a transformation from arbitrary implementations of TS to loquacious ones. Lemma 4.20. In a system with crash failures, let A be an implementation of TS. Then there exists a loquacious implementation A′ of TS such that δ(A′ ) ≤ δ(A). 12

Since this transformation does not increase worst-case message delay, any latency lower bound for loquacious implementations of TS also holds for arbitrary implementations of TS in the same system. We defer the proof of this lemma to Appendix C.1.1. The second auxiliary lemma concerns completion in two-delay algorithms. Intuitively, an algorithm with worst-case message delay at most two must return from an operation once its invoker completes a round trip with n − f processes. The invoker cannot wait for the remaining f processes, which may have crashed, or for another communication step, which would require a third message delay. The following lemma makes this intuition precise. Lemma 4.21. In a system with crash failures, let A be a loquacious algorithm with δ(A) ≤ 2. Let p be a process, and let Q be a set of processes such that |Q| = n − f and p ∈ Q. Suppose that σ is a schedule prefix of A in which the following hold: 1. Process p invokes an operation and broadcasts a message m in step σ[a]. 2. For each q ∈ Q, process q receives message m and broadcasts a message mq in step σ[jq ]. 3. Process p receives the set of messages {mq : q ∈ Q} in step σ[b]. 4. Between steps σ[a] and σ[b], inclusive, the only steps are those specified above. Then the operation invoked by p in step σ[a] returns no later than step σ[b]. We defer the proof of this lemma to Appendix C.3.1. 4.3.2

The Bounds

The first lower bound is intuitively clear: A process invoking next() cannot safely return before completing at least one round trip with another process, which requires at least two message delays. Proposition 4.22. In a system with crash failures, any implementation of TS has worst-case message delay at least two. Making this intuition precise requires some technical care; we defer the proof to Appendix D. We now show that implementing TS requires at least three message delays when two or more processes may crash. Our proof uses a novel cyclic chain argument: a chain of indistinguishable schedules that closes on itself, forcing the returned timestamps to increase strictly around a cycle. Theorem 4.23. In a system with crash failures, if f ≥ 2, then any implementation of TS has worst-case message delay at least three. Proof. Consider a system with n processes, of which at most f ≥ 2 may crash. Suppose, toward a contradiction, that there is an implementation of TS whose worst-case message delay is less than three. By Lemma 4.20, there is a loquacious implementation A of TS with δ(A) < 3. Since finite worst-case message delays are integers (Proposition 2.8), δ(A) ≤ 2. By Proposition 3.3, A satisfies ordering (CT1a). Finally, by Proposition 4.1, n > 2f . We name the processes p0 , p1 , . . . , pn−1 , with process indices taken from the cyclic group Zn . So arithmetic on process indices is modulo n. For i, j ∈ Zn , we write i, i + 1, . . . , j for the inclusive cyclic range obtained by starting at i and repeatedly adding one until j is first reached (in particular, when i = j, this range is simply i).

13

Phase 1

Phase 2

Phase 3 b0

p0 H0 = {p2 , p3 , p4 }

p1 p2 p3

D10 = ∅ D20 = ∅ m00

D30 = {p1 }

p4

D40 = {p1 , p2 }

p5

m b 04,0

a0 H5 = {p1 , p2 , p3 }

Schedule prefix σ 0 a1

p0 H0 = {p2 , p3 , p4 }

p1

b1 H1 = {p3 , p4 , p5 }

p2 p3 p4

D21 = ∅ m b 14,0

m10

D31 = ∅ D41 = {p2 }

p5

D51 = {p2 , p3 }

Schedule prefix σ 1

.. . p0 p1 p2 p3 p4 p5

D05 = ∅ D15 = ∅ D25 = {p0 } D35 = {p0 , p1 }

a5 H4 = {p0 , p1 , p2 }

b5 H5 = {p1 , p2 , p3 }

Schedule prefix σ

5

Figure 1: Proof of Theorem 4.23. In a system with crash failures where f ≥ 2, suppose toward a contradiction that some loquacious implementation A of TS has δ(A) ≤ 2. For n = 6 and f = 2, the figure shows σ 0 , σ 1 , and σ 5 . Each dot marks a step and is colored by the invocation it serves, while each arrow marks shows a message received within the prefix. A horizontal segment tracks a next() operation: its invocation step, and labeled r indicates that it has returned r by that step. Without a return marker, the figure makes no claim about whether the operation returns within the prefix. Condition (CT1a) gives ai < bi . Furthermore, σ i and σ i+1 are indistinguishable to pi through the return of its operation, so bi = ai+1 . Together, these relations yield the contradiction a0 < a1 < · · · < a5 < a0 .

14

Roadmap. For each i ∈ Zn , we will construct a schedule prefix σ i of A as follows (Figure 1 illustrates the construction for n = 6, f = 2): • For j = i + 1, i + 2, . . . , i − 2, process pj invokes next(); the message broadcast by its invocation step is then received by the processes in some receiver set Dji . • Process pi−1 invokes next(), completes a round trip of communication with itself and some set Hi−1 of helper processes, and returns value ai . • Process pi invokes next(), completes a round trip with itself and the helper processes in Hi , and returns value bi . Each σ i can be extended to a schedule of A in which pi−1 returns before pi invokes, so condition (CT1a) implies ai < bi for each i ∈ Zn . The key to the argument will be to choose the sets Dji and Hi such that σ i and σ i+1 are indistinguishable to process pi for each i ∈ Zn . Consequently, pi returns the same value from its operation in σ i and σ i+1 , and so ai+1 = bi for each i ∈ Zn . Thus ai < ai+1 for every i ∈ Zn . Chaining these inequalities around the cycle yields a0 < a1 < · · · < an−1 < a0 , a contradiction. We now give the full proof following this roadmap, starting by defining the sets Hi and Dji . Helper and receiver sets.

For each i ∈ Zn , define the helper set ∆

Hi = {pi+2 , pi+3 , . . . , pi−f }. By construction, |Hi | = n − f − 1. Moreover, since n > 2f and f ≥ 2, pi−1 , pi , pi+1 ∈ / Hi .

(1)

For i ∈ Zn and j ∈ {i + 1, i + 2, . . . , i − 2}, define the receiver set ∆

Dji = Hj ∩ Hj+1 ∩ · · · ∩ Hi−1 .

(2)

For each fixed i ∈ Zn , these sets are nested as their indices advance toward i − 1 in cyclic order: i i i Di+1 ⊆ Di+2 ⊆ · · · ⊆ Di−2 ⊆ Hi−1 .

(3)

Unwinding the definitions, for every pk ∈ Hi−1 and x ∈ {i + 1, i + 2, . . . , i − 2}, pk ∈ Dxi ⇐⇒ x ∈ {k + f, k + f + 1, . . . , i − 1}.

(4)

Constructing the schedule prefixes. Fix i ∈ Zn . We construct σ i in three phases, listing the steps taken in each phase. For each step, we specify the process that takes it, the operation it invokes, if any, and the messages it receives; the algorithm A then determines the message the step broadcasts, whether the step returns from an operation, and, if so, the return value. Any message whose receipt we do not specify is not received during σ i . Since A is loquacious, every step broadcasts a message, but we name only those messages relevant to the proof. If we do not state whether a step returns from an operation, then it is irrelevant to the proof whether it does. The three phases of σ i are as follows. Phase 1: background invocations. For j = i + 1, i + 2, . . . , i − 2, in that cyclic order:

15

(a) process pj takes a step that receives no messages and invokes next(), broadcasting a message mij ; and then (b) the processes in Dji (in any order) each take a step that receives mij . Phase 2: a complete operation by pi−1 . (a) process pi−1 takes a step that receives no messages and invokes next(), broadcasting a message mii−1 ; (b) each process pk ∈ Hi−1 ∪ {pi−1 } (in any order) takes a step that receives mii−1 , broadcasting a message m b ik,i−1 ; and then (c) process pi−1 takes a step that receives the set of messages {m b ik,i−1 : pk ∈ Hi−1 ∪ {pi−1 }} broadcast above. By Lemma 4.21 (with p = pi−1 and Q = Hi−1 ∪ {pi−1 }), the operation invoked by pi−1 in step 2a has returned by this point; denote its return value by ai . Phase 3: a complete operation by pi , repeating phase 2 with pi in place of pi−1 and Hi in place of Hi−1 : (a) process pi takes a step that receives no messages and invokes next(), broadcasting a message mii ; (b) each process pk ∈ Hi ∪ {pi } (in any order) takes a step that receives mii , broadcasting a message m b ik,i ; and then (c) process pi takes a step that receives the set of messages {m b ik,i : pk ∈ Hi ∪ {pi }} broadcast above. By Lemma 4.21 (with p = pi and Q = Hi ∪ {pi }), the operation invoked by pi in step 3a has returned by this point; denote its return value by bi . By construction, each process invokes only one operation, receives only messages broadcast in an earlier step, and receives each message at most once. Thus, σ i is a schedule prefix of A. We call the steps specified in 1a, 2a, and 3a invocation steps, and all other steps of σ i receive steps. Return-value order within each prefix. As previewed in the roadmap, we first use condition (CT1a) to order the return values of the two complete operations in each prefix. Claim 4.24. For every i ∈ Zn , ai < bi . Proof. Fix i ∈ Zn . Extend σ i to a schedule of A. Both operations are complete and pi−1 ’s operation returns before pi ’s operation is invoked. The claim follows from condition (CT1a). Claim 4.24 Return-value equality across consecutive prefixes. Next, we establish several auxiliary claims about the steps taken by processes in the schedule prefixes. We then use these claims to show that two complete operations by the same process in consecutive prefixes return the same value. Claim 4.25. For every i, j ∈ Zn , process pj ’s invocation step is its first step in σ i . Consequently, ′

mij = mij

for all i, i′ , j ∈ Zn .

Proof. Fix i, j ∈ Zn . In σ i , the invocation steps occur in the cyclic order pi+1 , pi+2 , . . . , pi−2 , pi−1 , pi . Suppose first that j ̸= i. Before pj invokes, every step in σ i is either an invocation step by a process px preceding pj in the order above, or a receive step taken by a process in Dxi for such an x. Since px precedes pj in the invocation order, (2) gives Dxi ⊆ Hj . Since pj ∈ / Hj by (1), none of these steps is taken by pj . 16

Now suppose that j = i. Every invocation step preceding pi ’s invocation is taken by some px with x ̸= i. Every preceding receive step is taken either by a process in Dxi ⊆ Hi−1 during phase 1, where the inclusion follows from (3), or by a process in Hi−1 ∪ {pi−1 } during phase 2. Since pi ∈ / Hi−1 by (1) and pi ̸= pi−1 , none of these steps is taken by pi . Thus, pj ’s invocation step is taken from its initial state in every prefix. These steps invoke the same ′ operation next() and receive no messages, so they must broadcast the same message. Therefore, mij = mij ′ for all i, i , j ∈ Zn . Claim 4.25 For each j ∈ Zn , denote by mj the message mij , which is the same for every i ∈ Zn . Claim 4.26. For every i ∈ Zn and pk ∈ Hi , in σ i the steps taken by pk through its receipt of mi consist of pk ’s invocation step followed, in order, by one receive step for each message in the sequence mk+f , mk+f +1 , . . . , mi .

(5)

Proof. Fix i ∈ Zn and pk ∈ Hi , and consider the prefix σ i . By (1), pk ∈ / {pi−1 , pi }, so pk invokes during phase 1. We distinguish two cases according to whether pk ∈ Hi−1 : • If pk ∈ Hi−1 , then (4) and the construction of phase 2 imply that, after invoking, pk receives mk+f , mk+f +1 , . . . , mi−1 in that order during phases 1 and 2. It then receives mi during phase 3, completing the sequence in (5). • If pk ∈ / Hi−1 , then pk ∈ Hi \ Hi−1 , which implies k + f = i. Thus the sequence in (5) consists only of mi . By (3), no receiver set used in phase 1 contains pk , so it receives no messages in that phase. Moreover, pk ∈ / Hi−1 ∪ {pi−1 }, so it does not receive mi−1 in phase 2 either. Hence pk takes no receive step before receiving mi in phase 3, as claimed. Claim 4.26 Claim 4.27. For every i ∈ Zn and pk ∈ Hi , in σ i+1 the steps taken by pk through its receipt of mi consist of pk ’s invocation step followed, in order, by one receive step for each message in the sequence (5). Proof. Fix i ∈ Zn and pk ∈ Hi , and consider the prefix σ i+1 . By (1), pk ∈ / {pi , pi+1 }, so pk takes its invocation step during phase 1. In σ i+1 , (4) implies that during phase 1 process pk receives, in order, exactly those messages in (5) that precede mi , each in a separate receive step. During phase 2, it receives mi in one more receive step because pk ∈ Hi . These are precisely the steps stated in the claim. Claim 4.27 Claim 4.28. For every i ∈ Zn and pk ∈ Hi ∪ {pi }, m b ik,i = m b i+1 k,i . Proof. Fix i ∈ Zn and pk ∈ Hi ∪ {pi }. By (1), pi ∈ / Hi , so exactly one of the following cases holds: • If pk ∈ Hi , then by Claims 4.26 and 4.27, pk takes the same sequence of steps in σ i and σ i+1 through i+1 its receive step for mi . This step broadcasts m b ik,i in σ i and m b i+1 , so m b ik,i = m b i+1 k,i in σ k,i . • If pk = pi , then Claim 4.25 implies that its first step in both σ i and σ i+1 is its invocation step, which broadcasts mi in each. By construction, its next step in each prefix is a receive step for mi . These receive steps are therefore identical, so m b ii,i = m b i+1 Claim 4.28 i,i . For each i ∈ Zn and pk ∈ Hi ∪ {pi }, we denote by m b k,i the message m b ik,i = m b i+1 k,i . Claim 4.29. For every i ∈ Zn , bi = ai+1 . Proof. Fix i ∈ Zn , and compare the steps of pi in σ i and σ i+1 , which belong to phase 3 of the former and phase 2 of the latter. In both prefixes, pi takes exactly three steps up to and including the last step of its round trip: 1. pi invokes next() and broadcasts mi ; 17

2. pi receives mi and broadcasts m b i,i ; and 3. pi receives all messages m b k,i for pk ∈ Hi ∪ {pi }. By Claim 4.25, pi ’s invocation is its first step in both prefixes and broadcasts the same message mi . By construction, its next step in each prefix receives mi , so steps 1 and 2 agree in the two prefixes. By Claim 4.28, pi receives the same set of messages in step 3, so this step agrees as well. By Lemma 4.21, pi ’s operation returns by this step in each prefix. It therefore returns at the same step and with the same value in both prefixes. This value is bi in σ i and ai+1 in σ i+1 , so bi = ai+1 . Claim 4.29 Contradiction. By Claims 4.24 and 4.29, ai < bi = ai+1 for every i ∈ Zn . Chaining these inequalities around the cycle gives a0 < a1 < · · · < an−1 < a0 , a contradiction. Thus every implementation of TS has worst-case message delay at least three.

4.4

Theorem 4.23

Summary

Proposition 4.1 and Theorem 4.10 together give the following necessary and sufficient condition for implementing TS under crash failures. Corollary 4.30. In a system with crash failures, there exists an implementation of TS if and only if n > 2f . We next state the optimal latency for implementations of TS under crash failures. When n > 2f and f ≥ 2, the latency upper bound in Theorem 4.10 matches the lower bound in Theorem 4.23, yielding the following. Corollary 4.31. In a system with crash failures, if n > 2f and f ≥ 2, then the optimal latency of implementing TS is three message delays. When n > 2f and f = 1, the latency upper bound in Theorem 4.2 matches the lower bound in Proposition 4.22, yielding the following. Corollary 4.32. In a system with crash failures, if n > 2f and f = 1, then the optimal latency of implementing TS is two message delays. Thus, the optimal latency of implementing TS under crash failures is settled in all cases where an implementation exists.

5

Adapting to Byzantine Failures

We now adapt the system model and latency measure (Section 2) and the implementation requirements for TS (Section 3) to systems with Byzantine processes. These adaptations apply in both settings we consider: with digital signatures (Section 6) and without them (Section 7).

5.1

System Model and Latency

We continue to assume n ≥ 2 processes and 1 ≤ f < n. The definitions of processes, the message-passing model, and algorithms are unchanged; only the definition of a schedule changes. In a system with Byzantine processes, a schedule S of algorithm A is an infinite sequence of steps in which at least n − f processes take infinitely many steps, all according to A; these processes are correct in S. Every other process is faulty—it may crash, deviate arbitrarily from A, or both. The message-delivery requirements on a schedule are unchanged. Under these revised notions of schedules and correct processes, the remaining definitions in Section 2.1 and the latency definitions in Section 2.2 carry over verbatim. The two consequences of finite worst-case 18

message delay, Propositions 2.7 and 2.8, also carry over. (Their proofs in Appendix B apply equally under crash and Byzantine failures.) In the setting with digital signatures (Section 6), no process can forge the signature of a correct process, and any process can relay a signed message and verify its signature. Remark 5.1. The eventual-delivery requirement in Section 2.1 and the definition of message timeliness in Definition 2.5 cover messages sent to any process that “takes infinitely many steps,” even if that process is Byzantine. This is natural because both constrain network behavior, not process behavior: The network does not deliver a message any less reliably or promptly merely because its recipient deviates from A. In particular, if a Byzantine process q takes infinitely many steps, every message m sent to q is eventually delivered. However, q may handle the delivered message arbitrarily: It may act as if it had not received m or as if it had received a different message m′ ̸= m.

5.2

Implementations of the Timestamp Object

To adapt Definition 3.2 (implementation of TS) to Byzantine failures, we replace crash linearizability with Byzantine linearizability [CK21, Section 4]. Intuitively, the history H of a schedule S is Byzantine linearizable b such that (1) the projection of H b onto the correct processes with respect to TS if there exists a history H b in S is the same as that of H, and (2) H is crash linearizable with respect to TS. In other words, H can be made crash linearizable with respect to TS by adding, omitting, or modifying operations of processes that are faulty in S. Below, we underline the changes for Byzantine failures. Definition 5.2 (TS implementation under Byzantine failures). Let A be an algorithm whose next() operation returns positive integers. We say that A implements TS in a system with Byzantine processes if every schedule S of A, with corresponding history H, satisfies the following conditions: (BT1) Safety: H is Byzantine linearizable with respect to TS. (BT2) Liveness: Every operation invoked by a correct process in S eventually returns. The following analogue of Proposition 3.3 characterizes TS implementations under Byzantine failures in terms of ordering and uniqueness for operations invoked by correct processes. Proposition 5.3 (Characterization of TS implementations under Byzantine failures). Let A be an algorithm whose next() operation returns positive integers. Then A implements TS in a system with Byzantine processes if and only if every schedule S of A, with corresponding history H, satisfies the following conditions: (BT1a) Ordering: If a complete operation O1 precedes a complete operation O2 in H, where both are invoked by correct processes in S, then O1 returns a smaller value than O2 . (BT1b) Uniqueness: No two distinct complete operations in H invoked by correct processes in S return the same value. (BT2) Liveness: Every operation invoked by a correct process in S eventually returns. Proof. The liveness condition (BT2) is the same in Definition 5.2 and the proposition. It therefore suffices to show that, for every schedule S of A with corresponding history H, (BT1) ⇐⇒ (BT1a) ∧ (BT1b). Each direction reuses the corresponding claim from the proof for systems with crash failures (Proposition 3.3). b (=⇒) Suppose that H is Byzantine linearizable with respect to TS (BT1). Then there exists a history H that is crash linearizable with respect to TS (CT1) and whose projection onto the correct processes in S b satisfies (CT1a) and (CT1b). Since H and H b have the same is the same as that of H. By Claim 3.4, H projection onto the correct processes in S, complete operations invoked by correct processes have the same return values and precedence in the two histories. Hence, H satisfies (BT1a) and (BT1b). (⇐=) Suppose that H satisfies (BT1a) and (BT1b). Let HC denote the projection of H onto the correct processes in S. Then HC satisfies (CT1a) and (CT1b). Moreover, because correct processes follow A, every complete operation in HC returns a positive integer. Hence, by Claim 3.5, HC is crash linearizable with respect to TS (CT1), which makes H Byzantine linearizable with respect to TS (BT1). Proposition 5.3 19

6

Results for Byzantine Failures with Digital Signatures

In this section, we consider implementations of TS in systems with Byzantine processes and digital signatures. Recall that we assume there are n ≥ 2 processes, of which at most f ≥ 1 may be Byzantine.

6.1

Maximum Resilience

Proposition 6.1. In a system with Byzantine processes and digital signatures, there exists an implementation of TS only if n > 3f . Proof. Suppose, toward a contradiction, that an implementation A of TS exists in such a system. By Proposition 5.3, A satisfies ordering (BT1a). Because 2 ≤ n ≤ 3f , we can choose pairwise disjoint sets A, B, C whose union is the set of processes, such that |A|, |B|, |C| ≤ f and A, C ̸= ∅. Fix processes pa ∈ A and pc ∈ C. Consider a schedule of A in which the processes in C crash before taking any steps (where |C| ≤ f ), the processes in A ∪ B are correct, and pa invokes next(). By liveness, this operation eventually returns some value ra . Let σA be the schedule prefix of A ending at its return; thus, σA contains no steps by processes in C. Symmetrically, let σC be a schedule prefix of A in which pc invokes next() and returns rc and processes in A take no steps (where |A| ≤ f ). Without loss of generality, assume ra ≥ rc . Now consider the concatenation σA ◦ σC . It extends to a schedule of A in which the processes in B are Byzantine (where |B| ≤ f ) and those in A ∪ C are correct. The processes in B first reproduce their steps in σA , and then “roll back” to their initial states and reproduce their steps in σC ; digital signatures do not prevent a Byzantine process from resetting its own state. The messages sent to C during σA and to A during σC are delayed until after both operations return, so that the processes in A ∪ C follow A throughout. Since pa , pc ∈ A ∪ C are correct and pa ’s operation returns before pc ’s operation is invoked, condition (BT1a) implies ra < rc , a contradiction. Proposition 6.1

6.2

Latency Upper Bounds

When n > 3f , TS can be implemented with a worst-case message delay of three. In fact, Theorem 7.2, proved in Section 7.2, gives such an implementation without digital signatures. Since it also works in systems with digital signatures, we immediately obtain the following. Observation 6.2. In a system with Byzantine processes and digital signatures, if n > 3f , then there exists an implementation of TS whose worst-case message delay is three. For the special case f = 1, TS can be implemented with only two message delays using digital signatures. Theorem 6.3. In a system with Byzantine processes and digital signatures, if n > 3f and f = 1, then there exists an implementation of TS (Algorithm 3) whose worst-case message delay is two. Proof. We prove the theorem in five parts. Parts 1 and 2 introduce the necessary definitions and present the algorithm. Part 3 establishes preliminary properties, which we use in Part 4 to prove that next() returns positive integers and satisfies ordering and uniqueness (Proposition 6.38). Finally, Part 5 proves liveness (Proposition 6.39) and shows that the worst-case message delay is two (Proposition 6.40). Part 1. Definitions. We start by defining some concepts used in the algorithm. We name the processes p0 , . . . , pn−1 . The notation ⟨m⟩σi denotes statement m carrying a digital signature by process pi . Definition 6.4. A label by process pi has the form ℓ = ⟨Label i, k, r⟩σi , We write

20

k, r ∈ Z≥1 .

• origin(ℓ) = i for the origin of ℓ, ∆

• seq(ℓ) = k for its sequence number, ∆

• rank(ℓ) = r for its rank. ∆

Successive invocations by a correct process pi are identified by labels of origin i with consecutive sequence numbers. Definition 6.5. An acknowledgment of label ℓ by process pi is ⟨ℓ⟩σi . Definition 6.6. A quorum certificate for label ℓ is a set of acknowledgments C = {⟨ℓ⟩σi : i ∈ Q} where Q ⊆ {0, . . . , n − 1} and |Q| = n − 1. A quorum certificate for ℓ contains acknowledgments from n − 1 distinct processes. Since at most one process is Byzantine, it proves that at least n − 2 correct processes have handled a request carrying label ℓ. Definition 6.7. A certified label is either ⊥ or a pair ℓb = (ℓ, C) where ℓ is a label and • if seq(ℓ) = 1, then C = ∅; • if seq(ℓ) > 1, then C is a quorum certificate for some label ℓ− such that origin(ℓ− ) = origin(ℓ) and seq(ℓ− ) = seq(ℓ) − 1. We say that ℓb contains label ℓ. For a non-⊥ certified label ℓb = (ℓ, C), define ∆

b = origin(ℓ), origin(ℓ)

∆

∆

b = rank(ℓ). rank(ℓ)

b = ℓ, label(ℓ)

∆

b = seq(ℓ), seq(ℓ) ∆

∆

Set seq(⊥) = 0 and rank(⊥) = 0. Definition 6.8 (Frontier). Let F be a sequence of n certified labels. We call F a frontier if the following conditions hold for every i = 0, . . . , n − 1: • origin(F [i]) = i whenever F [i] ̸= ⊥; • rank(F [i]) ≤ N (F ), where ∆

N (F ) =

n−1 X

seq(F [k]).

k=0 ∆

The empty frontier is ⊥n = (⊥, . . . , ⊥). Definition 6.9 (Merge). For frontiers F and G, the merge of G into F , denoted F ◁ G, is the sequence of n certified labels defined by ( G[i] if seq(G[i]) > seq(F [i]), ∆ (F ◁ G)[i] = F [i] otherwise.

21

This definition directly implies seq((F ◁ G)[i]) = max{seq(F [i]), seq(G[i])}

for every i = 0, . . . , n − 1.

Proposition 6.10. If F and G are frontiers, then F ◁ G is a frontier. ∆

Proof. Write H = F ◁ G. For each i = 0, . . . , n − 1, the certified label H[i] is either F [i] or G[i], hence is ⊥ or has origin i. Furthermore, rank(H[i]) ≤ max{rank(F [i]), rank(G[i])} ≤ max{N (F ), N (G)} (n−1 ) n−1 X X = max seq(F [k]), seq(G[k]) k=0

≤

n−1 X

(F , G are frontiers)

k=0

max{seq(F [k]), seq(G[k])}

k=0

=

n−1 X

seq(H[k])

(by the definition of ◁)

k=0

= N (H). Hence, H is a frontier.

Proposition 6.10

Definition 6.11. For frontiers F and G, we write F ⪯ G if seq(F [i]) ≤ seq(G[i])

for every i = 0, . . . , n − 1.

Proposition 6.12. Let F and G be frontiers. (a) The relation ⪯ is a preorder on frontiers.3 (b) F ⪯ F ◁ G and G ⪯ F ◁ G. (c) If F ⪯ G, then N (F ) ≤ N (G). Definition 6.13 (Messages). There are two kinds of valid messages: • A valid request from process pi has the form ⟨Req F ⟩, where F is a frontier with F [i] ̸= ⊥. • A valid reply from process pj has the form ⟨Reply ⟨ℓ⟩σj , F ⟩, where ℓ is a label and F is a frontier. Part 2. Algorithm and timestamp encoding. Algorithm 3 gives the implementation. It computes base timestamps using the two functions Ti and E from lines 1 and 2; we explain the idea behind them here. For each operation, the algorithm computes a base-timestamp triple τ of integers by applying Ti (line 25). The function Ti is defined so that the lexicographic order on triples respects the precedence of operations (proved in Part 4). Because next() must return a single positive integer, the algorithm then maps τ to a positive integer t (line 26) using the encoding E, which preserves the lexicographic order (Lemma 6.17). This integer t is the operation’s base timestamp; the invoker pi then returns n · t + i (line 28), using its index i to break ties between operations with the same base timestamp. 3 The relation ⪯ is not a partial order because it is not antisymmetric. For example, two frontiers can differ in the ranks of corresponding labels while having the same sequence number at every coordinate. They are distinct, but each is ⪯ the other.

22

Algorithm 3 A worst-case two-delay implementation of TS in a system with Byzantine processes and digital signatures where n > 3f and f = 1. Each gray tag in the right margin records how the values immediately after its line correspond to the notation in Part 3.
∆ 1: Ti (F, o) = N (F ), min{ri , ro }, 1{ri > ro } ▷ See Definition 6.14. where ri = rank(F [i]), ro = rank(F [o]) ∆

2: E((s, m, δ)) = s2 + 2m + δ

▷ See Definition 6.15.

Code for process pi (0 ≤ i < n): 3: frontieri ← ⊥n 4: labeli ← ⊥ ▷ Label for ongoing invocation, ⊥ while idle. 5: acksi ← ∅ ▷ Acknowledgments for ongoing invocation; latest label’s quorum certificate while idle. 6: upon invocation of next() do 7: 8: 9: 10: 11: 12: 13:

frontieri = Lγ

seq ← seq(frontieri [i]) + 1 rank ← N (frontieri ) + 1 ℓ ← ⟨Label i, seq, rank ⟩σi labeli ← ℓ frontieri [i] ← (ℓ, acksi ) acksi ← ∅ send ⟨Req frontieri ⟩ to every process

ℓ = ℓγ frontieri = Fγ0

14: upon receive valid ⟨Req F ⟩ from pj do 15: frontieri ← frontieri ◁ F 16: ℓ ← label(F [j]) 17: send ⟨Reply ⟨ℓ⟩σi , frontieri ⟩ to pj 18: upon receive valid ⟨Reply ⟨ℓ⟩σj , F ⟩ from pj do 19: if ℓ = labeli ̸= ⊥ and ⟨ℓ⟩σj ∈ / acksi then 20: acksi ← acksi ∪ {⟨ℓ⟩σj } 21: frontieri ← frontieri ◁ F 22: 23: 24: 25: 26: 27: 28:

if |acksi | = n − 1 then Q ← {k ∈ {0, . . . , n − 1} : ⟨ℓ⟩σk ∈ acksi } o ← the unique index in {0, . . . , n − 1} \ Q τ ← Ti (frontieri , o) t ← E(τ ) labeli ← ⊥ return n · t + i

23

F = Fγ,j

frontieri = Fγ Q = Qγ o = oγ τ = τγ ▷ Base timestamp. t = tγ ▷ Completes the next() invocation.

Definition 6.14 (Base-timestamp triple). For a frontier F and process indices i, o ∈ {0, . . . , n − 1}, the base-timestamp triple is the triple of integers defined by
∆ Ti (F, o) = N (F ), min{ri , ro }, 1{ri > ro } where ri = rank(F [i]) and ro = rank(F [o]), and where 1{P } denotes the indicator of a condition P , equal to 1 if P holds and to 0 otherwise. We compare these triples lexicographically, writing τ <lex τ ′ for the resulting strict total order. Definition 6.15 (Encoding). The encoding of a base-timestamp triple τ = (s, m, δ) is the integer ∆

E(τ ) = s2 + 2m + δ. Intuitively, a triple’s first component s confines its encoding to the interval [s2 , (s + 1)2 ). These intervals are disjoint and increasing, so the first component dominates. The remaining two components break ties within an interval. Proposition 6.16. Every base-timestamp triple τ = Ti (F, o) satisfies 2

N (F )2 ≤ E(τ ) < (N (F ) + 1) . Proof. Let ri = rank(F [i]) and ro = rank(F [o]), so that τ = (s, m, δ) with s = N (F ), m = min{ri , ro }, and δ = 1{ri > ro } ∈ {0, 1}. Because ranks are nonnegative and F is a frontier, 0 ≤ ri , ro ≤ s, and so 0 ≤ m ≤ s. If ri ≤ ro , then 2m + δ = 2ri ≤ 2s. If ri > ro , then 2m + δ = 2ro + 1 < 2(ro + 1) ≤ 2ri ≤ 2s. Thus 0 ≤ 2m + δ ≤ 2s in both cases, and therefore s2 ≤ E(τ ) = s2 + 2m + δ ≤ s2 + 2s < (s + 1)2 , which proves the claim.

Proposition 6.16 ′

Lemma 6.17 (Encoding order). For any base-timestamp triples τ and τ , τ <lex τ ′

⇐⇒

E(τ ) < E(τ ′ ).

Proof. Since <lex is a strict total order, it suffices to prove the forward implication. Suppose τ = (s, m, δ) <lex (s′ , m′ , δ ′ ) = τ ′ . If s < s′ , then s + 1 ≤ s′ and Proposition 6.16 gives E(τ ) < (s + 1)2 ≤ (s′ )2 ≤ E(τ ′ ). Otherwise s = s′ and (m, δ) <lex (m′ , δ ′ ), so 2m + δ < 2m′ + δ ′ (as m, m′ are integers and δ, δ ′ ∈ {0, 1}), and adding s2 gives E(τ ) < E(τ ′ ). Lemma 6.17 Part 3. Preliminary properties. proof.

The following are some simple invariants used throughout the safety

Proposition 6.18. The following hold at every correct process pi : (a) frontieri is a frontier and is non-decreasing under ⪯. (b) The sequence numbers and ranks of labels created by pi strictly increase with creation order. (c) Messages sent by pi on lines 13 and 17 are valid requests and valid replies, respectively. Proposition 6.18(b) immediately implies the following. Corollary 6.19. Let ℓ and ℓ′ be labels created by the same correct process. If seq(ℓ) ≥ seq(ℓ′ ), then rank(ℓ) ≥ rank(ℓ′ ). 24

Next, we state some properties of a complete operation invoked by a correct process. Throughout, we denote by γ such an operation and pi its invoker, and use the following notation (which also appears as right-margin tags in Algorithm 3): • ℓγ is the label created for γ on line 9. • Lγ is the invoker’s frontier at the start of γ (line 6). • Fγ0 is the frontier carried by γ’s request, namely the value of frontieri after line 11. • Qγ is the value of Q on line 23. • oγ is the value of o from line 24. (So Qγ = {0, . . . , n − 1} \ {oγ }.) • For j ∈ Qγ , Fγ,j is the frontier in the unique reply from pj that pi receives during γ and that passes the check on line 19. • Fγ is the value of frontieri when the check on line 22 succeeds. • τγ = Ti (Fγ , oγ ) is the base-timestamp triple computed on line 25. • tγ = E(τγ ) is the base timestamp computed on line 26. Proposition 6.20. Let pj be a correct process such that j ∈ Qγ , and let F be a frontier. If F ⪯ frontierj holds at some point before γ is invoked, then F ⪯ Fγ . Proof. Because pj is correct, Fγ,j is the value of frontierj when pj replies to γ’s request on line 17, after γ is invoked; frontier monotonicity (Proposition 6.18(a)) therefore gives F ⪯ Fγ,j . Since j ∈ Qγ , process pi receives pj ’s reply before γ completes, merging Fγ,j into frontieri on line 21, after which Fγ,j ⪯ frontieri . Frontier monotonicity preserves this until the check on line 22 succeeds, at which point frontieri = Fγ , so Fγ,j ⪯ Fγ . By the transitivity of ⪯ (Proposition 6.12(a)), we have F ⪯ Fγ . Proposition 6.20 Corollary 6.21. Let pj be a correct process with j ∈ Qγ . For any k ∈ {0, . . . , n − 1} and s ∈ Z≥0 , suppose that seq(frontierj [k]) ≥ s at some point before γ is invoked. Then seq(Fγ [k]) ≥ s. Proposition 6.22. After pi executes line 11 in invocation γ, label(frontieri [i]) = ℓγ holds until γ returns. Proof. Line 11 sets frontieri [i] to the certified label (ℓγ , acksi ), so Fγ0 [i] ̸= ⊥ and label(Fγ0 [i]) = ℓγ immediately after. Fix a point between then and γ’s return, and let F be the value of frontieri at that point. Frontier monotonicity (Proposition 6.18(a)) gives Fγ0 ⪯ F , so seq(F [i]) ≥ seq(Fγ0 [i]) = seq(ℓγ ) ≥ 1. In particular F [i] ̸= ⊥, and origin(F [i]) = i because F is a frontier. So label(F [i]) carries correct process pi ’s (unforgeable) signature and was therefore created by pi . Since labels are created only on line 9 and pi has at most one outstanding invocation, pi creates no label after ℓγ before γ returns. Every label that pi created before ℓγ has a smaller sequence number by Proposition 6.18(b), so label(F [i]) = ℓγ . Proposition 6.22 Proposition 6.23. The following equalities hold: (a) ℓγ = label(Fγ0 [i]) = label(Fγ [i]). (b) seq(ℓγ ) = seq(Fγ0 [i]) = seq(Fγ [i]). (c) rank(ℓγ ) = rank(Fγ0 [i]) = rank(Fγ [i]). (d) rank(ℓγ ) = N (Fγ0 ).

25

Proof. During the invocation of γ, line 11 sets frontieri [i] to a certified label containing ℓγ . Hence, ℓγ = label(Fγ0 [i]). Moreover, Fγ is the value of frontieri when the check on line 22 succeeds, which precedes γ’s return, so Proposition 6.22 gives label(Fγ [i]) = ℓγ . We have thus proved part (a). Applying seq and rank to part (a) immediately yields parts (b) and (c). Finally, lines 7 and 11 give Fγ0 [k] = Lγ [k]

(k ̸= i),

seq(Fγ0 [i]) = seq(Lγ [i]) + 1.

Therefore, by line 8, N (Fγ0 ) = N (Lγ ) + 1 = rank(ℓγ ), proving part (d).

Proposition 6.23

Part 4. Safety. Fix complete operations α and β, invoked by correct processes pa and pb , respectively, such that α returns before β is invoked. We first establish several relations between the two operations’ frontiers and ranks, then use them to prove that Algorithm 3 satisfies ordering (BT1a) and uniqueness (BT1b). Proposition 6.24. Fα0 ⪯ Fβ . Proof. Since |Qα | = |Qβ | = n − 1, we have |Qα ∩ Qβ | ≥ 2(n − 1) − n = n − 2 ≥ 2. Since at most one process is Byzantine, Qα ∩ Qβ contains a correct process pi . Because i ∈ Qα , process pi merges Fα0 into frontieri on line 15, before α returns. Thus Fα0 ⪯ frontieri at some point before β is invoked. Since i ∈ Qβ , Proposition 6.20 gives Fα0 ⪯ Fβ . Proposition 6.24 Proposition 6.25. seq(Fβ [a]) ≥ seq(Fα [a]) and rank(Fβ [a]) ≥ rank(Fα [a]). Proof. By Propositions 6.23 and 6.24, seq(Fβ [a]) ≥ seq(Fα0 [a]) = seq(Fα [a]) = seq(ℓα ) ≥ 1, which is the first inequality. It also implies that Fα [a], Fβ [a] ̸= ⊥, which means they contain labels that carry correct process pa ’s (unforgeable) signature, and so were created by pa . The second inequality then follows from Corollary 6.19. Proposition 6.25 Proposition 6.26. If a ∈ Qβ , then Fα ⪯ Fβ . Proof. When the check on line 22 succeeds during α, frontiera = Fα ; this point precedes β’s invocation. Since pa is correct and a ∈ Qβ , Proposition 6.20 gives Fα ⪯ Fβ . Proposition 6.26 Lemma 6.27. For any j ∈ {0, . . . , n − 1}, if seq(Fβ [j]) < seq(Fα [j]), then process pj is Byzantine and seq(Fβ [j]) ≥ seq(Fα [j]) − 1. Proof. Fix j ∈ {0, . . . , n − 1} and suppose seq(Fβ [j]) < seq(Fα [j]).

(6)

This implies seq(Fα [j]) ≥ 1; in particular, Fα [j] ̸= ⊥. We proceed by proving four claims. Claim 6.28. oβ = a. Proof. By (6), Fα ̸⪯ Fβ . The contrapositive of Proposition 6.26 therefore gives a ∈ / Qβ . By line 24, Qβ omits exactly oβ , so oβ = a and Qβ = {0, . . . , n − 1} \ {a}. Claim 6.28 Claim 6.29. j ∈ Qβ . Proof. If j = a, then Proposition 6.25 gives seq(Fβ [a]) ≥ seq(Fα [a]), contradicting (6). Hence j ̸= a, and Claim 6.28 gives j ∈ Qβ . Claim 6.29 Claim 6.30. Process pj is Byzantine.

26

Proof. Suppose for contradiction that pj is correct. Let ℓ = label(Fα [j]). Since origin(ℓ) = j, the label ℓ carries correct process pj ’s (unforgeable) signature; hence pj created ℓ on line 9. Line 11 then assigns to frontierj [j] a certified label containing ℓ. Because ℓ appears in Fα , this assignment precedes α’s return, and so it precedes β’s invocation. Immediately after the assignment, seq(frontierj [j]) = seq(ℓ) = seq(Fα [j]). Since j ∈ Qβ by Claim 6.29, Corollary 6.21 gives seq(Fβ [j]) ≥ seq(ℓ) = seq(Fα [j]), contradicting (6). Hence pj is Byzantine.

Claim 6.30

Claim 6.31. seq(Fβ [j]) ≥ seq(Fα [j]) − 1. Proof. The claim is immediate if seq(Fα [j]) = 1. Assume henceforth that seq(Fα [j]) > 1. The certified label Fα [j] carries a quorum certificate for a label ℓ− satisfying origin(ℓ− ) = j,

seq(ℓ− ) = seq(Fα [j]) − 1.

The certificate contains acknowledgments of ℓ− (of the form ⟨ℓ− ⟩σk ) from n − 1 processes, at least n − 2 of which are correct. Since Qβ omits only one process, at least n − 3 ≥ 1 of these correct processes belong to Qβ . Fix one such process pi . The quorum certificate in Fα [j] contains an acknowledgment carrying correct process pi ’s (unforgeable) signature, so pi sent that acknowledgment on line 17 before α returns. Before sending the acknowledgment, on line 15 pi merges into frontieri a frontier F with label(F [j]) = ℓ− . Immediately after, seq(frontieri [j]) ≥ seq(F [j]) = seq(ℓ− ). This holds at some point before β is invoked. Since i ∈ Qβ , Corollary 6.21 now gives seq(Fβ [j]) ≥ seq(ℓ− ) = seq(Fα [j]) − 1. Claims 6.30 and 6.31 establish the two conclusions.

Claim 6.31 Lemma 6.27

Proposition 6.32. seq(ℓβ ) > seq(Fα [b]) and rank(ℓβ ) > rank(Fα [b]). Proof. If Fα [b] = ⊥, the claim is immediate. Otherwise, label(Fα [b]) carries correct process pb ’s (unforgeable) signature, so pb created it before α returned, whereas it created ℓβ after β was invoked. Thus, ℓβ comes after label(Fα [b]) in pb ’s label-creation order and therefore has a larger sequence number and rank by Proposition 6.18(b). Proposition 6.32 Proposition 6.33. If b ∈ Qα , then rank(ℓβ ) > rank(ℓα ). Proof. By Proposition 6.23, N (Fα0 ) = rank(ℓα ). Because b ∈ Qα , process pb merges Fα0 into frontierb on line 15 upon receiving a request for α—so before α returns. Since α returns before β is invoked, frontier monotonicity (Proposition 6.18(a)) gives Fα0 ⪯ Lβ . Thus, by line 8 during β and Proposition 6.12(c), rank(ℓβ ) = N (Lβ ) + 1 ≥ N (Fα0 ) + 1 = rank(ℓα ) + 1 > rank(ℓα ). Proposition 6.33

Proposition 6.34 (Ordering for base timestamps). In Algorithm 3, if α and β are complete operations invoked by correct processes and α returns before β is invoked, then their base timestamps satisfy tβ > tα . 27

Proof. Write ∆

xα = rank(Fα [a]) = rank(ℓα ),

(“=” by Proposition 6.23)

∆

yα = rank(Fα [oα ]), ∆

xβ = rank(Fβ [b]) = rank(ℓβ ),

(“=” by Proposition 6.23)

∆

yβ = rank(Fβ [oβ ]), so that
τα = N (Fα ), min{xα , yα }, 1{xα > yα } ,
τβ = N (Fβ ), min{xβ , yβ }, 1{xβ > yβ } . Since E respects the lexicographic order of these triples (Lemma 6.17), it suffices to prove that τβ >lex τα . We prove this via three claims, each comparing one component of τα and τβ under the assumption that the preceding components are equal. Claim 6.35. N (Fβ ) ≥ N (Fα ). Proof. First, by Propositions 6.23 and 6.32, seq(Fβ [b]) = seq(ℓβ ) ≥ seq(Fα [b]) + 1.

(7)

Next, since at most one process is Byzantine and pb is correct, Lemma 6.27 ensures that there exists at most one index j ̸= b such that seq(Fβ [j]) < seq(Fα [j]), and that if such j exists, then seq(Fβ [j]) ≥ seq(Fα [j]) − 1. Summing over i ̸= b therefore gives X X seq(Fβ [i]) ≥ seq(Fα [i]) − 1. (8) i̸=b

i̸=b

Putting together (7) and (8), we get N (Fβ ) = seq(Fβ [b]) +

X

seq(Fβ [i])

i̸=b

  X ≥ seq(Fα [b]) + 1 +  seq(Fα [i]) − 1

i̸=b

= N (Fα ), as claimed.

Claim 6.35

Claim 6.36. If N (Fβ ) = N (Fα ), then yβ ≥ xα ≥ min{xα , yα },

(9)

xβ > min{xα , yα }.

(10)

Consequently, min{xβ , yβ } ≥ min{xα , yα }. Proof. Assume that N (Fβ ) = N (Fα ). We first show that a ∈ / Qβ . Suppose instead that a ∈ Qβ . Then Proposition 6.26 gives Fα ⪯ Fβ , so seq(Fβ [i]) ≥ seq(Fα [i]) for every i. But seq(Fβ [b]) > seq(Fα [b]) by (7). Summing over all i then yields N (Fβ ) > N (Fα ), contradicting our assumption. Since Qβ omits only one index, we conclude that oβ = a, so yβ = rank(Fβ [a]). Proposition 6.25 immediately gives yβ ≥ xα , proving (9). For (10), if b ∈ Qα , then Proposition 6.33 gives xβ > xα ≥ min{xα , yα }; otherwise, oα = b, so yα = rank(Fα [b]) and Proposition 6.32 gives xβ > yα ≥ min{xα , yα }. So in both cases, xβ > min{xα , yα }. Inequalities (9) and (10) together imply that min{xβ , yβ } ≥ min{xα , yα }. Claim 6.36 28

Claim 6.37. If N (Fβ ) = N (Fα ) and min{xβ , yβ } = min{xα , yα }, then 1{xβ > yβ } > 1{xα > yα }. Proof. Suppose N (Fβ ) = N (Fα ) and min{xβ , yβ } = min{xα , yα }. By Claim 6.36, inequalities (9) and (10) hold. By (10), xβ > min{xβ , yβ }, so yβ = min{xβ , yβ } = min{xα , yα }. Combined with (9), this gives yβ = xα = min{xα , yα }. Therefore, xα = min{xα , yα } ≤ yα ,

so 1{xα > yα } = 0;

xβ > min{xβ , yβ } = yβ ,

so 1{xβ > yβ } = 1.

This proves 1{xβ > yβ } > 1{xα > yα }.

Claim 6.37

Claims 6.35 to 6.37 together show that τβ >lex τα . Therefore, tβ = E(τβ ) > E(τα ) = tα .

Proposition 6.34

Proposition 6.38 (Return values). Algorithm 3 returns positive integers from next() and satisfies ordering (BT1a) and uniqueness (BT1b). Proof. Consider a complete operation γ at a correct process pi . By Proposition 6.23(b), N (Fγ ) ≥ seq(Fγ [i]) = seq(ℓγ ) ≥ 1. Thus, Proposition 6.16 gives tγ ≥ N (Fγ )2 ≥ 1, so both tγ and n · tγ + i are positive integers. For (BT1a), suppose a complete operation α at a correct process pa precedes a complete operation β at a correct process pb . By Proposition 6.34, tα < tβ , so n · tα + a < n · (tα + 1) ≤ n · tβ + b. For (BT1b), timestamps returned by different correct processes differ modulo n, and those returned by the same correct process are distinct by (BT1a) since its operations are sequential. Proposition 6.38 Part 5. Liveness and latency. Proposition 6.39 (Liveness). In Algorithm 3, every invocation of next() by a correct process eventually returns. Proof. On line 13, a correct invoker sends every process a request that is valid by Proposition 6.18(c); hence every correct process eventually receives it. By line 11, the request frontier contains the invoker’s current label at the invoker’s coordinate, so each correct recipient sends a valid reply acknowledging that label on line 17. These replies have distinct signers and therefore pass the check on line 19. At least n − 1 processes, including the invoker itself, are correct, so eventually the invoker accepts n − 1 replies, the check on line 22 succeeds, and the invoker returns on line 28. Proposition 6.39 Proposition 6.40 (Latency). The worst-case message delay of Algorithm 3 is two. Proof sketch. An invocation follows one Req delay and one Reply delay, as illustrated below: Req

Reply

return

invoke next()

Proposition 6.40

By Propositions 6.38 and 6.39, Algorithm 3 satisfies the conditions of Proposition 5.3 and hence implements TS. By Proposition 6.40, its worst-case message delay is two. Theorem 6.3

29

6.3

Latency Lower Bounds

The latency lower bounds for systems with crash failures (Section 4.3) also apply to systems with Byzantine processes and digital signatures. Thus, Proposition 4.22 immediately implies the following. Observation 6.41. In a system with Byzantine processes and digital signatures, any implementation of TS has worst-case message delay at least two. And Theorem 4.23 similarly implies the following. Observation 6.42. In a system with Byzantine processes and digital signatures, if f ≥ 2, then any implementation of TS has worst-case message delay at least three.

6.4

Summary

Proposition 6.1 and Observation 6.2 together give the following necessary and sufficient condition for implementing TS under Byzantine failures with digital signatures. Corollary 6.43. In a system with Byzantine processes and digital signatures, there exists an implementation of TS if and only if n > 3f . We next state the optimal latency for implementations of TS in systems with Byzantine processes and digital signatures. When n > 3f and f ≥ 2, the latency upper bound in Observation 6.2 matches the latency lower bound in Observation 6.42, yielding the following. Corollary 6.44. In a system with Byzantine processes and digital signatures, if n > 3f and f ≥ 2, then the optimal latency of implementing TS is three message delays. When n > 3f and f = 1, the latency upper bound in Theorem 6.3 matches the latency lower bound in Observation 6.41, yielding the following. Corollary 6.45. In a system with Byzantine processes and digital signatures, if n > 3f and f = 1, then the optimal latency of implementing TS is two message delays. Thus, the optimal latency of implementing TS under Byzantine failures with digital signatures is settled in all cases where an implementation exists.

7

Results for Byzantine Failures without Digital Signatures

In this section, we consider implementations of TS in systems with Byzantine processes, but without digital signatures. Again, we assume there are n ≥ 2 processes, of which at most f ≥ 1 may be Byzantine.

7.1

Maximum Resilience

The resilience lower bound for systems with Byzantine processes and digital signatures, given by Proposition 6.1, holds also for systems without digital signatures: Observation 7.1. In a system with Byzantine processes, there exists an implementation of TS only if n > 3f .

7.2

Latency Upper Bound

Theorem 7.2. In a system with Byzantine processes, if n > 3f , then there exists an implementation of TS (Algorithm 4) whose worst-case message delay is three.

30

Proof. The algorithm uses three types of messages. We call a message valid if it has one of the following forms: • a request ⟨Req q⟩, where q is an integer; • a proposal ⟨Prop ⟨k, q⟩, v⟩, where k ∈ {0, . . . , n − 1} and q and v are integers; • an echo ⟨Echo q, j, v⟩, where j ∈ {0, . . . , n − 1} and q and v are integers. We first establish some supporting properties of the algorithm. We then show that the algorithm implements TS by proving that it returns positive integers and satisfies ordering (BT1a), uniqueness (BT1b), and liveness (BT2). Finally, we show that its worst-case message delay is three. Claim 7.3. For every correct process pi , its local clock xi is non-decreasing. Proof. After initialization, the only assignments to xi are on lines 14 and 19, neither of which decreases xi . Claim 7.3

Claim 7.4. If the set certified computed by a correct process pi on line 25 contains ⟨j, v⟩, then at that time, at least n − 2f correct processes pk satisfy xk ≥ v. Proof. Let S = {k : echoVali [j, k] = v} when pi executes line 25. Then |S| ≥ n − f , so at least n − 2f indices in S belong to correct processes. For each such correct index k, process pk sent its Echo message only after line 19 made xk ≥ v. By Claim 7.3, xk ≥ v still holds when pi executes line 25. Claim 7.4 Claim 7.5. If an invocation of next() by a correct process computes base timestamp t on line 29, then at the time of return, at least n − 2f correct processes pk satisfy xk ≥ t. Proof. By line 29, ⟨j, t⟩ ∈ certified for some j. By Claim 7.4, xk ≥ t for at least n − 2f correct processes pk when certified is computed, and Claim 7.3 implies that these inequalities still hold when the invocation returns. Claim 7.5 Claim 7.6. If the set certified computed by a correct process pi on line 25 contains both ⟨j, v⟩ and ⟨j, v ′ ⟩, then v = v ′ . Proof. Let Su = {k : echoVali [j, k] = u} when pi executes line 25. Suppose v ̸= v ′ . Since both pairs belong to certified , we have |Sv |, |Sv′ | ≥ n − f . Since each entry echoVali [j, k] records at most one non-⊥ value, Sv ∩Sv′ = ∅. But |Sv ∩Sv′ | = |Sv |+|Sv′ |−|Sv ∪Sv′ | ≥ 2(n−f )−n = n−2f > 0, a contradiction. Claim 7.6 Claim 7.7 (Ordering for base timestamps). Suppose two next() operations invoked by correct processes compute base timestamps t and t′ on line 29, respectively. If the first returns before the second is invoked, then t < t′ . Proof. By Claim 7.5, when the first operation returns, there is a set C of process indices such that |C| ≥ n−2f and for every k ∈ C, pk is correct and xk ≥ t. By Claim 7.3, these inequalities still hold when the second operation is invoked and thereafter. Let pj be the process performing the second operation, let qj be the value of seqj when it is invoked, let certified ′ be pj ’s certified set when it returns on line 30, and let P = {k : ⟨k, −⟩ ∈ certified ′ }. The check on line 26 ensures that |certified ′ | ≥ n − f . By Claim 7.6, distinct pairs in certified ′ have distinct first components, so |P | = |certified ′ | ≥ n − f . Hence, |C ∩ P | = |C| + |P | − |C ∪ P | ≥ (n − 2f ) + (n − f ) − n = n − 3f > 0, so we may fix some ℓ ∈ C ∩ P ; process pℓ is correct. Since ℓ ∈ P , there is a value vℓ such that ⟨ℓ, vℓ ⟩ ∈ certified ′ . By line 25, process pj received an ⟨Echo qj , ℓ, vℓ ⟩ message from at least n − f distinct processes; at least n − 2f > 0 of them are correct, so fix one such correct process pm . By line 20, pm sent that Echo only after receiving from pℓ the message 31

Algorithm 4 A worst-case three-delay implementation of TS in a system with Byzantine processes where n > 3f . Code for process pi (0 ≤ i < n): 1: xi ← 0 ▷ pi ’s local clock. 2: seqi ← 0 ▷ Sequence number of pi ’s ongoing invocation, or of its next invocation when idle. 3: reqSeqi [k] ← −1 for each k ▷ Largest q in a ⟨Req q⟩ received from pk . 4: propSeqi [k, j] ← −1 for each k, j 5: phasei ← idle 6: echoVali [j, k] ← ⊥ for each j, k

▷ Largest q in a ⟨Prop ⟨k, q⟩, −⟩ received from pj . ▷ Whether pi is idle or has an ongoing invocation. ▷ pj ’s proposal for pi ’s ongoing invocation as echoed by pk .

7: upon invocation of next() do 8: phasei ← ongoing 9: echoVali [j, k] ← ⊥ for each j, k 10: send ⟨Req seqi ⟩ to every process 11: upon receive valid ⟨Req q⟩ from pk do 12: 13: 14: 15:

if q > reqSeqi [k] then reqSeqi [k] ← q xi ← xi + 1 send ⟨Prop ⟨k, q⟩, xi ⟩ to every process

16: upon receive valid ⟨Prop ⟨k, q⟩, v⟩ from pj do 17: if q > propSeqi [k, j] then 18: propSeqi [k, j] ← q 19: 20:

xi ← max(xi , v) send ⟨Echo q, j, v⟩ to pk

▷ pi says to pk : “pj proposed v for your invocation q.”

21: upon receive valid ⟨Echo q, j, v⟩ from pk do 22: if phasei = ongoing and q = seqi then 23: if echoVali [j, k] = ⊥ then 24: echoVali [j, k] ← v 25: 26: 27: 28: 29: 30:

certified ← {⟨j ′ , v ′ ⟩ : v ′ ̸= ⊥, |{k ′ : echoVali [j ′ , k ′ ] = v ′ }| ≥ n − f } ▷ The proposal by pj ′ of value v ′ is certified once it is echoed by n − f distinct processes pk′ . if |certified | ≥ n − f then phasei ← idle seqi ← seqi + 1 t ← max{v ′ : ⟨j ′ , v ′ ⟩ ∈ certified } ▷ Base timestamp. return n · t + i ▷ Completes the next() invocation.

32

⟨Prop ⟨j, qj ⟩, vℓ ⟩. As pℓ is correct, it sent that Prop to every process on line 15 immediately after executing xℓ ← xℓ + 1 on line 14, upon receiving the Req message that pj sent at the start of the second operation. Because ℓ ∈ C, xℓ ≥ t immediately before this assignment, so vℓ ≥ t + 1 > t. Since line 29 computes the base timestamp as the maximum value in certified ′ , we have t′ ≥ vℓ > t. Claim 7.7 Claim 7.8 (Return values). Algorithm 4 returns positive integers from next() and satisfies ordering (BT1a) and uniqueness (BT1b). Proof. Consider a complete operation at a correct process pi with base timestamp t, and let certified be the set from which t is computed. By the check on line 26, this set contains at least n − f pairs, whose first components are distinct by Claim 7.6. Since n − f > f , certified contains a pair ⟨ℓ, vℓ ⟩ such that pℓ is correct. Some correct process echoed vℓ after receiving it in a Prop message from pℓ , which sent that message right after incrementing xℓ on line 14; hence vℓ ≥ 1. Moreover, every value in certified is an integer, since it comes from a valid Echo message. Thus, t, the maximum of these values, is a positive integer, and so is n · t + i. For (BT1a), suppose a complete operation at a correct process pi with base timestamp t precedes one at a correct process pj with base timestamp t′ . By Claim 7.7, t < t′ , so n · t + i < n · (t + 1) ≤ n · t′ + j. For (BT1b), timestamps returned by different correct processes differ modulo n, and those returned by the same correct process are distinct by (BT1a) since its operations are sequential. Claim 7.8 Claim 7.9 (Liveness). In Algorithm 4, every invocation of next() by a correct process eventually returns. Proof. Every message sent by a correct process is valid, since seqi and xi always hold integers and every other field is either a process index or copied from a valid message. Let pi be a correct process that invokes next(), and let q be the value of seqi at that invocation. By initialization (lines 2 and 3) and the increment of seqi after each return (line 28), the Req message for q is fresh at every correct process. Hence every correct process eventually receives it, passes the check on line 12, and sends a corresponding Prop message to every process. Until the invocation returns, pi remains in phase ongoing with seqi = q and sends no request with a higher sequence number. Likewise, by initialization (lines 2 and 4) and the increment of seqi after each return (line 28), every Prop message for q from a correct proposer is fresh at every correct process, which eventually passes the check on line 17 and sends the corresponding Echo to pi . Thus, for each of at least n − f correct proposers, pi eventually receives n − f matching Echo messages. Since the corresponding echoVali entries were reset to ⊥ when the invocation began, pi records all n − f echoes on line 24; together, the resulting entries certify the proposal. Consequently, the condition |certified | ≥ n − f eventually holds, and pi returns on line 30. Claim 7.9 Claim 7.10 (Latency). The worst-case message delay of Algorithm 4 is three. Proof sketch. An invocation follows one Req delay, one Prop delay, and one Echo delay, as illustrated below (where a thin arrow denotes a single message and a thick arrow denotes multiple messages): Req

Prop

Echo

return

invoke next()

Claim 7.10

By Claims 7.8 and 7.9, Algorithm 4 satisfies the conditions of Proposition 5.3 and hence implements TS. By Claim 7.10, its worst-case message delay is three. Theorem 7.2

33

7.3

Latency Lower Bounds

7.3.1

Auxiliary Lemmas

We begin with two lemmas used in the proofs below. First, the notion of a loquacious algorithm (Definition 4.19) carries over unchanged. A Byzantine process that deviates from A need not behave loquaciously. The loquacious-transformation lemma has the following Byzantine analogue. Lemma 7.11 (Byzantine version of Lemma 4.20). In a system with Byzantine processes, let A be an implementation of TS. Then there exists a loquacious implementation A′ of TS such that δ(A′ ) ≤ δ(A). We defer its proof to Appendix C.1.2. Our second auxiliary lemma adapts the completion lemma (Lemma 4.21) to the Byzantine setting by adding one hypothesis: Every process in Q must follow A throughout the prefix. Without this requirement, p may deviate from the algorithm and fail to return; alternatively, another process q ∈ Q may send a reply that p recognizes as invalid, in which case p may, without violating the two-delay bound, disregard it and wait for a reply from a process outside Q before returning. We state the resulting Byzantine variant below, with the differences from Lemma 4.21 underlined. (We index sequences from 0. For a sequence µ, we write µ[i..j] for the contiguous subsequence µ[i], . . . , µ[j].) Lemma 7.12 (Byzantine version of Lemma 4.21). In a system with Byzantine processes, let A be a loquacious algorithm with δ(A) ≤ 2. Let p be a process, and let Q be a set of processes such that |Q| = n − f and p ∈ Q. Suppose that σ is a schedule prefix of A in which the following hold: 1. Process p invokes an operation and broadcasts a message m in step σ[a]. 2. For each q ∈ Q, process q receives m and broadcasts a message mq in step σ[jq ]. 3. Process p receives the set of messages {mq : q ∈ Q} in step σ[b]. 4. Between steps σ[a] and σ[b], inclusive, the only steps are those specified above. 5. Processes in Q follow the algorithm A throughout σ[0..b]. Then the operation invoked by p in step σ[a] returns no later than step σ[b]. Its proof is very close to that of Lemma 4.21; we defer it to Appendix C.3.2. 7.3.2

The Bounds

The latency lower bounds for systems with crash failures (Section 4.3) also apply to systems with Byzantine processes, since any implementation that tolerates Byzantine processes also tolerates crashes. Thus, Proposition 4.22 immediately implies the following. Observation 7.13. In a system with Byzantine processes, any implementation of TS has worst-case message delay at least two. Similarly, Theorem 4.23 immediately implies the following. Observation 7.14. In a system with Byzantine processes, if f ≥ 2, then any implementation of TS has worst-case message delay at least three. When f = 1, the best lower bound we obtain for n > 4 is two delays (from Observation 7.13). However, in the boundary case n = 4, we prove a stronger lower bound of three delays. Theorem 7.15. In a system with Byzantine processes, if n = 4 and f = 1, then any implementation of TS has worst-case message delay at least three.

34

p0

r0

p1 p2 p3

Auxiliary prefix α0

p0 p1

r1

p2 p3

Auxiliary prefix α1 (a) Auxiliary schedule prefixes, in which all processes follow algorithm A. p0

r0

p1 Byz

r1

p2 p3

Principal prefix σ01 : r0 < r1

p0 p1

r0 r1

p2 Byz

p3

Principal prefix σ10 : r1 < r0 (b) Principal schedule prefixes, in which the process marked Byz deviates from algorithm A.

Figure 2: Proof of Theorem 7.15. In a system with n = 4 processes, at most f = 1 of which may be Byzantine, suppose toward a contradiction that some loquacious implementation A of TS has δ(A) ≤ 2. Each dot marks a step and is colored by the invocation it serves, while each arrow shows a message received within the prefix. A horizontal segment tracks a next() operation: marks its invocation step, and labeled r indicates that it has returned r by that step; without a return marker, the figure makes no claim about whether the operation returns within the prefix. A solid arrow shows a message sent according to A; a wavy arrow in a principal prefix shows a Byzantine message with the same content as the corresponding message in an auxiliary prefix. By Lemma 7.12, the operations of p0 in α0 and p1 in α1 return by the final depicted steps; let r0 and r1 denote their respective return values. Process p0 cannot distinguish either principal prefix from α0 , and p1 cannot distinguish either from α1 . Thus, in both principal prefixes, p0 returns r0 and p1 returns r1 . Condition (BT1a) then gives r0 < r1 in σ01 and r1 < r0 in σ10 , a contradiction.

35

Proof. Consider a system with n = 4 processes named {p0 , p1 , p2 , p3 }, at most f = 1 of which may be Byzantine. Suppose, toward a contradiction, that in this system there exists an implementation of TS with worst-case message delay less than three. By Lemma 7.11, there is a loquacious implementation A of TS with δ(A) < 3. Since finite worst-case message delays are integers (Proposition 2.8), δ(A) ≤ 2. By Proposition 5.3, A satisfies ordering (BT1a). We construct four schedule prefixes of A: two auxiliary prefixes α0 and α1 as shown in Figure 2a, and two principal prefixes σ01 and σ10 as shown in Figure 2b. First consider the auxiliary prefixes α0 and α1 , shown in Figure 2a. Schedule prefix α0 begins with process p1 invoking an operation and p2 receiving its broadcast. Next, p0 invokes an operation and broadcasts a message. Processes p0 , p2 , p3 each receive this message and broadcast a reply, in three separate steps, after which p0 receives all three replies in a single step. All processes follow A, so by Lemma 7.12 (with p = p0 and Q = {p0 , p2 , p3 }), p0 ’s operation has returned by the final step; let r0 be the value returned. Similarly, in α1 , process p0 invokes an operation and p3 receives its broadcast before p1 invokes an operation and completes an analogous round trip with p1 , p2 , p3 . Again, by Lemma 7.12 (with p = p1 and Q = {p1 , p2 , p3 }), p1 ’s operation has returned by the final step; let r1 be the value returned. Next, construct σ01 as shown in Figure 2b: Process p0 completes a round trip with p0 , p2 , p3 , followed by p1 with p1 , p2 , p3 . Processes p0 , p1 , p3 follow A, whereas p2 deviates from A by sending its reply from α0 to p0 and its reply from α1 to p1 .4 Process p3 receives p0 ’s invocation message and then p1 ’s, so its state at each reply is the one it has in α0 and in α1 ; it therefore sends those replies to p0 and p1 , respectively. All remaining messages are delayed until after σ01 . These steps form a schedule prefix of A, which extends to a schedule in which p2 is the only Byzantine process. Prefix σ01 is indistinguishable from α0 to p0 and from α1 to p1 , so their operations return r0 and r1 , respectively. The former returns before the latter is invoked, so applying condition (BT1a) to the extended schedule yields r0 < r1 . Symmetrically, construct σ10 as shown in Figure 2b, with p1 ’s operation first and p0 ’s second. Here, processes p0 , p1 , p2 follow A, whereas p3 deviates from A by sending its reply from α1 to p1 and its reply from α0 to p0 . As above, σ10 extends to a schedule of A in which p3 is the only Byzantine process. It is indistinguishable from α1 to p1 and from α0 to p0 , so the operations return r1 and r0 , respectively. Applying condition (BT1a) to the extended schedule yields r1 < r0 , contradicting r0 < r1 . Theorem 7.15

7.4

Summary and Open Question

Observation 7.1 and Theorem 7.2 together give the following necessary and sufficient condition for implementing TS in a system with Byzantine processes. Corollary 7.16. In a system with Byzantine processes, there exists an implementation of TS if and only if n > 3f . We now turn to the optimal latency. When n > 3f and f ≥ 2, the latency upper bound in Theorem 7.2 matches the latency lower bound in Observation 7.14, yielding the following. Corollary 7.17. In a system with Byzantine processes, if n > 3f and f ≥ 2, then the optimal latency of implementing TS is three message delays. When n = 4 and f = 1, the latency upper bound in Theorem 7.2 matches the latency lower bound in Theorem 7.15, yielding the following. Corollary 7.18. In a system with Byzantine processes, if n = 4 and f = 1, then the optimal latency of implementing TS is three message delays. One case remains open: n > 4 and f = 1. Here the upper bound is three delays (Theorem 7.2), whereas the lower bound is two delays (Observation 7.13). 4 Note that p may not be able to do this if A used digital signatures. In that case, p ’s reply to p in α may include data 2 2 0 0 signed by p1 , received in p1 ’s invocation broadcast. Process p2 could not reproduce that reply in σ01 : When p2 must send it, p1 has not yet invoked, so the signature does not exist and p2 cannot forge it. The same applies to p3 in σ10 .

36

Question 7.19. In a system with Byzantine processes, if n > 4 and f = 1, what is the optimal latency of implementing TS?

8

Related Work

Applications of timestamps. Timestamps have long been used in concurrent and distributed algorithms to order requests and distinguish versions of shared data. For example, in Lamport’s mutual-exclusion algorithm [Lam78, p. 561], processes order requests for a shared resource by their timestamps; once a request is granted, any subsequently issued request receives a larger timestamp. In optimistic concurrency control for databases, Kung and Robinson [KR81, Section 3.2] assign transaction numbers from a global counter so that a transaction that completes before another starts receives a smaller number. In an early shared-memory construction of MWMR atomic registers, Vitányi and Awerbuch [VA86, Section 3] attach ordered tags to written values to determine which values reads return. Motivated by such uses, we study the resilience and latency of TS implementations in the presence of crash and Byzantine failures. Message-passing register algorithms. Many register implementations in message-passing systems generate timestamps internally, and we can extract this logic to obtain an implementation of TS. For example, in the MWMR atomic register of Lynch and Shvartsman [LS97, Section 4.1], a writer queries a read quorum for tags and forms a new tag by incrementing the largest sequence number received and pairing it with its own identifier; the writer then propagates the tagged value to a write quorum and waits for acknowledgments. If we instantiate this algorithm with majority quorums, omit register values, and have each writer return its new tag as a positive integer preserving tag order, we can obtain an implementation of TS in systems with crash failures when n > 2f . However, the resulting implementation takes two round trips per operation, for a worst-case message delay of four. In contrast, our algorithms achieve the optimal latency: two message delays when f = 1 (Algorithm 1) and three when f ≥ 2 (Algorithm 2). As mentioned in Section 4.2.2, Algorithm 2 adopts the max-min technique [DGLC04, Section 1.1], previously used to obtain three-delay reads for MWMR atomic registers [HNS17, Section 4]. Some storage protocols that tolerate Byzantine servers [MR98, Section 3.2; MAD02, Section 3, Figure 1] use the same general write pattern as Lynch and Shvartsman’s register algorithm. A writer queries a quorum for timestamps, chooses a fresh timestamp larger than those received, and propagates the timestamped value, waiting for acknowledgments from a quorum. To extract their timestamping logic, we can omit the stored data, wait for n − f responses in each phase, and have each write return its new timestamp. This yields an implementation of TS that does not rely on digital signatures in systems with Byzantine processes when n > 3f . However, its worst-case message delay is four, whereas Algorithm 4 achieves three. Timestamp services in distributed databases. Some distributed databases use a dedicated timestamp service for transaction processing. Percolator’s timestamp oracle [PD10, Section 2.3] runs on a single server with stable storage and supplies strictly increasing timestamps. It can serve requests from memory in one round trip (two message delays). To preserve timestamp monotonicity across restarts, the oracle periodically records an upper bound on its allocated timestamps in stable storage and resumes above that bound after a restart. The oracle cannot serve requests while it is down, whereas our model requires operations invoked by correct processes to complete despite up to f (permanent) crashes. Timestamp abstractions in shared memory. Aspnes et al. [AACE15, Algorithm 4] give a limited-use, wait-free implementation of TS from a max register. Other work implements slightly weaker objects from read/write registers: the weak counter of Guerraoui and Ruppert [GR05, Section 4], designed for anonymous systems, and fetch-and-increment with multiplicity of Castañeda, Rajsbaum, and Raynal [CRR23, Section 4.2]. For both objects, an operation returns an integer larger than those returned by preceding operations, but concurrent operations may return the same integer. Breaking such ties by process identifiers yields wait-free implementations of TS, although for the weak counter this sacrifices anonymity. All of

37

these shared-memory constructions can be run in message-passing systems via register emulation [ABD95; LS97], but the resulting implementations do not achieve the optimal latency of implementing TS. Ellen, Fatourou, and Ruppert [EFR07] and Helmi et al. [HHPW11] study how many read/write registers are needed to implement variants of TS, whereas we study latency in message-passing systems.

9

Conclusion

We have determined the maximum resilience of TS implementations in asynchronous message-passing systems with crash or Byzantine failures, as well as the optimal latency of implementing TS in all but one case. The open case concerns systems with Byzantine processes and no digital signatures when n > 4 and f = 1: Do two message delays suffice, or are three necessary? When n = 4 and f = 1, we have shown that digital signatures reduce the optimal latency from three message delays to two, so resolving this question would show whether digital signatures offer the same advantage for n > 4.

10

AI Methodology

The ideas behind Algorithm 3 emerged from a multi-agent search using GPT-5.6 Sol in Codex. We then put considerable effort into simplifying the construction (with help from GPT and Claude), developing our own notation, and writing our own presentation of the algorithm and its proof to make them easier to follow. The ideas behind Algorithm 4 emerged from a conversation with GPT-5.5 Pro that began with two of our own three-delay TS implementations in systems with Byzantine processes: one with signatures for n > 3f , and one without signatures for n > 4f . GPT proposed an implementation without signatures for n = 4 and f = 1, and then generalized it to all n > 3f . We simplified the algorithm in discussion with GPT, then wrote our own presentation of the algorithm and its proof to make them easier to follow. GPT also contributed to proving two auxiliary results. GPT-5.4 Pro proposed a retiming argument for Lemma B.1 after we found an error in its first attempt, and GPT-5.5 developed the proof of Proposition 2.7 under our guidance. We simplified the time mapping in the former and wrote the exposition of both proofs. We also used GPT, Claude, and Gemini for literature search, writing code to generate figures, and copyediting. We checked all technical content, including every algorithm and proof, and take full responsibility for this paper.

References [AACE15]

James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. “Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity”. In: J. ACM 62.1 (2015), 3:1–3:22. doi: 10.1145/ 2732263. url: https://doi.org/10.1145/2732263.

[ABD95]

Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. “Sharing Memory Robustly in MessagePassing Systems”. In: J. ACM 42.1 (1995), pp. 124–142. doi: 10.1145/200836.200869. url: https://doi.org/10.1145/200836.200869.

[AW04]

Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. 2nd ed. Wiley series on parallel and distributed computing. Wiley, 2004. isbn: 978-0-471-45324-6. doi: 10.1002/0471478210. url: https://doi.org/10.1002/0471478210.

[Awe85]

Baruch Awerbuch. “Complexity of Network Synchronization”. In: J. ACM 32.4 (1985), pp. 804– 823. doi: 10.1145/4221.4227. url: https://doi.org/10.1145/4221.4227.

[BFKR25]

João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud. “Asynchronous Latency and Fast Atomic Snapshot”. In: 39th International Symposium on Distributed Computing, DISC 2025, Berlin, Germany, October 27–31, 2025. Ed. by Dariusz R. Kowalski. Vol. 356. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 15:1–15:22. doi: 10.4230/LIPIcs.DISC.2025.15. url: https://doi.org/10.4230/LIPIcs.DISC.2025.15. 38

[CK21]

Shir Cohen and Idit Keidar. “Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer”. In: 35th International Symposium on Distributed Computing, DISC 2021, Freiburg, Germany (Virtual Conference), October 4–8, 2021. Ed. by Seth Gilbert. Vol. 209. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 18:1–18:18. doi: 10.4230/LIPIcs.DISC.2021.18. url: https://doi.org/10.4230/LIPIcs.DISC.2021.18.

[CRR23]

Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. “Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch&Increment, Stacks and Queues with Multiplicity”. In: Distributed Comput. 36.2 (2023), pp. 89–106. doi: 10.1007/s00446- 022- 00440- y. url: https://doi.org/10.1007/s00446-022-00440-y.

[DGLC04]

Partha Dutta, Rachid Guerraoui, Ron R. Levy, and Arindam Chakraborty. “How fast can a distributed atomic read be?” In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25–28, 2004. ACM, 2004, pp. 236–245. doi: 10.1145/1011767.1011802. url: https://doi. org/10.1145/1011767.1011802.

[EFR07]

Faith Ellen, Panagiota Fatourou, and Eric Ruppert. “The Space Complexity of Unbounded Timestamps”. In: Distributed Computing, 21st International Symposium, DISC 2007, Lemesos, Cyprus, September 24–26, 2007, Proceedings. Ed. by Andrzej Pelc. Vol. 4731. Lecture Notes in Computer Science. Springer, 2007, pp. 223–237. doi: 10.1007/978-3-540-75142-7_19. url: https://doi.org/10.1007/978-3-540-75142-7_19.

[GR05]

Rachid Guerraoui and Eric Ruppert. “What Can Be Implemented Anonymously?” In: Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26–29, 2005, Proceedings. Ed. by Pierre Fraigniaud. Vol. 3724. Lecture Notes in Computer Science. Springer, 2005, pp. 244–259. doi: 10.1007/11561927_19. url: https://doi.org/10. 1007/11561927_19.

[HHPW11]

Maryam Helmi, Lisa Higham, Eduardo Pacheco, and Philipp Woelfel. “The space complexity of long-lived and one-shot timestamp implementations”. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6–8, 2011. Ed. by Cyril Gavoille and Pierre Fraigniaud. ACM, 2011, pp. 139–148. doi: 10.1145/1993806.1993826. url: https://doi.org/10.1145/1993806.1993826.

[HNS17]

Theophanis Hadjistasi, Nicolas Nicolaou, and Alexander A. Schwarzmann. “Oh-RAM! One and a Half Round Atomic Memory”. In: Networked Systems - 5th International Conference, NETYS 2017, Marrakech, Morocco, May 17–19, 2017, Proceedings. Ed. by Amr El Abbadi and Benoı̂t Garbinato. Vol. 10299. Lecture Notes in Computer Science. Springer, 2017, pp. 117–132. doi: 10.1007/978- 3- 319- 59647- 1_10. url: https://doi.org/10.1007/978- 3- 319- 596471_10.

[HW90]

Maurice P. Herlihy and Jeannette M. Wing. “Linearizability: A Correctness Condition for Concurrent Objects”. In: ACM Trans. Program. Lang. Syst. 12.3 (1990), pp. 463–492. doi: 10.1145/78969.78972. url: https://doi.org/10.1145/78969.78972.

[KR81]

H. T. Kung and John T. Robinson. “On Optimistic Methods for Concurrency Control”. In: ACM Trans. Database Syst. 6.2 (1981), pp. 213–226. doi: 10 . 1145 / 319566 . 319567. url: https://doi.org/10.1145/319566.319567.

[Lam78]

Leslie Lamport. “Time, Clocks, and the Ordering of Events in a Distributed System”. In: Commun. ACM 21.7 (1978), pp. 558–565. doi: 10.1145/359545.359563. url: https://doi. org/10.1145/359545.359563.

[LS97]

N. A. Lynch and A. A. Shvartsman. “Robust Emulation of Shared Memory Using Dynamic Quorum-Acknowledged Broadcasts”. In: Digest of Papers: FTCS-27, The Twenty-Seventh Annual International Symposium on Fault-Tolerant Computing, Seattle, Washington, USA, June 24–27, 1997. IEEE Computer Society, 1997, pp. 272–281. doi: 10.1109/FTCS.1997.614100. url: https://doi.org/10.1109/FTCS.1997.614100. 39

[MAD02]

Jean-Philippe Martin, Lorenzo Alvisi, and Michael Dahlin. “Minimal Byzantine Storage”. In: Distributed Computing, 16th International Conference, DISC 2002, Toulouse, France, October 28–30, 2002 Proceedings. Ed. by Dahlia Malkhi. Vol. 2508. Lecture Notes in Computer Science. Springer, 2002, pp. 311–325. doi: 10.1007/3-540-36108-1_21. url: https://doi.org/10. 1007/3-540-36108-1_21.

[MR98]

Dahlia Malkhi and Michael K. Reiter. “Byzantine Quorum Systems”. In: Distributed Comput. 11.4 (1998), pp. 203–213. doi: 10.1007/s004460050050. url: https://doi.org/10.1007/ s004460050050.

[PD10]

Daniel Peng and Frank Dabek. “Large-scale Incremental Processing Using Distributed Transactions and Notifications”. In: 9th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2010, October 4–6, 2010, Vancouver, BC, Canada, Proceedings. Ed. by Remzi H. Arpaci-Dusseau and Brad Chen. USENIX Association, 2010, pp. 251–264. url: http://www.usenix.org/events/osdi10/tech/full_papers/Peng.pdf.

[VA86]

Paul M.B. Vitányi and Baruch Awerbuch. “Atomic Shared Register Access by Asynchronous Hardware (Detailed Abstract)”. In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27–29 October 1986. IEEE Computer Society, 1986, pp. 233–243. doi: 10.1109/SFCS.1986.11. url: https://doi.org/10.1109/SFCS.1986.11.

A

Auxiliary Notations

We use the following notation for finite sequences of steps: • |σ| is the number of steps in a schedule prefix σ; and • ⟨s1 , . . . , sk ⟩ is the finite sequence consisting of the steps s1 , . . . , sk , in that order. We also introduce notation for the affine maps used below to retime runs. In interval notation, an overstruck bracket ([ or )] denotes an endpoint that may be open or closed. Definition A.1 (Affine map). Let I = ([ a, b]) and J = ([ c, d]) be bounded real intervals with the same endpoint types, where a < b and c < d. We write AffineI→J : I → J for the map defined by d−c (x − a). b−a We use the same notation for half-infinite intervals bounded on the same side and having the same finite-endpoint type: ∆

AffineI→J (x) = c +

∆

Affine[(a,+∞)→[(c,+∞) (x) = x + (c − a), ∆

Affine(−∞,b])→(−∞,d]) (x) = x + (d − b). Proposition A.2. AffineI→J is a strictly increasing bijection from I to J.

B

Properties of Finite Worst-Case Message Delay

In this section, we prove the two consequences of finite worst-case message delay stated in Section 2.2. Although originally stated for crash failures, these results—along with their proofs—hold under Byzantine failures as well, with “correct” interpreted in the respective sense.

40

O 1

3

δR (O)

2

···

T 0

1

2

k

k+1 α

1

3

2

···

T′ 0

1−η

1

2−η O

2

k + 1 − η δR′ (O) k + 1

Figure 3: Proof of Lemma B.1: retiming the run R = (S, T ) (top) into the run R′ = (S, T ′ ) (bottom) when k < α < k + 1. For each integer i ≥ 1, the unit interval (i − 1, i] in T is compressed into (i − η, i] in T ′ , where η = (k + 1 − α)/2 ∈ (0, 1/2). In T ′ , “◦” marks open interval endpoints, “•” marks closed interval endpoints, and dashed segments mark times at which no step is taken. Every message m sent during O in R with δR (m) ≤ 1 still satisfies δR′ (m) ≤ 1 (as illustrated by cases 1 , 2 , and 3 ). The operation satisfies δR (O) ≤ α, but this choice of η ensures that δR′ (O) = ϕ(δR (O)) > α.

B.1

Finite Worst-Case Message Delay Implies Liveness

We first prove Proposition 2.7, restated below. Proposition 2.7. If δ(A) < ∞, then A satisfies liveness: In every schedule of A, every operation invoked by a correct process eventually returns. Proof. Let A be an algorithm with finite worst-case message delay α. Let S be an (infinite) schedule of A, and let O be an operation in S invoked by a correct process in step S[a]. We show that O returns in S. We assign times to the steps of S, obtaining a run in which every received message has latency at most one. For each i ≥ 0, let ei be the largest index j such that step S[j] receives a message sent in step S[i]; if no such message is received, set ei = i. Partition the step indices into consecutive finite blocks Bk = [bk , bk+1 ), for k ≥ 0, as follows. Set b0 = 0, and choose each bk+1 > bk large enough that ei < bk+1 for every i < bk . By construction, if a message sent in block Bk is later received, then its receive step lies in either block Bk or Bk+1 . Assign times T to the steps in S so that the steps in each block Bk get strictly increasing times in the interval [k/2, (k +1)/2). These intervals are disjoint, ordered by k, and unbounded, so T is strictly increasing and unbounded, and therefore R = (S, T ) is a run of A. Now consider any message sent in block Bk and later received. By the preceding paragraph, its receive step lies in Bk or Bk+1 . Its send time is at least k/2, and its receive time is less than k/2 + 1, so its latency is less than 1. Hence every message that is received has latency at most one in R. Every message sent to a process that takes infinitely many steps is received, and so messages are timely during O in R. Since A has worst-case message delay α, we have δ(O) ≤ α < ∞. Hence O is complete in R, and thus returns in schedule S. Proposition 2.7

B.2

A Finite Worst-Case Message Delay Is an Integer

Next, we prove Proposition 2.8: that a finite worst-case message delay is always a nonnegative integer. The key step is the following rounding lemma. Lemma B.1. Let A be an algorithm. If δ(A) ≤ α for some nonnegative real number α, then δ(A) ≤ ⌊α⌋.

41

∆

Proof. Let k = ⌊α⌋. If α = k, the claim is immediate, so assume k < α < k + 1. Suppose, for the sake of contradiction, that δ(A) > k. Then there exist a run R = (S, T ) of A, and an operation O invoked by a correct process, such that messages are timely during O in R and δR (O) > k. By the definition of worst-case message delay, δR (O) ≤ δ(A) ≤ α < ∞; hence O is complete. Let O be invoked in step S[a] and return in step S[b], so δR (O) = T [b] − T [a]. Putting the inequalities together, we have k < δR (O) ≤ α < k + 1.

(11)

By subtracting T [a] from every entry of T , we may assume without loss of generality that T [a] = 0. Then T [b] = δR (O). We will now retime R to obtain another run R′ with schedule S such that δR′ (O) > α; see Figure 3. Set ∆

η =

k+1−α . 2

Since k < α < k + 1, we have 0 < η < 1/2. We construct a time mapping ϕ : R → R that leaves times at or before 0 unchanged and, for each integer i ≥ 1, compresses the unit interval (i − 1, i] affinely onto the shorter interval (i − η, i]: ( t, t ≤ 0, ∆ ϕ(t) = Affine(i−1,i]→(i−η,i] (t), i − 1 < t ≤ i for some i ≥ 1. Then ϕ is strictly increasing and unbounded. ∆ ∆ Define the infinite sequence T ′ by T ′ [i] = ϕ(T [i]), and let R′ = (S, T ′ ). Since ϕ is strictly increasing and unbounded, R′ is a run of A; moreover, it has the same correct processes as R. By construction, IR′ (O) = [T ′ [a], T ′ [b]] = [ϕ(T [a]), ϕ(T [b])] = [0, ϕ(δR (O))]. Claim B.2. Messages are timely during O in R′ . Proof. Fix an arbitrary message m sent during O in R′ to a process that takes infinitely many steps. Let s < t denote, respectively, the send and receive times of m in R. Since T ′ = ϕ ◦ T , its send and receive times in R′ are ϕ(s) and ϕ(t), respectively. Thus, ϕ(0) ≤ ϕ(s) ≤ ϕ(δR (O)). Because ϕ is strictly increasing, this implies 0 ≤ s ≤ δR (O), so m is sent during O in R. Since messages are timely during O in R, δR (m) = t − s ≤ 1. It remains to show that δR′ (m) = ϕ(t) − ϕ(s) ≤ 1. Given that 0 < t − s ≤ 1, there are three cases for the positions of s and t, exemplified by messages labeled 1 , 2 , and 3 in Figure 3: 1. If s = 0, then 0 < t ≤ 1, and we get ϕ(t) − ϕ(s) = ϕ(t) ≤ ϕ(1) = 1. 2. If s, t ∈ (i − 1, i] for some i ≥ 1, then since ϕ is affine on (i − 1, i] with slope η, ϕ(t) − ϕ(s) = η(t − s) ≤ η < 1. 3. Otherwise, s ∈ (i − 1, i] and t ∈ (i, i + 1] for some i ≥ 1. Then     ϕ(t) − ϕ(s) = (i + 1 − η) + η(t − i) − (i − η) + η(s − (i − 1)) = 1 + η(t − s − 1) ≤ 1. Thus, δR′ (m) ≤ 1 in every case. Since m was arbitrary, messages are timely during O in R′ .

Claim B.2

Claim B.3. δR′ (O) > α. Proof. By (11), δR (O) ∈ (k, k + 1]. Since ϕ maps (k, k + 1] onto (k + 1 − η, k + 1], it follows that ϕ(δR (O)) > k + 1 − η. Therefore, δR′ (O) = ϕ(δR (O)) − ϕ(0) > k + 1 − η = 42

k+1+α > α. 2

Claim B.3

By the first claim and the definition of worst-case message delay, δR′ (O) ≤ δ(A) ≤ α, contradicting the second claim. Hence, δ(A) ≤ k = ⌊α⌋. Lemma B.1 Proposition 2.8, which we restate below, immediately follows from this lemma. Proposition 2.8. If δ(A) < ∞, then δ(A) = k for some nonnegative integer k. Proof. Let the algorithm’s worst-case message delay be α < ∞. Since operation latencies are nonnegative, we have α ≥ 0. By Lemma B.1, the algorithm’s worst-case message delay is at most ⌊α⌋, so α ≤ ⌊α⌋. Since always ⌊α⌋ ≤ α, it follows that α = ⌊α⌋. Thus α is a nonnegative integer. Proposition 2.8

C

Auxiliary Results for Latency Lower Bounds

C.1

Proofs of the Loquacious-Transformation Lemmas

We prove the two loquacious-transformation lemmas in turn, beginning with crash failures and then adapting the argument to Byzantine failures. C.1.1

Crash Failures

We first prove Lemma 4.20 from Section 4, restated below for convenience. Lemma 4.20. In a system with crash failures, let A be an implementation of TS. Then there exists a loquacious implementation A′ of TS such that δ(A′ ) ≤ δ(A). Proof. We construct an algorithm A′ in which each process simulates its counterpart in A but broadcasts one packed message in every step. A packed message encodes a finite, possibly empty set of pairs (m, q), where m is an original message of A and q is its destination. For each process p, we define the automaton A′p that A′ assigns to p in terms of the automaton Ap that A assigns to p. The local states and initial state of A′p are those of Ap . From every state s, set M ′ of received messages, and operation invocation (if any), A′p has a unique transition, which: • extracts from the packed messages in M ′ the set M of original messages paired with destination p; • follows the unique transition t of Ap from state s on M and the same operation invocation, if any, moving to the state that t moves to; • broadcasts the packed message containing the pair (m, q) for every original message m that t sends to a process q; and • returns the same value as t, if t returns from an operation. By construction, A′ is loquacious. Given a schedule S ′ of A′ , define an infinite sequence S step by step. For each i, let p be the process that takes step S ′ [i]. Step S[i] is taken by p and is defined as follows: • S[i] invokes an operation iff S ′ [i] does; • for every process q, step S[i] receives from q precisely those original messages m for which (m, p) appears in a packed message received from q in S ′ [i]; • for every process q, step S[i] sends to q precisely those original messages m for which (m, q) appears in the packed message broadcast in S ′ [i]; and • S[i] returns from an operation with value v iff S ′ [i] does with the same value. We now isolate the properties of S that we will later need. 43

Claim C.1. Let S be defined as above from S ′ . Then: (a) For every i, steps S[i] and S ′ [i] are taken by the same process and have the same invocation and return. (b) The same processes take infinitely many steps in S as in S ′ . (c) Every process correct in S ′ is correct in S.5 (d) If a message sent in S[i] is received in S[j], then some message sent in S ′ [i] is received in S ′ [j]. (e) S is a schedule of A. Proof. An induction on i shows that every step S[i] follows A: It performs precisely the transition of A that S ′ [i] simulates, from the same local state. Moreover, corresponding steps of S and S ′ are taken by the same process and have the same invocation and return. Thus (a) and (b) hold. Since every step of S follows A, (b) implies (c). For every original message m sent to q in S[i], let m′ be the copy of the packed message broadcast in S ′ [i] that is sent to q. By construction, m′ contains the pair (m, q), and m is received in S[j] iff m′ is received in S ′ [j], proving (d). Together with (b) and the fact that S ′ is a schedule, this correspondence implies that in S, every received message was sent earlier, no message is received more than once, and every message sent to a process that takes infinitely many steps is eventually received. Moreover, (b) implies that at least n − f processes take infinitely many steps in S, since they do in S ′ . By (a), each process’s operations remain sequential. Thus S is a schedule of A, proving (e). Claim C.1 Claim C.2. A′ is an implementation of TS. Proof. Let S ′ be any schedule of A′ and let S be as defined above. By Claim C.1(e), S is a schedule of A. By Claim C.1(a), S and S ′ have the same history. Since A satisfies the safety condition (CT1), this history is linearizable with respect to TS, so A′ satisfies (CT1) as well. To show that A′ satisfies the liveness condition (CT2), let O′ be any operation in S ′ invoked by a correct process p. By Claim C.1(a), S has a corresponding operation O invoked by the same process p. By Claim C.1(c), p is correct in S as well. Since S is a schedule of A, which implements TS, O eventually returns. By Claim C.1(a), the corresponding return occurs in S ′ , so O′ eventually returns as well. Claim C.2 Claim C.3. δ(A′ ) ≤ δ(A). Proof. Let R′ = (S ′ , T ′ ) be any run of A′ , and let R = (S, T ′ ), where S is as defined above. We first verify that R is a run of A: • By Claim C.1(e), S is a schedule of A. • Since R′ is a run, T ′ is non-decreasing and unbounded. • If a message is sent in S[i] and received in S[j], then Claim C.1(d) gives a message sent in S ′ [i] and received in S ′ [j]; hence T ′ [i] < T ′ [j]. • Likewise, if S[i] and S[j], with i < j, are taken by the same process, then Claim C.1(a) implies that S ′ [i] and S ′ [j] are taken by the same process; hence again T ′ [i] < T ′ [j]. Thus all conditions of the definition of a run are satisfied. Let O′ be any operation in R′ invoked by a correct process p such that messages are timely during O′ . By Claim C.1(a), S has a corresponding operation O invoked by p, with the same invocation- and return-step indices. Since R and R′ share the time sequence T ′ , I(O) = I(O′ )

and hence

δ(O) = δ(O′ ).

5 Of course, in the crash-failure model, a process is correct exactly when it takes infinitely many steps. We nevertheless state this separately from the preceding property so that both remain true in the Byzantine model, where a process may take infinitely many steps yet be faulty.

44

By Claim C.1(c), p is correct in R as well. We now show that messages are timely during O in R. Let m be any message sent during O to a process q that takes infinitely many steps in S, so m is eventually received. Suppose it is sent in step S[i] and received in step S[j]. By Claim C.1(d), some message m′ is sent in S ′ [i] and received in S ′ [j], and so δ(m′ ) = T ′ [j] − T ′ [i] = δ(m). By Claim C.1(a), step S ′ [j] is taken by q, so m′ is sent to q. By Claim C.1(b), q takes infinitely many steps in S ′ . Moreover, because m and m′ are sent at the same time and I(O) = I(O′ ), message m′ is sent during O′ . Because messages are timely during O′ in R′ , we have δ(m) = δ(m′ ) ≤ 1. Thus every message sent during O to a process that takes infinitely many steps has latency at most one, so messages are timely during O in R. Since O is invoked by a correct process, the definition of δ(A) yields δ(O′ ) = δ(O) ≤ δ(A). Taking the supremum over all such R′ and O′ yields δ(A′ ) ≤ δ(A).

Claim C.3

The construction and the latter two claims establish the result.

Lemma 4.20

C.1.2

Byzantine Failures

We next restate Lemma 7.11 from Section 7.3.1 and sketch its proof. Lemma 7.11 (Byzantine version of Lemma 4.20). In a system with Byzantine processes, let A be an implementation of TS. Then there exists a loquacious implementation A′ of TS such that δ(A′ ) ≤ δ(A). Proof sketch. We reuse the construction of A′ and the transformation of S ′ into S from the proof of the crash-failure counterpart, Lemma 4.20, modifying only how the messages sent in S[i] are defined: For every process q, step S[i] sends to q precisely those original messages m for which (m, q) appears in a packed message sent to q in S ′ [i]. This modification is necessary because the crash-failure transformation refers to the packed message broadcast in S ′ [i], whereas a Byzantine process may send different messages to different recipients or send no message at all. Because the construction of A′ is unchanged, the algorithm is loquacious as before. Moreover, under the modified transformation, Claim C.1 continues to hold under Byzantine failures. We omit the details of the argument, but two points merit mention: • Malformed messages in S ′ are simply ignored, as desired. This is because both the construction of A′ and the transformation of S ′ into S consider only (valid) packed messages. • A process that is faulty in S ′ and takes infinitely many steps may nevertheless be correct in S, if all of its transformed steps happen to conform to A. This is harmless: Claim C.1 requires only that every process correct in S ′ also be correct in S. The subsequent arguments use this implication only in that direction. Let S ′ be any schedule of A′ , and let S be the sequence obtained by the modified transformation. Since b that is linearizable with respect to TS and agrees A satisfies the safety condition (BT1), there is a history H with the history of S on the processes correct in S. By Claim C.1, S and S ′ have the same history, and b agrees with the history of S ′ on the processes correct every process correct in S ′ is correct in S. Hence H ′ ′ in S , so A satisfies the safety condition (BT1). The liveness and latency arguments carry over unchanged, using (BT2) for the liveness condition. Lemma 7.11

45

O S

a

T

T [a]

S

a

T′

T [a]

b T [b] − 1

τ

T [b]

τ +1

µ

τ +1

µ

b T [b] − 1 O

τ

T [b]

Figure 4: Proof of Lemma C.5: retiming the run R = (S, T ) (top) into the run R′ = (S, T ′ ) (bottom). Both runs share the same schedule S, which contains an invocation at step S[a] and a corresponding response at step S[b]. Each horizontal line is a “unified” timeline depicting steps taken by all processes. Dots are steps, arcs are messages (red: latency exceeding 1; black: at most 1), and dashed portions of a timeline indicate no step is taken. Observe that in R, messages are ultimately timely, but not timely, during the operation (denoted O). The shaded band is the ultimate interval (T [b] − 1, T [b]]. Time τ is the earliest sending time of a message in Mult ; time µ is the latest receiving time of such a message. T ′ is constructed from T by compressing the time interval (T [b], µ] into (T [b], τ +1], pulling late message receptions to within 1 time unit of the send times. The operation O has the same latency in R′ as in R, but messages are timely during O in R′ .

C.2

Weaker Timeliness Requirements

The definitions and results in this subsection apply in both the crash-failure and Byzantine settings, with “correct” interpreted in the respective sense. Recall from Definition 2.6 that an algorithm’s worst-case message delay bounds the latency of an operation if messages are timely (i.e., have latency at most one) throughout the operation. This bound should continue to hold under a weaker requirement that exempts messages sent within one unit of time before the operation returns. Indeed, if such a message is untimely, it arrives only after the operation has returned and cannot affect the timing of the return step. To state this requirement more conveniently, we extend timeliness from operations to arbitrary time intervals: Given a run R = (S, T ) and an interval I ⊆ R, we say that messages are timely during I in R if δ(m) ≤ 1 for every message m sent at a time in I to a process that takes infinitely many steps in S. Timeliness during an operation O (Definition 2.5) is the special case I = IR (O). Definition C.4 formalizes the weaker requirement described above, called ultimate timeliness; Lemma C.5 shows that the message-delay bound still applies. Definition C.4 (Ultimate timeliness). Let R = (S, T ) be a run, and let O be an operation in R. We say that messages are ultimately timely during O in R if either of the following applies: (1) O is incomplete, and messages are timely during O in R; or (2) O is complete, having been invoked in step S[a] and returned in step S[b], and messages are timely during [T [a], T [b] − 1] in R. Note that if δ(O) < 1, then messages are vacuously ultimately timely during O. Lemma C.5. Let A be an algorithm, let R be a run of A, and let O be an operation in R invoked by a correct process. If messages are ultimately timely during O in R, then δ(O) ≤ δ(A).

46

Proof. Write R = (S, T ). If messages are timely during O in R, the claim follows directly from the definition of worst-case message delay, so assume otherwise. Since ultimate timeliness coincides with timeliness for an incomplete operation (Definition C.4(1)), O must be complete. Let O be invoked in step S[a] and return in step S[b]. We will construct a run R′ = (S, T ′ ) such that δR′ (O) = δR (O) and messages are timely during O in R′ ; see Figure 4. Let M denote the set of messages sent during O in R to a process that takes infinitely many steps. Since S is a schedule, every message in M is eventually received. Let Mult ⊆ M consist of the messages sent during the ultimate interval (T [b] − 1, T [b]]. Since T is non-decreasing and unbounded, only finitely many steps occur during this interval, hence Mult is finite. Because messages are ultimately timely but not timely during O in R, some message in Mult has latency exceeding 1, so Mult ̸= ∅. Let τ and µ be, respectively, the earliest send time and latest receive time of a message in Mult . These times are well-defined because Mult is finite, nonempty, and consists of messages that are received. By definition, τ > T [b] − 1. Moreover, if some message m ∈ Mult with δR (m) > 1 is sent at time s and received at time r, then µ ≥ r > s + 1 ≥ τ + 1. Thus, T [b] < τ + 1 < µ. We “retime” R by compressing the interval (T [b], µ] into (T [b], τ + 1] and leaving other times unchanged. Define ϕ : R → R by   t ≤ T [b], t, ∆ ϕ(t) = Affine(T [b],µ]→(T [b],τ +1] (t), T [b] < t ≤ µ,   t, t > µ. Since T [b] < τ + 1 < µ, the map ϕ is strictly increasing and unbounded. ∆ Define T ′ [i] = ϕ(T [i]). Because T is non-decreasing and unbounded, so is T ′ . Moreover, since ϕ is strictly increasing, T [i] < T [j] iff T ′ [i] < T ′ [j] for all indices i and j. Thus, R′ = (S, T ′ ) is a run of A with the same schedule as R. Since T [a] ≤ T [b], we have T ′ [a] = ϕ(T [a]) = T [a] and T ′ [b] = ϕ(T [b]) = T [b], so δR′ (O) = δR (O). It remains to show that messages are timely during O in R′ . Because ϕ is strictly increasing and fixes T [a] and T [b], for any time t we have t ∈ IR (O)

⇐⇒

ϕ(t) ∈ IR′ (O).

(12)

Fix any message m sent during O in R′ to a process that takes infinitely many steps. Let S[i] be its send ∆ step and set s = T [i]. Its send time in R′ is ϕ(s) ∈ IR′ (O), so (12) implies s ∈ IR (O), i.e., m is also sent ∆ during O in R. Hence m ∈ M . Let S[j] be its receive step and set r = T [j]. Since s ≤ T [b], we have ϕ(s) = s, and therefore δR′ (m) = ϕ(r) − ϕ(s) = ϕ(r) − s. There are two cases, depending on whether m was sent before or during the ultimate interval: 1. If s ≤ T [b] − 1, ultimate timeliness during O in R implies r − s ≤ 1, and hence r ≤ T [b]. Thus ϕ(r) = r, so δR′ (m) = ϕ(r) − s = r − s ≤ 1. 2. If s > T [b] − 1, then m ∈ Mult , so s ≥ τ and r ≤ µ. Therefore, δR′ (m) = ϕ(r) − s ≤ ϕ(µ) − τ = (τ + 1) − τ = 1. In both cases, δR′ (m) ≤ 1. So every message sent during O in R′ to a process that takes infinitely many steps has latency at most one, meaning messages are timely during O in R′ . By the definition of worst-case message delay, δR′ (O) ≤ δ(A). Since δR (O) = δR′ (O), the claim follows. Lemma C.5

47

We can weaken the timeliness requirement once more. Write t for the time a complete operation returns. The idea is to additionally exempt messages sent during the time interval (t − 2, t − 1] to processes other than the invoker p. Any run that meets this weaker requirement can be transformed into one in which messages are ultimately timely during the operation: We move the receipt of each exempted message that arrived late to just after time t − 1. Since p is not the recipient of any such message, this transformation leaves p’s steps—and hence the operation’s return time and latency—unchanged, so Lemma C.5 bounds the latency. Definition C.6 states this weaker requirement precisely and names it penultimate timeliness; Lemma C.7 then shows that the message-delay bound still applies under it. Definition C.6 (Penultimate timeliness). Let R = (S, T ) be a run, and let O be an operation in R. We say that messages are penultimately timely during O in R if either of the following applies: (1) O is incomplete and messages are timely during O in R; or (2) O is complete, having been invoked by a process p in step S[a] and returned in step S[b]; writing ∆

Iearly = [T [a], T [b] − 2]

and

∆

Ipen = [T [a], T [b] − 1] \ Iearly ,

both of the following conditions apply: (a) messages are timely during Iearly in R; and (b) if p takes infinitely many steps in S, then every message sent to p during Ipen has latency at most one in R. Note that condition (2)(a) holds vacuously when δ(O) < 2, and condition (2)(b) holds vacuously when p crashes or when δ(O) < 1. In particular, if δ(O) < 1, then messages are penultimately timely during O. Lemma C.7. Let A be an algorithm, let R be a run of A, and let O be an operation in R invoked by a correct process. If messages are penultimately timely during O in R, then δ(O) ≤ δ(A). Proof. Write R = (S, T ). If messages are timely during O in R, the claim follows directly from the definition of worst-case message delay, so assume otherwise. Since penultimate timeliness coincides with timeliness for an incomplete operation (Definition C.6(1)), O must be complete. Let O be invoked by a correct process p in step S[a] and return in step S[b]. If messages are ultimately timely during O in R, the claim follows from Lemma C.5, so assume messages are not ultimately timely during O in R. This means δ(O) ≥ 1, and hence a < b. Proof plan. The remainder of the proof is devoted to constructing a run R′ of A in which O is invoked by a correct process, messages are ultimately timely during O, and δR′ (O) = δR (O); see Figure 5. Given such a run, Lemma C.5 would give δR (O) = δR′ (O) ≤ δ(A), completing the proof. Since messages are already timely during Iearly in R, only messages sent during Ipen to processes that take infinitely many steps can prevent ultimate timeliness. Let Mpen denote the set of such messages; we must ensure that each message in Mpen has latency at most one in R′ . A message in Mpen received in S[b] is received by p. Because p is correct and hence takes infinitely many steps, condition (2)(b) already bounds the message’s latency by one; we will leave such a message alone. We will deal with the remaining messages in Mpen in two stages of construction: e in which every step preceding S[b] occurs early • First, we will retime R into an intermediate run R enough to make those messages received before S[b] timely. This retiming also clears a stretch of time that precedes S[b] and yet lies less than one time unit after every message in Mpen is sent. • Then, we will insert into that stretch receive steps for the messages received after S[b]. Such steps may be placed before S[b] because they are taken by processes other than p and so commute with S[b]. This yields the desired run R′ . We now give the full proof following the plan. 48

S

a

T

T [a] T [b] − 2

S

a

Te

T [a] T [b] − 2

O

τ

b

T [b] − 1

T [b]

b τ

T [b] − 1

λ

τ +1

T [b]

O S′

a

T′

T [a] T [b] − 2

b+k τ

T [b] − 1 O

λ

τ +1

T [b]

Figure 5: Proof of Lemma C.7: transforming the run R = (S, T ) (top) into the run R′ = (S ′ , T ′ ) e = (S, Te) (middle). Each horizontal line is a “unified” timeline (bottom), by way of the intermediate run R depicting steps taken by all processes. Dots are steps, arcs are messages (red: latency exceeding 1; black: at most 1), and dashed portions indicate no step is taken. Top: A correct process p invokes the operation O in step S[a] and returns in step S[b]. Messages are penultimately timely, but not ultimately timely, during O in R. τ is the earliest sending time of a message in Mpen , and λ ∈ (T [b] − 1, τ + 1). Penultimate timeliness forbids a red arc from the shaded band into step S[b], which is taken by p; hence the “▲” step is taken by e keeps the schedule S and compresses the time interval (T [b] − 1, T [b]] a process other than p. Middle: R into (T [b] − 1, λ] for the steps before the return, leaving the return step S[b] at time T [b]. δRe (O) = δR (O). e inserts k receive steps “ ” in the time Bottom: R′ keeps the steps in S[0..(b − 1)] at their times in R, interval (λ, τ + 1) for the messages in Mlate , keeps the return step at time T [b], and continues with a new infinite suffix (the wavy portion). In R′ , the operation O is invoked in step S ′ [a] = S[a] and returns in step S ′ [b + k] = S[b]. Messages are ultimately timely during O in R′ . Thus Lemma C.5 gives δR′ (O) ≤ δ(A); since the construction preserves the latency of O, we have δR (O) = δRe (O) = δR′ (O) ≤ δ(A), as desired.

49

Setup. Let Iearly and Ipen be as in Definition C.6(2) for O; recall that they partition [T [a], T [b] − 1]. Let M denote the (finite) set of messages in R sent during [T [a], T [b] − 1] to a process that takes infinitely many steps, and let Mpen ⊆ M consist of those sent during Ipen . Recall that by condition (2)(a), messages are timely during Iearly in R. Since messages are not ultimately timely during O, Mpen must contain a message whose latency exceeds one, hence Mpen ̸= ∅. Let τ be the earliest send time of a message in Mpen , so that T [a] ≤ τ ≤ T [b] − 1 and τ > T [b] − 2. Since τ + 1 > T [b] − 1, we may fix an arbitrary time λ ∈ (T [b] − 1, τ + 1), obtaining T [b] − 1 < λ < τ + 1 ≤ T [b].

(13)

An intermediate run. We now retime R so that every step preceding the response step S[b] occurs at time at most λ: For such steps we will compress the interval (T [b] − 1, T [b]] into (T [b] − 1, λ], while S[b] and every later step keeps its time. To do so, define ϕ : (−∞, T [b]] → R by ( t, t ≤ T [b] − 1, ∆ ϕ(t) = Affine(T [b]−1,T [b]]→(T [b]−1,λ] (t), T [b] − 1 < t ≤ T [b]. By (13), the map ϕ is strictly increasing; ϕ(t) = t for all t ≤ T [b] − 1; and the range of ϕ is contained in (−∞, λ]. Define the infinite sequence Te by ( ϕ(T [i]), i < b, ∆ Te[i] = T [i], i ≥ b. The sequence Te is non-decreasing and unbounded. Furthermore, it can be verified that T [i] < T [j] only e = (S, Te) is a run of A with the same schedule, and hence the same correct if Te[i] < Te[j]. Thus, R processes, as R. Since a < b and T [a] ≤ T [b] − 1, we have Te[a] = ϕ(T [a]) = T [a]; also, Te[b] = T [b]. Hence δRe (O) = δR (O). Since Te[a] = T [a] and Te[b] = T [b], and since Te agrees with T at every step whose time is at most T [b] − 1 e sent during [Te[a], Te[b] − 1] that timeliness constrains, and in either run, M is also the set of messages in R each has the same send time in both runs. Let Mlate ⊆ M consist of the (finitely many) messages received in a step S[j] with j > b. Claim C.8. Fix a message m ∈ M with send time s, and let S[i] and S[j] be its send and receive steps. Then: (a) i < b and T [i] = Te[i] = s. (b) If s ≤ T [b] − 2, then T [j] ≤ s + 1 ≤ T [b] − 1 and j < b. (c) If s > T [b] − 2, then s ∈ Ipen , so m ∈ Mpen and s ≥ τ . Proof. We prove each part in turn. (a) The monotonicity of Te, with Te[i] = s ≤ T [b] − 1 < Te[b], yields i < b. The definitions of ϕ and Te then give T [i] = Te[i] = s. (b) Since s ∈ Iearly , condition (2)(a) of penultimate timeliness gives δR (m) ≤ 1, and hence T [j] ≤ T [i]+1 = s + 1 ≤ T [b] − 1 < T [b]. The monotonicity of T therefore implies j < b. (c) Since s ∈ [T [a], T [b] − 1] and s > T [b] − 2, we have s ∈ Ipen and hence m ∈ Mpen . By the definition of τ , it follows that s ≥ τ . Claim C.8 e the following hold: Claim C.9. In R, 50

(a) Every i < b satisfies Te[i] ≤ λ, while Te[b] − 1 < λ < τ + 1 ≤ Te[b]. (b) Every message m ∈ Mlate is sent to a process other than p, in a step S[i] with i < b and Te[i] ≥ τ . (c) Every message in M \ Mlate is received in a step S[j] with j ≤ b and has latency at most one. Proof. (a) For every i < b, we have Te[i] = ϕ(T [i]) ≤ λ because the range of ϕ is contained in (−∞, λ]. Moreover, since Te[b] = T [b], the displayed inequalities are a restatement of (13). ∆ (b) Fix a message m ∈ Mlate , let S[i] and S[j] be its send and receive steps, and write s = Te[i]. The definition of Mlate gives j > b. Claim C.8(a) gives i < b.

Claim C.8(b) then rules out s ≤ T [b] − 2, so Claim C.8(c) applies and gives s ∈ Ipen and s ≥ τ . Finally, if m were sent to p, then S[b] and S[j] would both be steps of p, implying T [j] > T [b]. But p takes infinitely many steps and s ∈ Ipen , so condition (2)(b) of penultimate timeliness would yield T [j] ≤ s + 1 ≤ T [b], a contradiction. (c) Fix a message m ∈ M \ Mlate with send time s, and let S[i] and S[j] be its send and receive steps. Claim C.8 applies to m, and the definition of Mlate gives j ≤ b. We bound δRe (m) = Te[j] − s in three cases. If s ≤ T [b] − 2, then Claim C.8(b) gives j < b and T [j] ≤ s + 1 ≤ T [b] − 1. Thus ϕ(T [j]) = T [j], and δRe (m) = T [j] − s ≤ 1. Now suppose s > T [b] − 2. By Claim C.8(c), s ∈ Ipen and s ≥ τ . If j < b, then Te[j] ≤ λ by part (a), so δRe (m) ≤ λ − τ < 1. If instead j = b, then m is received by p, which takes infinitely many steps, so condition (2)(b) of penultimate timeliness gives T [b] − s ≤ 1. Hence δRe (m) = T [b] − s ≤ 1. Claim C.9 ∆

Inserting receive steps. Let σ0 = S[0..(b − 1)], a schedule prefix of A. By Claim C.9(b), every message in Mlate is sent in σ0 to a process other than p. Moreover, its receive step in S has index greater than b, so it has not yet been received by the end of σ0 . We may therefore extend σ0 by a finite sequence σ1 of steps, all taken by processes other than p, in which every message in Mlate is received: A recipient that is correct in S takes a step according to A, and a recipient that is faulty in S—possible only under Byzantine failures, since these recipients take infinitely ∆ many steps—takes an arbitrary step receiving the message. Write k = |σ1 |. Because σ1 contains no step of p and step S[b] is a step of p, ∆ σ ′ = σ0 ◦ σ1 ◦ ⟨S[b]⟩ is a schedule prefix of A by commutativity. Extend σ ′ to a schedule S ′ of A such that exactly the processes that take infinitely many steps in S do so in S ′ , and every correct process in S is correct in S ′ . In particular, p is correct in S ′ . By construction, S ′ [0..(b − 1)] = S[0..(b − 1)],

S ′ [b..(b + k − 1)] = σ1 ,

S ′ [b + k] = S[b].

e place the k inserted Assigning times. To construct R′ , we keep the steps in S[0..(b−1)] at their times in R, e steps in the interval (λ, τ + 1), and keep the return step at time T [b]. Specifically, define  e  i < b, T [i], ∆ ′ b ≤ i < b + k, T [i] = Affine(b−1,b+k)→(λ,τ +1) (i),  Affine (i), i ≥ b + k. [b+k,+∞)→[Te[b],+∞) By Claim C.9(a), every step in S[0..(b − 1)] has time at most λ. The inserted steps have strictly increasing times in (λ, τ + 1), the return step has time Te[b] ≥ τ + 1, and all subsequent steps have strictly increasing 51

times exceeding Te[b]. Thus T ′ is non-decreasing and unbounded. Moreover, all required strict inequalities e or follow from these strict separations. Thus R′ = (S ′ , T ′ ) is a run of A. are either inherited from R ′ In R , the operation O is invoked in step S ′ [a] = S[a] and returns in step S ′ [b + k] = S[b]; it is invoked by p, which is correct in S ′ . Since T ′ [a] = Te[a] and T ′ [b + k] = Te[b], we have δR′ (O) = δRe (O). Claim C.10. Messages are ultimately timely during O in R′ . Proof. Fix a message m sent at a time in [T ′ [a], T ′ [b + k] − 1] = [Te[a], Te[b] − 1] to a process that takes infinitely many steps in S ′ , and let S ′ [i] be its send step. By the definition of T ′ and Claim C.9(a), every ℓ ≥ b satisfies T ′ [ℓ] > λ > Te[b] − 1. Hence i < b, so S ′ [i] = S[i] and T ′ [i] = Te[i]; in particular, m is also sent e with the same send time, and by the choice of S ′ its recipient is the same in both schedules and takes in R, infinitely many steps in each. Thus m ∈ M . • If m ∈ / Mlate , then by Claim C.9(c), m is received in a step S[j] with j ≤ b and δRe (m) ≤ 1. Its receive step in R′ is S ′ [j] if j < b, and S ′ [b + k] if j = b; in either case, its receive time is the same in R′ as e Therefore δR′ (m) = δ e (m) ≤ 1. in R. R • If m ∈ Mlate , then Claim C.9(b) gives T ′ [i] = Te[i] ≥ τ . By construction, m is received in an inserted step S ′ [j ′ ] with b ≤ j ′ < b + k; the definition of T ′ therefore gives T ′ [j ′ ] < τ + 1. Hence δR′ (m) = T ′ [j ′ ] − T ′ [i] < (τ + 1) − τ = 1. Since m was arbitrary, messages are ultimately timely during O in R′ . By Lemma C.5, δR′ (O) ≤ δ(A). Since δR (O) = δRe (O) = δR′ (O), the claim follows.

C.3

Claim C.10 Lemma C.7

Proofs of the Completion Lemmas

We prove the crash- and Byzantine-failure completion lemmas in turn. C.3.1

Crash Failures

We first prove the crash-failure completion lemma using penultimate timeliness; its statement is restated below. Lemma 4.21. In a system with crash failures, let A be a loquacious algorithm with δ(A) ≤ 2. Let p be a process, and let Q be a set of processes such that |Q| = n − f and p ∈ Q. Suppose that σ is a schedule prefix of A in which the following hold: 1. Process p invokes an operation and broadcasts a message m in step σ[a]. 2. For each q ∈ Q, process q receives message m and broadcasts a message mq in step σ[jq ]. 3. Process p receives the set of messages {mq : q ∈ Q} in step σ[b]. 4. Between steps σ[a] and σ[b], inclusive, the only steps are those specified above. Then the operation invoked by p in step σ[a] returns no later than step σ[b]. Proof. In a system with crash failures, let A be a loquacious algorithm with δ(A) ≤ 2, and let σ be a schedule prefix of A that satisfies the assumptions in the lemma statement. Suppose, for the sake of contradiction, that process p has not returned from the operation by step σ[b]. Extend the prefix σ[0..b] to a schedule S of A in which every process in Q takes infinitely many further steps and receives every message sent to it, while every remaining process takes no further steps. Since p is correct in S and δ(A) < ∞, Proposition 2.7 implies that the operation invoked in step S[a] = σ[a] eventually returns, in some step S[c] with c > b. 52

s r m

r

q

mq

m

mp

p a T

0

1/2

3/4

c

b

O 1

3/2

7/4

2

5/2

Figure 6: Proof of Lemma 4.21. Let A be a loquacious algorithm with δ(A) ≤ 2, and suppose toward a contradiction that the operation O, invoked by p in step a, has not returned by step b. Extend the schedule prefix so that exactly the processes in Q are correct; then O returns in some step c > b, and the times T give δ(O) = T [c] − T [a] = 5/2. The figure depicts the instance n = 4, f = 1, and Q = {p, q, r}, in which p, q, and r are correct and s crashes; in general |Q| = n − f . The shaded bands show the two intervals from Definition C.6(2) of penultimate timeliness: (a) Iearly = [0, 1/2]; and (b) Ipen = (1/2, 3/2]. The figure shows only the messages to which these conditions apply; each has latency less than 1. So messages are penultimately timely during O, and Lemma C.7 gives δ(O) ≤ δ(A) ≤ 2, contradicting δ(O) = 5/2. Now, define the time sequence T as follows (see Figure 6):  i ≤ a,  Affine(−∞,a]→(−∞,0] (i),  Affine (i), a < i < b, ∆ (a,b)→(3/4,1) T [i] = Affine[b,c]→[7/4,5/2] (i), b ≤ i ≤ c,    Affine(c,+∞)→(5/2,+∞) (i), i > c. It can be verified that T is strictly increasing and unbounded, so R = (S, T ) is a run of A. Let O denote the operation in R invoked in step S[a] and returning in step S[c]. It follows that δ(O) = T [c] − T [a] = 5/2. Claim. Messages are penultimately timely during O in R. Proof. Since O is complete, we must verify conditions (2)(a) and (2)(b) of Definition C.6. • For condition (2)(a), consider the interval   1 Iearly = [T [a], T [c] − 2] = 0, 2

(blue interval in Figure 6).

The only step in this interval is S[a], so the messages sent during this interval to a process that takes infinitely many steps are precisely the copies of m sent in step S[a] to processes in Q. By assumption 2, each such message is received in some step S[jq ] with a < jq < b, and hence before time 1. Since these messages are sent at time 0, each has latency less than 1. • For condition (2)(b), we have  Ipen = [T [a], T [c] − 1] \ Iearly =

1 3 , 2 2

 (orange interval in Figure 6).

Since p takes infinitely many steps, we must examine the messages sent in this interval to p. Let m b be such a message, sent in step S[j]. Since T [a] = 0 <

1 3 7 < T [j] ≤ < = T [b] 2 2 4 53

and T is strictly increasing, we have a < j < b. So by assumptions 2 and 4, we have m b = mq for some q ∈ Q. By assumption 3, message m b is received in step S[b]. Furthermore, j > a implies T [j] > 3/4 by the definition of T . Therefore, δ(m) b = T [b] − T [j] <

7 3 − = 1. 4 4

By Lemma C.7, the claim implies δ(O) ≤ δ(A) ≤ 2. This contradicts δ(O) = 5/2. C.3.2

Claim

Lemma 4.21

Byzantine Failures

We next derive the Byzantine variant from the same argument; its statement is also restated below (with the differences from the crash version underlined). Lemma 7.12 (Byzantine version of Lemma 4.21). In a system with Byzantine processes, let A be a loquacious algorithm with δ(A) ≤ 2. Let p be a process, and let Q be a set of processes such that |Q| = n − f and p ∈ Q. Suppose that σ is a schedule prefix of A in which the following hold: 1. Process p invokes an operation and broadcasts a message m in step σ[a]. 2. For each q ∈ Q, process q receives m and broadcasts a message mq in step σ[jq ]. 3. Process p receives the set of messages {mq : q ∈ Q} in step σ[b]. 4. Between steps σ[a] and σ[b], inclusive, the only steps are those specified above. 5. Processes in Q follow the algorithm A throughout σ[0..b]. Then the operation invoked by p in step σ[a] returns no later than step σ[b]. Proof. The proof of Lemma 4.21 applies with only one change: We must justify its initial extension of σ[0..b] to a schedule of A. Since every process in Q follows A throughout σ[0..b], we can extend this prefix to a schedule of A by letting these processes take infinitely many further steps according to A (and ensuring that every message sent to them is eventually received), and letting the remaining processes take no further steps. In the resulting schedule, the processes in Q are exactly the ones that take infinitely many steps and exactly the correct ones, and so there are n − |Q| = f faulty processes. Because p is correct in the schedule, its operation eventually returns. The remainder of the proof—the time assignment and the verification of penultimate timeliness—applies verbatim and yields the same contradiction. Lemma 7.12

D

Proof of the Two-Delay Lower Bound for Crash Failures

In this section, we prove the two-delay latency lower bound in systems with crash failures from Section 4.3. The proof relies on the following lemma. Lemma D.1. In a system with crash failures, let A be a loquacious algorithm with δ(A) ≤ 1. Suppose that σ is a schedule prefix of A in which some process p: • invokes an operation and broadcasts a message m in step σ[a], and • receives its own message m in step σ[b]. Then the operation invoked by p in step σ[a] returns no later than step σ[b].

54

Proof. Let the worst-case message delay of A be k ≤ 1. Suppose, for the sake of contradiction, that the operation invoked by p in step σ[a] does not return by step σ[b]. By assumption, b > a. Extend σ[0..b] to an (infinite) schedule S of A in which p takes infinitely many steps. Then p is correct in S, and since A has finite worst-case message delay, Proposition 2.7 implies that the operation invoked in step S[a] eventually returns. Let S[c] be its return step, where c > b, and call the complete operation O. Assign times T to the steps in S by setting  i ≤ a,  Affine(−∞,a]→(−∞,0] (i),  Affine (i), a < i ≤ b, ∆ (a,b]→(1/2,3/4] T [i] = Affine(b,c]→(3/4,3/2] (i), b < i ≤ c,    Affine(c,+∞)→(3/2,+∞) (i), i > c. This sequence is strictly increasing and unbounded. Let R = (S, T ) be the resulting run. Since O is complete, we show that messages are penultimately timely during O in R by verifying the two conditions of Definition C.6(2). Condition (2)(a) holds vacuously because T [c] − 2 < T [a]. Since p takes infinitely many steps, condition (2)(b) requires us to consider the messages sent to p during the relevant time interval [0, 1/2]; the only step taken in this interval is S[a]. Since A is loquacious, the only message sent to p in step S[a] is m; by assumption, p receives m in step S[b], with latency T [b] − T [a] = 3/4 ≤ 1. Therefore, by Lemma C.7, δ(O) ≤ k ≤ 1, contradicting the fact that δ(O) = T [c] − T [a] = 3/2. Lemma D.1

We now restate and prove the two-delay latency lower bound. Proposition 4.22. In a system with crash failures, any implementation of TS has worst-case message delay at least two. Proof. Suppose, toward a contradiction, that there is an implementation A of TS whose worst-case message delay is at most one. By Lemma 4.20, we may assume without loss of generality that A is loquacious. By Proposition 3.3, A satisfies ordering (CT1a). Since n ≥ 2, let p and q be distinct processes in the system. Construct a schedule prefix σp of A consisting of two steps, both taken by process p: In the first step, p invokes an operation and broadcasts a message mp ; in the second step, p receives mp . By Lemma D.1, this operation returns by the end of σp —let its return value be xp . Construct σq symmetrically for process q, with return value xq . Note that σp contains only steps of p and σq contains only steps of q, so their concatenation σp ◦ σq is also a schedule prefix of A. Extend σp ◦ σq to a schedule of A; in this schedule, condition (CT1a) implies xp < xq . Similarly, we can extend σq ◦ σp to a schedule of A, yielding xq < xp , a contradiction. Proposition 4.22

55

Related documents

• On Latency-Optimal Implementations of the Timestamp Object#1448360
• Dynamically Quantifying and Improving the Reliability of Distributed Storage Systems#16757
• Real-Time Decentralized Information Processing and Returns to Scale#486191
• Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold#1141665
• Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold#1122198