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 § 12 ). 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 § 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 n \ge2 n ≥ 2 is the number of processes in the system and 1 ≤ f < n 1 \le f < n 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 n > 4 n > 4 and f = 1 f = 1 f = 1 . There, we narrow the optimal latency down to either two or three message delays.
Table 1. Summary of results on implementing the timestamp object (TS), where n ≥ 2 n \ge2 n ≥ 2 is the number of processes in the system and 1 ≤ f < n 1 \le f < n 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.
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.
System Model and Latency under Crash Failures
We first define the system model and latency measure for crash failures; § 6 adapts these definitions to systems with Byzantine processes.
System Model
The system consists of n ≥ 2 n \ge2 n ≥ 2 processes connected pairwise by reliable asynchronous channels. At most f f f processes may crash, where 1 ≤ f < n 1 \le f < n 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 \mathcal{A} A assigns to each process p p p a deterministic automaton A p \mathcal{A}_p A p . Each transition of A p \mathcal{A}_p A p maps process p p p ’s current state, an optional operation invocation, and the received messages to a new state, outgoing messages, and any response to p p p ’s pending operation.
A schedule S S S of A \mathcal{A} A is an infinite sequence of steps, each taken according to A \mathcal{A} A , in which at least n − f n-f n − f processes take infinitely many steps. The processes that take infinitely many steps are correct in S S 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 σ \sigma σ of A \mathcal{A} A is a finite prefix of a schedule of A \mathcal{A} 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.
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. [5 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 [4 Section 2.1] ; see Attiya and Welch [3 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 ) R=(S,T) R = ( S , T ) of A \mathcal{A} A consists of a schedule S S S of A \mathcal{A} A and a non-decreasing, unbounded sequence T T T of real numbers, where T [ j ] T[j] T [ j ] is the time of step S [ j ] S[j] S [ j ] , such that:
if a message sent in step S [ j ] S[j] S [ j ] is received in step S [ k ] S[k] S [ k ] , then T [ j ] < T [ k ] T[j] < T[k] T [ j ] < T [ k ] ; and
if steps S [ j ] S[j] S [ j ] and S [ k ] S[k] S [ k ] with j < k j < k j < k are taken by the same process, then T [ j ] < T [ k ] T[j] < T[k] T [ j ] < T [ k ] .
A process is correct in R R R if it is correct in S S 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 § 1 , in which local computation takes no time.
We now define the latency of a message and of an operation in a run R R R .
Definition 2.2 (Message latency). In a run R = ( S , T ) R=(S,T) R = ( S , T ) , if a message m m m is sent in step S [ j ] S[j] S [ j ] and received in step S [ k ] S[k] S [ k ] , then its latency in R R R is δ R ( m ) ≜ T [ k ] − T [ j ] \delta_R(m) \triangleq T[k]-T[j] δ 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 ) R=(S,T) R = ( S , T ) , let O O O be an operation invoked in step S [ a ] S[a] S [ a ] .
I R ( O ) ≜ { [ T [ a ] , T [ b ] ] , if O returns in step S [ b ] , [ T [ a ] , ∞ ) , if O is incomplete. \mathcal{I}_{R}(O) \triangleq
\begin{cases}
[T[a],T[b]], & \text{if } O \text{ returns in step } S[b],\\
[T[a],\infty), & \text{if } O \text{ is incomplete.}
\end{cases} I R ( O ) ≜ { [ T [ a ] , T [ b ]] , [ T [ a ] , ∞ ) , if O returns in step S [ b ] , if O is incomplete.
The latency of O O O , denoted δ R ( O ) \delta_{R}(O) δ R ( O ) , is the length of I R ( O ) \mathcal{I}_{R}(O) I R ( O ) . In particular, δ R ( O ) = ∞ \delta_{R}(O)=\infty δ R ( O ) = ∞ if O O O is incomplete.
Definition 2.5. In a run R = ( S , T ) R=(S,T) R = ( S , T ) , let L L L be the set of processes that take infinitely many steps in S S S , and let O O O be an operation. We say that messages are timely during O O O if every message sent during O O O to a process in L L L is timely.
All these notions are relative to a run, which we specify explicitly when needed. When the run R R R is clear from context, we omit it from the notation, writing I ( O ) \mathcal{I}(O) I ( O ) , δ ( m ) \delta(m) δ ( m ) , and δ ( O ) \delta(O) δ ( O ) .
Definition 2.6 (Worst-case message delay). The worst-case message delay of an algorithm A \mathcal{A} A is
δ ( A ) ≜ sup { δ R ( O ) | R is a run of A , O is an operation in R invoked by a correct process in R , messages are timely during O } . \delta(\mathcal{A}) \triangleq\sup\left\{ \delta_{R}(O) \;\middle|\;
\begin{array}{l}
R\text{ is a run of }\mathcal{A},\\
O\text{ is an operation in }R\text{ invoked by a correct process in }R,\\
\text{messages are timely during }O
\end{array}
\right\}. δ ( A ) ≜ sup ⎩ ⎨ ⎧ δ R ( O ) R is a run of A , O is an operation in R invoked by a correct process in R , messages are timely during O ⎭ ⎬ ⎫ .
If δ ( A ) \delta(\mathcal{A}) δ ( A ) is finite, two simple but useful consequences follow:
Proposition 2.7. If δ ( A ) < ∞ \delta(\mathcal{A})<\infty δ ( A ) < ∞ , then A \mathcal{A} A satisfies liveness: In every schedule of A \mathcal{A} A , every operation invoked by a correct process eventually returns.
Proposition 2.8. If δ ( A ) < ∞ \delta(\mathcal{A})<\infty δ ( A ) < ∞ , then δ ( A ) = k \delta(\mathcal{A})=k δ ( A ) = k for some nonnegative integer k k k .
Accordingly, whenever we refer to a worst-case message delay of k k k , we take k k k to be a nonnegative integer. Both propositions are intuitively clear, but their proofs require some technical care; we defer them to Appendix B.
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: l a s t ∈ Z ≥ 0 \mathit{last} \in\mathbb{Z}_{\ge0} last ∈ Z ≥ 0 , initially 0.
next():
choose any Δ ∈ Z ≥ 1 \Delta\in\mathbb{Z}_{\ge1} Δ ∈ Z ≥ 1
l a s t ← l a s t + Δ \mathit{last} \leftarrow\mathit{last}+\Delta last ← last + Δ
return l a s t \mathit{last} 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 [13 ] , 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 H 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 ′ H' H ′ that (1) satisfies the sequential specification of TS and (2) preserves the precedence of operations in H H H .
Definition 3.2 (TS implementation). Let A A A be an algorithm whose next ( ) \operatorname{next}() next ( ) operation returns positive integers. We say that A A A implements TS in a system with crash failures if every schedule S S S of A A A , with corresponding history H H H , satisfies the following conditions:
(CT1) Safety : H H H is linearizable with respect to TS.
(CT2) Liveness : Every operation invoked by a correct process in S S S eventually returns.
We call such an algorithm A A 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 A A be an algorithm whose next ( ) \operatorname{next}() next ( ) operation returns positive integers. Then A A A implements TS in a system with crash failures if and only if every schedule S S S of A A A , with corresponding history H H H , satisfies the following conditions:
(CT1a) Ordering : If a complete operation O 1 O_1 O 1 precedes a complete operation O 2 O_2 O 2 in H H H , then O 1 O_1 O 1 returns a smaller value than O 2 O_2 O 2 .
(CT1b) Uniqueness : No two distinct complete operations in H H H return the same value.
(CT2) Liveness : Every operation invoked by a correct process in S S 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 A A , (CT1) ⟺ \Longleftrightarrow ⟺ (CT1a) ∧ \land ∧ (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 H H , (CT1) ⟹ \Longrightarrow ⟹ (CT1a) ∧ \land ∧ (CT1b).
Proof. Suppose that H H H satisfies (CT1). Since H H H is linearizable with respect to TS, we can discard some incomplete operations from H H H , append responses to the remaining incomplete operations, and arrange the resulting operations into a sequential history H ′ H' H ′ that (1) satisfies the sequential specification of TS and (2) preserves the precedence of operations in H H H . Every complete operation in H H H therefore appears in H ′ H' H ′ with the same return value. By the sequential specification of TS, each next ( ) \operatorname{next}() next ( ) operation increases last \operatorname{last} last by some Δ ≥ 1 \Delta\ge1 Δ ≥ 1 and returns the new value of last \operatorname{last} last . Hence, the values returned by successive operations in H ′ H' H ′ are strictly increasing.
For (CT1a), suppose that a complete operation O 1 O_1 O 1 precedes a complete operation O 2 O_2 O 2 in H H H . Since H ′ H' H ′ preserves the precedence of operations in H H H , O 1 O_1 O 1 appears before O 2 O_2 O 2 in H ′ H' H ′ and therefore returns a smaller value. For (CT1b), let O 1 O_1 O 1 and O 2 O_2 O 2 be distinct complete operations in H H H . Both appear in H ′ H' H ′ with the same return values as in H H H . Since H ′ H' H ′ is sequential, one appears before the other; because return values strictly increase in H ′ H' H ′ , they return distinct values.
Claim 3.5. For every history H H H whose complete operations return positive integers, (CT1a) ∧ \land ∧ (CT1b) ⟹ \Longrightarrow ⟹ (CT1).
Proof. Suppose that H H H satisfies (CT1a) and (CT1b). Discard all incomplete operations from H H H , and arrange the complete operations into a sequential history H ′ H' H ′ in increasing order of their return values.5 To show that H H H is linearizable with respect to TS, it remains to show that H ′ H' H ′ satisfies the sequential specification of TS and preserves the precedence of operations in H H H .
The return values in H ′ H' H ′ are positive integers and, by construction and (CT1b), strictly increasing. Thus, H ′ H' H ′ satisfies the sequential specification of TS.
Next, suppose that a complete operation O 1 O_1 O 1 precedes a complete operation O 2 O_2 O 2 in H H H . By (CT1a), O 1 O_1 O 1 returns a smaller value than O 2 O_2 O 2 . Since H ′ H' H ′ orders operations by increasing return value, O 1 O_1 O 1 appears before O 2 O_2 O 2 in H ′ H' H ′ . Hence, H ′ H' H ′ preserves the precedence of operations in H H H .
Therefore, H H H is linearizable with respect to TS.
Since the next() operation of A \mathcal{A} A returns positive integers, Claims 3.4 and 3.5 prove the proposition.
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 n \ge2 n ≥ 2 processes in the system, of which at most f ≥ 1 f \ge1 f ≥ 1 may crash.
Maximum Resilience
Proposition 4.1. In a system with crash failures, there exists an implementation of TS only if n > 2 f n > 2f n > 2 f .
Proof. By a standard partitioning argument.
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 f = 1 f = 1 and then for general f f f .
Two-Delay Algorithm for f = 1 f=1 f = 1
When f = 1 f = 1 f = 1 , TS can be implemented in two message delays.
Theorem 4.2. In a system with crash failures, if n > 2 f n > 2f n > 2 f and f = 1 f = 1 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.6 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 p i p_i p i , its local clock x i x_i x i is non-decreasing.
Proof. After initialization, only lines 13 and 20 assign to x i x_i x i , and neither decreases it.
Claim 4.4. If an invocation of next() computes base timestamp t t t on line 19, then at the time of return, at least two distinct processes p j p_j p j satisfy x j ≥ t x_j \ge t x j ≥ t .
Proof. Let p i p_i p i be the process performing the invocation. Write R = { j : ⟨ j , − ⟩ ∈ r e p l i e s i } R = \{j : \langle j, -\rangle\in\mathrm{replies}_i\} R = { j : ⟨ j , − ⟩ ∈ replies i } when p i p_i p i computes t t t on line 19. By line 18, ∣ r e p l i e s i ∣ = n − 2 |\mathrm{replies}_i| = n - 2 ∣ replies i ∣ = n − 2 ; by line 11, each sender contributes at most one element to r e p l i e s i \mathrm{replies}_i replies i , so ∣ R ∣ = n − 2 ≥ 1 |R| = n - 2 \ge1 ∣ R ∣ = n − 2 ≥ 1 . Moreover, p i p_i p i sends no request to itself (line 9) and therefore receives no reply from itself, so i ∉ R i \notin R i ∈ / R .
For each j ∈ R j \in R j ∈ R , let v j v_j v j be the unique value such that ⟨ j , v j ⟩ ∈ r e p l i e s i \langle j, v_j\rangle\in\mathrm{replies}_i ⟨ j , v j ⟩ ∈ replies i when p i p_i p i computes t t t (line 19). Since t = max j ∈ R v j t = \max_{j \in R} v_j t = max j ∈ R v j , choose ℓ ∈ R \ell\in R ℓ ∈ R such that v ℓ = t v_\ell= t v ℓ = t . By lines 13 and 14, process p ℓ p_\ell p ℓ has x ℓ = v ℓ = t x_\ell= v_\ell= t x ℓ = v ℓ = t when it sends its reply. By Claim 4.3 , x ℓ ≥ t x_\ell\ge t x ℓ ≥ t still holds when p i p_i p i returns.
For the invoking process p i p_i p i , line 20 sets x i ← max ( x i , t ) x_i \leftarrow\max(x_i,t) x i ← max ( x i , t ) before line 23 returns. Hence, x i ≥ t x_i \ge t x i ≥ t at the time of return. Since ℓ ∈ R \ell\in R ℓ ∈ R and i ∉ R i \notin R i ∈ / R , the processes p ℓ p_\ell p ℓ and p i p_i p i are distinct, and the claim follows.
Algorithm 1 A worst-case two-delay implementation of TS in a system with crash failures where n > 2 f n > 2f n > 2 f and f = 1 f = 1 f = 1 .
Code for process p_i (0 ≤ i < n):
1: x_i ← 0 ▷ p_i’s local clock.
2: seq_i ← 0 ▷ Sequence number of p_i’s ongoing invocation, or of its next invocation when idle.
3: reqSeq_i[j] ← −1 for each j ≠ i ▷ Largest q in a ⟨Req q, −⟩ received from p_j.
4: phase_i ← idle ▷ Whether p_i is idle or has an ongoing invocation.
5: replies_i ← ∅ ▷ Set of ⟨sender index, reply value⟩ received for p_i’s ongoing invocation.
6: upon invocation of next() do
7: replies_i ← ∅
8: phase_i ← ongoing
9: send ⟨Req seq_i, x_i⟩ to every process except p_i
10: upon receive ⟨Req q, v⟩ from p_j do
11: if q > reqSeq_i[j] then
12: reqSeq_i[j] ← q
13: x_i ← max(x_i, v) + 1
14: send ⟨Reply q, x_i⟩ to p_j
15: upon receive ⟨Reply q, v⟩ from p_j do
16: if phase_i = ongoing and q = seq_i then
17: replies_i ← replies_i ∪ {⟨j, v⟩}
18: if |replies_i| = n − 2 then
19: t ← max{v′ : ⟨j′, v′⟩ ∈ replies_i} ▷ Base timestamp.
20: x_i ← max(x_i, t)
21: phase_i ← idle
22: seq_i ← seq_i + 1
23: return n · t + i ▷ Completes the next() invocation.
Claim 4.5. Let h h h be an integer, and suppose that when a process p i p_i p i invokes next(), there are distinct processes p j p_j p j and p k p_k p k such that x j ≥ h x_j \ge h x j ≥ h and x k ≥ h x_k \ge h x k ≥ h . Then, if the invocation completes, its base timestamp t t t satisfies t > h t > h t > h .
Proof. Let v i v_i v i be the value of x i x_i x i included in the Req message that p i p_i p i sends for this invocation on line 9. When p i p_i p i computes t t t on line 19, write R = { j : ⟨ j , − ⟩ ∈ r e p l i e s i } R = \{j : \langle j, - \rangle\in\mathrm{replies}_i\} R = { j : ⟨ j , − ⟩ ∈ replies i } . As argued in the proof of Claim 4.4 , ∣ R ∣ = n − 2 |R| = n - 2 ∣ R ∣ = n − 2 and i ∉ R i \notin R i ∈ / R .
If i ∈ { j , k } i \in\{j, k\} i ∈ { j , k } , then v i ≥ h v_i \ge h v i ≥ h by assumption and monotonicity (Claim 4.3 ). For each ℓ ∈ R \ell\in R ℓ ∈ R , line 13 makes p ℓ p_\ell p ℓ ’s reply value at least v i + 1 > h v_i + 1 > h v i + 1 > h . Since t t t is the maximum of these reply values (line 19), we have t > h t > h t > h .
Otherwise, i ∉ { j , k } i \notin\{j, k\} i ∈ / { j , k } . Because ∣ R ∣ = n − 2 |R| = n - 2 ∣ R ∣ = n − 2 and i ∉ R i \notin R i ∈ / R , the set R R R omits only one of the n − 1 n - 1 n − 1 indices other than i i i ; hence j ∈ R j \in R j ∈ R or k ∈ R k \in R k ∈ R . Without loss of generality, assume j ∈ R j \in R j ∈ R . By Claim 4.3 , x j ≥ h x_j \ge h x j ≥ h when p j p_j p j receives the Req message from p i p_i p i . Line 13 therefore makes p j p_j p j ’s reply value greater than h h h . This value is among those whose maximum is t t t (line 19), so t > h t > h t > h .
Claim 4.6 (Ordering for base timestamps). Suppose two next() operations compute base timestamps t t t and t ′ t' t ′ on line 19, respectively. If the first returns before the second is invoked, then t < t ′ t < t' t < t ′ .
Proof. By Claim 4.4 , when the first operation returns, there exist distinct processes p j p_j p j and p k p_k p k such that x j ≥ t x_j \ge t x j ≥ t and x k ≥ t x_k \ge t x k ≥ t . By Claim 4.3 , both inequalities still hold when the second operation is invoked. Applying Claim 4.5 with h = t h = t h = t therefore shows that the second operation has base timestamp t ′ > t t' > t t ′ > t .
Claim 4.7 (Return values). Algorithm 1 returns positive integers from next() and satisfies ordering (CT1a) and uniqueness (CT1b).
Proof. Local clocks x i x_i x i 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 t t is a positive integer, and so is n ⋅ t + i n \cdot t + i n ⋅ t + i .
For (CT1a), suppose a complete operation at p i p_i p i with base timestamp t t t precedes one at p j p_j p j with base timestamp t ′ t' t ′ . By Claim 4.6, t < t ′ t < t' t < t ′ , so n ⋅ t + i < n ⋅ ( t + 1 ) ≤ n ⋅ t ′ + j n \cdot t + i < n \cdot(t + 1) \le n \cdot t' + j n ⋅ t + i < n ⋅ ( t + 1 ) ≤ n ⋅ t ′ + j .
For (CT1b), timestamps returned by different processes differ modulo n n n , and those returned by the same process are distinct by (CT1a) since its operations are sequential.
Claim 4.8 (Liveness). In Algorithm 1, every invocation by a correct process eventually returns.
Proof. Let p i p_i p i be a correct process that invokes next(). Line 9 sends a Req message to each of the other n − 1 n - 1 n − 1 processes, at least n − 2 n - 2 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 p i p_i p i eventually receives. Thus line 17 eventually makes ∣ r e p l i e s i ∣ = n − 2 |\mathrm{replies}_i| = n - 2 ∣ replies i ∣ = n − 2 , causing p i p_i p i to pass the check on line 18 and return on line 23.
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:
Figure 7.
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.
Three-Delay Algorithm for General f f f
In the general case, TS can be implemented in three message delays.
Theorem 4.10. In a system with crash failures, if n > 2 f n > 2f n > 2 f , then there exists an implementation of TS (Algorithm 2) whose worst-case message delay is three.
Proof. The algorithm adopts the “max-min technique” [8 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 p i p_i p i , its local clock x i x_i x i is non-decreasing.
Proof. After initialization, the only assignment to x i x_i x i is on line 24, which cannot decrease x i x_i x i .
Claim 4.12. For all processes p i p_i p i and p j p_j p j and every sequence number q q q , process p j p_j p j sends at most one ⟨ PROP ⟨ i , q ⟩ , − ⟩ \langle\operatorname{PROP}\langle i,q\rangle,-\rangle ⟨ PROP ⟨ i , q ⟩ , − ⟩ message to each process and at most one ⟨ REPLY q , − ⟩ \langle\operatorname{REPLY}\ q,-\rangle ⟨ REPLY q , − ⟩ message to p i p_i p i .
Proof. Process p j p_j p j sends ⟨ PROP ⟨ i , q ⟩ , − ⟩ \langle\operatorname{PROP}\langle i,q\rangle,-\rangle ⟨ PROP ⟨ i , q ⟩ , − ⟩ on line 15 only upon receiving ⟨ REQ q ⟩ \langle\operatorname{REQ}\ q\rangle ⟨ REQ q ⟩ from p i p_i p i with q > reqSeq j [ i ] q > \operatorname{reqSeq}_j[i] q > reqSeq j [ i ] , and it sets reqSeq j [ i ] ← q \operatorname{reqSeq}_j[i] \leftarrow q reqSeq j [ i ] ← q on line 14 before sending. As line 14 is the only assignment to reqSeq j [ i ] \operatorname{reqSeq}_j[i] reqSeq j [ i ] and never decreases it, the test q > reqSeq j [ i ] q > \operatorname{reqSeq}_j[i] q > reqSeq j [ i ] fails thereafter, so p j p_j p j sends no further PROP message for ⟨ i , q ⟩ \langle i,q\rangle ⟨ i , q ⟩ .
Process p j p_j p j sends ⟨ REPLY q , − ⟩ \langle\operatorname{REPLY}\ q,-\rangle ⟨ REPLY q , − ⟩ to p i p_i p i on line 25 only when an insertion on line 21 brings ∣ props j [ i ] ∣ |\operatorname{props}_j[i]| ∣ props j [ i ] ∣ to n − f n-f n − f while propSeq j [ i ] = q \operatorname{propSeq}_j[i]=q propSeq j [ i ] = q . Thereafter, the test on line 20 fails for every later ⟨ PROP ⟨ i , q ⟩ , − ⟩ \langle\operatorname{PROP}\langle i,q\rangle,-\rangle ⟨ PROP ⟨ i , q ⟩ , − ⟩ message received, so no further insertion—and hence no further reply—occurs while propSeq j [ i ] = q \operatorname{propSeq}_j[i]=q propSeq j [ i ] = q . Moreover, any later assignment to propSeq j [ i ] \operatorname{propSeq}_j[i] propSeq j [ i ] occurs on line 18, where it can only increase the value past q q q , so propSeq j [ i ] \operatorname{propSeq}_j[i] propSeq j [ i ] never equals q q q again.
Claim 4.13. If an invocation of next() computes base timestamp t t t on line 30, then at the time of return, at least n − f n-f n − f processes p j p_j p j satisfy x j ≥ t x_j \ge t x j ≥ t .
Proof. Let p i p_i p i be the process performing the invocation, and consider the time when p i p_i p i executes line 30 before returning. Write R = { j : ⟨ j , − ⟩ ∈ replies i } R = \{j : \langle j,-\rangle\in\operatorname{replies}_i\} R = { j : ⟨ j , − ⟩ ∈ replies i } . Line 30 is reached only when ∣ replies i ∣ = n − f |\operatorname{replies}_i|=n-f ∣ replies i ∣ = n − f (line 29). Every pair in replies i \operatorname{replies}_i replies i comes from a REPLY message with sequence number seq i \operatorname{seq}_i seq i , and by Claim 4.12 each process sends at most one such message to p i p_i p i , so we have ∣ R ∣ = n − f |R|=n-f ∣ R ∣ = n − f .
Fix an index j ∈ R j \in R j ∈ R , and let v j v_j v j be the value with ⟨ j , v j ⟩ ∈ replies i \langle j,v_j\rangle\in\operatorname{replies}_i ⟨ j , v j ⟩ ∈ replies i . By line 30, t ≤ v j t \le v_j t ≤ v j . Process p j p_j p j had x j = v j x_j=v_j x j = v j when it sent this reply on line 25, so by Claim 4.11, x j ≥ v j ≥ t x_j \ge v_j \ge t x j ≥ v j ≥ t still holds when p i p_i p i returns. As j ∈ R j \in R j ∈ R was arbitrary and ∣ R ∣ = n − f |R|=n-f ∣ R ∣ = n − f , the claim follows.
Claim 4.14. Let h h h be an integer, and suppose that when a process p i p_i p i invokes next(), at least n − f n-f n − f processes p k p_k p k have x k ≥ h x_k \ge h x k ≥ h . Then, if the invocation completes, its base timestamp t t t satisfies t > h t > h t > h .
Proof. Let A A A be a set of n − f n-f n − f indices such that x k ≥ h x_k \ge h x k ≥ h for every k ∈ A k \in A k ∈ A when the invocation begins. When p i p_i p i executes line 30, write R = { j : ⟨ j , − ⟩ ∈ replies i } R=\{j:\langle j,-\rangle\in\operatorname{replies}_i\} R = { j : ⟨ j , − ⟩ ∈ replies i } . Fix an index j ∈ R j \in R j ∈ R , and let v j v_j v j be the value with ⟨ j , v j ⟩ ∈ replies i \langle j,v_j\rangle\in\operatorname{replies}_i ⟨ j , v j ⟩ ∈ replies i . Before p j p_j p j sends this reply on line 25, ∣ props j [ i ] ∣ = n − f |\operatorname{props}_j[i]|=n-f ∣ props j [ i ] ∣ = n − f (line 22); by Claim 4.12, the pairs in props j [ i ] \operatorname{props}_j[i] props j [ i ] carry distinct indices, so p j p_j p j received PROP messages for this invocation from a set P j P_j P j of n − f n-f n − f process indices. Since ∣ A ∣ , ∣ P j ∣ ≥ n − f |A|,|P_j| \ge n-f ∣ A ∣ , ∣ P j ∣ ≥ n − f and n > 2 f n>2f n > 2 f , we have ∣ A ∩ P j ∣ > 0 |A\cap P_j|>0 ∣ A ∩ P j ∣ > 0 .
Fix some k ∈ A ∩ P j k\in A\cap P_j k ∈ A ∩ P j . As k ∈ A k\in A k ∈ A , we have x k ≥ h x_k\ge h x k ≥ h when p i p_i p i invoked next(). Process p k p_k p k sent its PROP message on line 15 upon receiving p i p_i p i ’s REQ message from line 11, hence after the invocation began, so Claim 4.11 implies that its proposal value w k w_k w k satisfies w k ≥ h w_k\ge h w k ≥ h . As k ∈ P j k\in P_j k ∈ P j , we have ⟨ k , w k ⟩ ∈ props j [ i ] \langle k,w_k\rangle\in\operatorname{props}_j[i] ⟨ k , w k ⟩ ∈ props j [ i ] , so v max ≥ w k ≥ h v_{\max}\ge w_k\ge h v m a x ≥ w k ≥ h when p j p_j p j executes line 24. After that line, we have x j ≥ v max + 1 > h x_j\ge v_{\max}+1>h x j ≥ v m a x + 1 > h , and p j p_j p j sends this value of x j x_j x j as v j v_j v j on line 25, so v j > h v_j>h v j > h .
Since j ∈ R j\in R j ∈ R was arbitrary, line 30 yields t = min { v j : j ∈ R } > h t=\min\{v_j:j\in R\}>h t = min { v j : j ∈ R } > h .
:::
Algorithm 2 A worst-case three-delay implementation of TS in a system with crash failures where n > 2 f n > 2f n > 2 f .
Code for process p i p_i p i (0 ≤ i < n 0 \le i < n 0 ≤ i < n ):
1: x i ← 0 x_i \leftarrow0 x i ← 0 ▷ p i p_i p i ’s local clock.
2: seq i ← 0 \operatorname{seq}_i \leftarrow0 seq i ← 0 ▷ Sequence number of p i p_i p i ’s ongoing invocation, or of its next invocation when idle.
3: reqSeq i [ k ] ← − 1 \operatorname{reqSeq}_i[k] \leftarrow-1 reqSeq i [ k ] ← − 1 for each k k k ▷ Largest q q q in a ⟨ Req q ⟩ \langle\operatorname{Req}\ q\rangle ⟨ Req q ⟩ received from p k p_k p k .
4: propSeq i [ k ] ← − 1 \operatorname{propSeq}_i[k] \leftarrow-1 propSeq i [ k ] ← − 1 for each k k k ▷ Largest q q q in a received ⟨ Prop ⟨ k , q ⟩ , − ⟩ \langle\operatorname{Prop}\ \langle k,q\rangle,-\rangle ⟨ Prop ⟨ k , q ⟩ , − ⟩ .
5: props i [ k ] ← ∅ \operatorname{props}_i[k] \leftarrow\varnothing props i [ k ] ← ∅ for each k k k ▷ Set of ⟨ \langle ⟨ sender index, proposal value⟩ \rangle ⟩ received for sequence number propSeq i [ k ] \operatorname{propSeq}_i[k] propSeq i [ k ] of p k p_k p k .
6: phase i ← idle \operatorname{phase}_i \leftarrow\operatorname{idle} phase i ← idle ▷ Whether p i p_i p i is idle or has an ongoing invocation.
7: replies i ← ∅ \operatorname{replies}_i \leftarrow\varnothing replies i ← ∅ ▷ Set of ⟨ \langle ⟨ sender index, reply value⟩ \rangle ⟩ received for p i p_i p i ’s ongoing invocation.
8: upon invocation of next ( ) \operatorname{next}() next ( ) do
9: replies i ← ∅ \operatorname{replies}_i \leftarrow\varnothing replies i ← ∅
10: phase i ← ongoing \operatorname{phase}_i \leftarrow\operatorname{ongoing} phase i ← ongoing
11: send ⟨ Req seq i ⟩ \langle\operatorname{Req}\ \operatorname{seq}_i\rangle ⟨ Req seq i ⟩ to every process
12: upon receive ⟨ Req q ⟩ \langle\operatorname{Req}\ q\rangle ⟨ Req q ⟩ from p k p_k p k do
13: if q > reqSeq i [ k ] q > \operatorname{reqSeq}_i[k] q > reqSeq i [ k ] then
14: reqSeq i [ k ] ← q \operatorname{reqSeq}_i[k] \leftarrow q reqSeq i [ k ] ← q
15: send ⟨ Prop ⟨ k , q ⟩ , x i ⟩ \langle\operatorname{Prop}\ \langle k,q\rangle,x_i\rangle ⟨ Prop ⟨ k , q ⟩ , x i ⟩ to every process
16: upon receive ⟨ Prop ⟨ k , q ⟩ , v ⟩ \langle\operatorname{Prop}\ \langle k,q\rangle,v\rangle ⟨ Prop ⟨ k , q ⟩ , v ⟩ from p j p_j p j do
17: if q > propSeq i [ k ] q > \operatorname{propSeq}_i[k] q > propSeq i [ k ] then
18: propSeq i [ k ] ← q \operatorname{propSeq}_i[k] \leftarrow q propSeq i [ k ] ← q
19: props i [ k ] ← ∅ \operatorname{props}_i[k] \leftarrow\varnothing props i [ k ] ← ∅
20: if q = propSeq i [ k ] q = \operatorname{propSeq}_i[k] q = propSeq i [ k ] and ∣ props i [ k ] ∣ < n − f |\operatorname{props}_i[k]| < n-f ∣ props i [ k ] ∣ < n − f then
21: props i [ k ] ← props i [ k ] ∪ { ⟨ j , v ⟩ } \operatorname{props}_i[k] \leftarrow\operatorname{props}_i[k] \cup\{\langle j,v\rangle\} props i [ k ] ← props i [ k ] ∪ {⟨ j , v ⟩}
22: if ∣ props i [ k ] ∣ = n − f |\operatorname{props}_i[k]| = n-f ∣ props i [ k ] ∣ = n − f then
23: v max ← max { v ′ : ⟨ j ′ , v ′ ⟩ ∈ props i [ k ] } v_{\max} \leftarrow\max\{v' : \langle j',v'\rangle\in\operatorname{props}_i[k]\} v m a x ← max { v ′ : ⟨ j ′ , v ′ ⟩ ∈ props i [ k ]}
24: x i ← max ( x i , v max ) + 1 x_i \leftarrow\max(x_i,v_{\max}) + 1 x i ← max ( x i , v m a x ) + 1
25: send ⟨ Reply q , x i ⟩ \langle\operatorname{Reply}\ q,x_i\rangle ⟨ Reply q , x i ⟩ to p k p_k p k
26: upon receive ⟨ Reply q , v ⟩ \langle\operatorname{Reply}\ q,v\rangle ⟨ Reply q , v ⟩ from p j p_j p j do
27: if phase i = ongoing \operatorname{phase}_i = \operatorname{ongoing} phase i = ongoing and q = seq i q = \operatorname{seq}_i q = seq i then
28: replies i ← replies i ∪ { ⟨ j , v ⟩ } \operatorname{replies}_i \leftarrow\operatorname{replies}_i \cup\{\langle j,v\rangle\} replies i ← replies i ∪ {⟨ j , v ⟩}
29: if ∣ replies i ∣ = n − f |\operatorname{replies}_i| = n-f ∣ replies i ∣ = n − f then
30: t ← min { v ′ : ⟨ j ′ , v ′ ⟩ ∈ replies i } t \leftarrow\min\{v' : \langle j',v'\rangle\in\operatorname{replies}_i\} t ← min { v ′ : ⟨ j ′ , v ′ ⟩ ∈ replies i } ▷ Base timestamp.
31: phase i ← idle \operatorname{phase}_i \leftarrow\operatorname{idle} phase i ← idle
32: seq i ← seq i + 1 \operatorname{seq}_i \leftarrow\operatorname{seq}_i + 1 seq i ← seq i + 1
33: return n ⋅ t + i n \cdot t + i n ⋅ t + i ▷ Completes the next ( ) \operatorname{next}() next ( ) invocation.
Claim 4.15 (Ordering for base timestamps ). Suppose two next() operations compute base timestamps t t t and t ′ t' t ′ on line 30, respectively. If the first returns before the second is invoked, then t < t ′ t < t' t < t ′ .
Proof. By Claim 4.13 , when the first operation returns, at least n − f n-f n − f processes p j p_j p j satisfy x j ≥ t x_j \ge t x j ≥ t . By Claim 4.11 , these inequalities still hold when the second operation is invoked. Applying Claim 4.14 with h = t h=t h = t therefore shows that the second operation has base timestamp t ′ > t t' > t t ′ > t .
Claim 4.16 (Return values ). Algorithm 2 returns positive integers from next() and satisfies ordering (CT1a) and uniqueness (CT1b).
Proof. Local clocks x i x_i x i 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 t t is a positive integer, and so is n ⋅ t + i n \cdot t+i n ⋅ t + i .
For (CT1a), suppose a complete operation at p i p_i p i with base timestamp t t t precedes one at p j p_j p j with base timestamp t ′ t' t ′ . By Claim 4.15, t < t ′ t < t' t < t ′ , so n ⋅ t + i < n ⋅ ( t + 1 ) ≤ n ⋅ t ′ + j n \cdot t+i < n \cdot(t+1) \le n \cdot t'+j n ⋅ t + i < n ⋅ ( t + 1 ) ≤ n ⋅ t ′ + j .
For (CT1b), timestamps returned by different processes differ modulo n n n , and those returned by the same process are distinct by (CT1a) since its operations are sequential.
Claim 4.17 (Liveness ). In Algorithm 2, every invocation by a correct process eventually returns.
Proof. Let p i p_i p i be a correct process that invokes next(), and let q q q be the value of s e q i \mathrm{seq}_i seq i during this invocation. Line 11 sends ⟨ R e q q ⟩ \langle\mathrm{Req}\ q\rangle ⟨ Req q ⟩ to every process, at least n − f n-f n − f of which are correct. Each correct recipient eventually receives this fresh request, passes the check on line 13, and sends ⟨ P r o p ⟨ i , q ⟩ , − ⟩ \langle\mathrm{Prop}\ \langle i,q\rangle,-\rangle ⟨ Prop ⟨ i , q ⟩ , − ⟩ to every process on line 15.
Since p i p_i p i sends no request with a higher sequence number before this invocation returns, each correct process p j p_j p j eventually receives these Prop messages from at least n − f n-f n − f distinct processes while p r o p S e q j [ i ] = q \mathrm{propSeq}_j[i]=q propSeq j [ i ] = q . Thus line 21 eventually makes ∣ p r o p s j [ i ] ∣ = n − f |\mathrm{props}_j[i]|=n-f ∣ props j [ i ] ∣ = n − f , causing p j p_j p j to pass the check on line 22 and send a Reply to p i p_i p i on line 25, which p i p_i p i eventually receives. Hence, line 28 eventually makes ∣ r e p l i e s i ∣ = n − f |\mathrm{replies}_i|=n-f ∣ replies i ∣ = n − f , causing p i p_i p i to pass the check on line 29 and return on line 33.
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:
Figure 8.
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.
Latency Lower Bounds
We now turn to lower bounds on the worst-case message delay of implementing TS under crash failures.
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 \mathcal{A} A be an implementation of TS. Then there exists a loquacious implementation A ′ \mathcal{A}' A ′ of TS such that δ ( A ′ ) ≤ δ ( A ) \delta(\mathcal{A}') \le\delta(\mathcal{A}) δ ( A ′ ) ≤ δ ( A ) .
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 § 17 .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 n-f n − f processes. The invoker cannot wait for the remaining f f 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 A A be a loquacious algorithm with δ ( A ) ≤ 2 \delta(A) \le2 δ ( A ) ≤ 2 . Let p p p be a process, and let Q Q Q be a set of processes such that ∣ Q ∣ = n − f |Q| = n-f ∣ Q ∣ = n − f and p ∈ Q p \in Q p ∈ Q .
Suppose that σ \sigma σ is a schedule prefix of A A A in which the following hold:
Process p p p invokes an operation and broadcasts a message m m m in step σ [ a ] \sigma[a] σ [ a ] .
For each q ∈ Q q \in Q q ∈ Q , process q q q receives message m m m and broadcasts a message m q m_q m q in step σ [ j q ] \sigma[j_q] σ [ j q ] .
Process p p p receives the set of messages { m q : q ∈ Q } \{m_q : q \in Q\} { m q : q ∈ Q } in step σ [ b ] \sigma[b] σ [ b ] .
Between steps σ [ a ] \sigma[a] σ [ a ] and σ [ b ] \sigma[b] σ [ b ] , inclusive, the only steps are those specified above.
Then the operation invoked by p p p in step σ [ a ] \sigma[a] σ [ a ] returns no later than step σ [ b ] \sigma[b] σ [ b ] .
We defer the proof of this lemma to Appendix § 17 .3.1.
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 § 18 .
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 f \ge2 f ≥ 2 , then any implementation of TS has worst-case message delay at least three.
Proof. Consider a system with n n n processes, of which at most f ≥ 2 f \ge2 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 A A of TS with δ ( A ) < 3 \delta(A) < 3 δ ( A ) < 3 . Since finite worst-case message delays are integers (Proposition 2.8), δ ( A ) ≤ 2 \delta(A) \le2 δ ( A ) ≤ 2 . By Proposition 3.3 , A A A satisfies ordering (CT1a). Finally, by Proposition 4.1 , n > 2 f n > 2f n > 2 f .
We name the processes p 0 , p 1 , … , p n − 1 p_0,p_1,\ldots,p_{n-1} p 0 , p 1 , … , p n − 1 , with process indices taken from the cyclic group Z n \mathbb{Z}_n Z n . So arithmetic on process indices is modulo n n n . For i , j ∈ Z n i,j \in\mathbb{Z}_n i , j ∈ Z n , we write i , i + 1 , … , j i,i+1,\ldots,j i , i + 1 , … , j for the inclusive cyclic range obtained by starting at i i i and repeatedly adding one until j j j is first reached (in particular, when i = j i=j i = j , this range is simply i i i ).
Roadmap. For each i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n , we will construct a schedule prefix σ i \sigma^i σ i of A \mathcal{A} A as follows (Figure 1 (PDF p. 14) illustrates the construction for n = 6 n = 6 n = 6 , f = 2 f = 2 f = 2 ):
Figure 1 (PDF p. 14). Proof of Theorem 4.23 . In a system with crash failures where f ≥ 2 f \ge2 f ≥ 2 , suppose toward a contradiction that some loquacious implementation A A A of TS has δ ( A ) ≤ 2 \delta(A) \le2 δ ( A ) ≤ 2 . For n = 6 n = 6 n = 6 and f = 2 f = 2 f = 2 , the figure shows σ 0 \sigma^0 σ 0 , σ 1 \sigma^1 σ 1 , and σ 5 \sigma^5 σ 5 . 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 r r indicates that it has returned r r r by that step. Without a return marker, the figure makes no claim about whether the operation returns within the prefix. Condition (CT1a) gives a i < b i a^i < b^i a i < b i . Furthermore, σ i \sigma^i σ i and σ i + 1 \sigma^{i+1} σ i + 1 are indistinguishable to p i p_i p i through the return of its operation, so b i = a i + 1 b^i = a^{i+1} b i = a i + 1 . Together, these relations yield the contradiction a 0 < a 1 < ⋯ < a 5 < a 0 a^0 < a^1 < \cdots< a^5 < a^0 a 0 < a 1 < ⋯ < a 5 < a 0 .
For j = i + 1 , i + 2 , … , i − 2 j = i + 1, i + 2, \ldots, i - 2 j = i + 1 , i + 2 , … , i − 2 , process p j p_j p j invokes next ( ) \operatorname{next}() next ( ) ; the message broadcast by its invocation step is then received by the processes in some receiver set D j i D^i_j D j i .
Process p i − 1 p_{i-1} p i − 1 invokes next ( ) \operatorname{next}() next ( ) , completes a round trip of communication with itself and some set H i − 1 H_{i-1} H i − 1 of helper processes, and returns value a i a^i a i .
Process p i p_i p i invokes next ( ) \operatorname{next}() next ( ) , completes a round trip with itself and the helper processes in H i H_i H i , and returns value b i b^i b i .
Each σ i \sigma^i σ i can be extended to a schedule of A \mathcal{A} A in which p i − 1 p_{i-1} p i − 1 returns before p i p_i p i invokes, so condition (CT1a) implies
a i < b i for each i ∈ Z n . a^i < b^i \qquad\text{for each } i \in\mathbb{Z}_n. a i < b i for each i ∈ Z n .
The key to the argument will be to choose the sets D j i D^i_j D j i and H i H_i H i such that σ i \sigma^i σ i and σ i + 1 \sigma^{i+1} σ i + 1 are indistinguishable to process p i p_i p i for each i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n . Consequently, p i p_i p i returns the same value from its operation in σ i \sigma^i σ i and σ i + 1 \sigma^{i+1} σ i + 1 , and so
a i + 1 = b i for each i ∈ Z n . a^{i+1} = b^i \qquad\text{for each } i \in\mathbb{Z}_n. a i + 1 = b i for each i ∈ Z n .
Thus a i < a i + 1 a^i < a^{i+1} a i < a i + 1 for every i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n . Chaining these inequalities around the cycle yields a 0 < a 1 < ⋯ < a n − 1 < a 0 a^0 < a^1 < \cdots< a^{n-1} < a^0 a 0 < a 1 < ⋯ < a n − 1 < a 0 , a contradiction.
We now give the full proof following this roadmap, starting by defining the sets H i H_i H i and D j i D^i_j D j i .
Helper and receiver sets. For each i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n , define the helper set
H i ≜ { p i + 2 , p i + 3 , … , p i − f } . H_i \mathrel{\triangleq} \{p_{i+2},p_{i+3},\ldots,p_{i-f}\}. H i ≜ { p i + 2 , p i + 3 , … , p i − f } .
By construction, ∣ H i ∣ = n − f − 1 |H_i| = n - f - 1 ∣ H i ∣ = n − f − 1 . Moreover, since n > 2 f n > 2f n > 2 f and f ≥ 2 f \ge2 f ≥ 2 ,
p i − 1 , p i , p i + 1 ∉ H i . (1) p_{i-1},p_i,p_{i+1} \notin H_i. \tag*{(1)} p i − 1 , p i , p i + 1 ∈ / H i . (1)
For i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n and j ∈ { i + 1 , i + 2 , … , i − 2 } j \in\{i + 1, i + 2, \ldots, i - 2\} j ∈ { i + 1 , i + 2 , … , i − 2 } , define the receiver set
D j i ≜ H j ∩ H j + 1 ∩ ⋯ ∩ H i − 1 . (2) D^i_j \mathrel{\triangleq} H_j \cap H_{j+1} \cap\cdots\cap H_{i-1}. \tag*{(2)} D j i ≜ H j ∩ H j + 1 ∩ ⋯ ∩ H i − 1 . (2)
For each fixed i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n , these sets are nested as their indices advance toward i − 1 i - 1 i − 1 in cyclic order:
D i + 1 i ⊆ D i + 2 i ⊆ ⋯ ⊆ D i − 2 i ⊆ H i − 1 . (3) D^i_{i+1} \subseteq D^i_{i+2} \subseteq\cdots\subseteq D^i_{i-2} \subseteq H_{i-1}. \tag*{(3)} D i + 1 i ⊆ D i + 2 i ⊆ ⋯ ⊆ D i − 2 i ⊆ H i − 1 . (3)
Unwinding the definitions, for every p k ∈ H i − 1 p_k \in H_{i-1} p k ∈ H i − 1 and x ∈ { i + 1 , i + 2 , … , i − 2 } x \in\{i + 1, i + 2, \ldots, i - 2\} x ∈ { i + 1 , i + 2 , … , i − 2 } ,
p k ∈ D x i ⟺ x ∈ { k + f , k + f + 1 , … , i − 1 } . (4) p_k \in D^i_x \Longleftrightarrow x \in\{k + f, k + f + 1, \ldots, i - 1\}. \tag*{(4)} p k ∈ D x i ⟺ x ∈ { k + f , k + f + 1 , … , i − 1 } . (4)
Constructing the schedule prefixes. Fix i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n . We construct σ i \sigma^i σ 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 \mathcal{A} 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 \sigma^i σ i . Since A \mathcal{A} 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 \sigma^i σ i are as follows.
Phase 1: background invocations. For j = i + 1 , i + 2 , … , i − 2 j = i + 1, i + 2, \ldots, i - 2 j = i + 1 , i + 2 , … , i − 2 , in that cyclic order: (a) process p j p_j p j takes a step that receives no messages and invokes next(), broadcasting a message m j i m_j^i m j i ; and then
(b) the processes in D j i D_j^i D j i (in any order) each take a step that receives m j i m_j^i m j i .
Phase 2: a complete operation by p i − 1 p_{i-1} p i − 1 .
(a) process p i − 1 p_{i-1} p i − 1 takes a step that receives no messages and invokes next(), broadcasting a message m i − 1 i m_{i-1}^i m i − 1 i ;
(b) each process p k ∈ H i − 1 ∪ { p i − 1 } p_k \in H_{i-1} \cup\{p_{i-1}\} p k ∈ H i − 1 ∪ { p i − 1 } (in any order) takes a step that receives m i − 1 i m_{i-1}^i m i − 1 i , broadcasting a message m ^ k , i − 1 i \widehat{m}_{k,i-1}^i m k , i − 1 i ; and then
(c) process p i − 1 p_{i-1} p i − 1 takes a step that receives the set of messages { m ^ k , i − 1 i : p k ∈ H i − 1 ∪ { p i − 1 } } \{\widehat{m}_{k,i-1}^i : p_k \in H_{i-1} \cup\{p_{i-1}\}\} { m k , i − 1 i : p k ∈ H i − 1 ∪ { p i − 1 }} broadcast above.
By Lemma 4.21 (with p = p i − 1 p = p_{i-1} p = p i − 1 and Q = H i − 1 ∪ { p i − 1 } Q = H_{i-1} \cup\{p_{i-1}\} Q = H i − 1 ∪ { p i − 1 } ), the operation invoked by p i − 1 p_{i-1} p i − 1 in step 2a has returned by this point; denote its return value by a i a^i a i .
Phase 3: a complete operation by p i p_i p i , repeating phase 2 with p i p_i p i in place of p i − 1 p_{i-1} p i − 1 and H i H_i H i in place of H i − 1 H_{i-1} H i − 1 :
(a) process p i p_i p i takes a step that receives no messages and invokes next(), broadcasting a message m i i m_i^i m i i ;
(b) each process p k ∈ H i ∪ { p i } p_k \in H_i \cup\{p_i\} p k ∈ H i ∪ { p i } (in any order) takes a step that receives m i i m_i^i m i i , broadcasting a message m ^ k , i i \widehat{m}_{k,i}^i m k , i i ; and then
(c) process p i p_i p i takes a step that receives the set of messages { m ^ k , i i : p k ∈ H i ∪ { p i } } \{\widehat{m}_{k,i}^i : p_k \in H_i \cup\{p_i\}\} { m k , i i : p k ∈ H i ∪ { p i }} broadcast above.
By Lemma 4.21 (with p = p i p = p_i p = p i and Q = H i ∪ { p i } Q = H_i \cup\{p_i\} Q = H i ∪ { p i } ), the operation invoked by p i p_i p i in step 3a has returned by this point; denote its return value by b i b^i b i .
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 \sigma^i σ i is a schedule prefix of A \mathcal{A} A . We call the steps specified in 1a, 2a, and 3a invocation steps , and all other steps of σ i \sigma^i σ 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 ∈ Z n i \in\mathbb{Z}_n i ∈ Z n , a i < b i a^i < b^i a i < b i .
Proof. Fix i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n . Extend σ i \sigma^i σ i to a schedule of A \mathcal{A} A . Both operations are complete and p i − 1 p_{i-1} p i − 1 ’s operation returns before p i p_i p i ’s operation is invoked. The claim follows from condition (CT1a).
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 ∈ Z n i,j \in\mathbb{Z}_n i , j ∈ Z n , process p j p_j p j ’s invocation step is its first step in σ i \sigma^i σ i . Consequently,
m j i = m j i ′ for all i , i ′ , j ∈ Z n . m_j^i = m_j^{i'} \qquad\text{for all } i,i',j \in\mathbb{Z}_n. m j i = m j i ′ for all i , i ′ , j ∈ Z n . Proof. Fix i , j ∈ Z n i,j \in\mathbb{Z}_n i , j ∈ Z n . In σ i \sigma^i σ i , the invocation steps occur in the cyclic order
p i + 1 , p i + 2 , … , p i − 2 , p i − 1 , p i . p_{i+1}, p_{i+2}, \ldots, p_{i-2}, p_{i-1}, p_i. p i + 1 , p i + 2 , … , p i − 2 , p i − 1 , p i . Suppose first that j ≠ i j \ne i j = i . Before p j p_j p j invokes, every step in σ i \sigma^i σ i is either an invocation step by a process p x p_x p x preceding p j p_j p j in the order above, or a receive step taken by a process in D x i D_x^i D x i for such an x x x . Since p x p_x p x precedes p j p_j p j in the invocation order, (2) gives D x i ⊆ H j D_x^i \subseteq H_j D x i ⊆ H j . Since p j ∉ H j p_j \notin H_j p j ∈ / H j by (1), none of these steps is taken by p j p_j p j .
Now suppose that j = i j=i j = i . Every invocation step preceding p i p_i p i ’s invocation is taken by some p x p_x p x with x ≠ i x\ne i x = i . Every preceding receive step is taken either by a process in D x i ⊆ H i − 1 D_x^i\subseteq H_{i-1} D x i ⊆ H i − 1 during phase 1, where the inclusion follows from (3), or by a process in H i − 1 ∪ { p i − 1 } H_{i-1}\cup\{p_{i-1}\} H i − 1 ∪ { p i − 1 } during phase 2. Since p i ∉ H i − 1 p_i\notin H_{i-1} p i ∈ / H i − 1 by (1) and p i ≠ p i − 1 p_i\ne p_{i-1} p i = p i − 1 , none of these steps is taken by p i p_i p i .
Thus, p j p_j p j ’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, m j i = m j i ′ m_j^i=m_j^{i'} m j i = m j i ′ for all i , i ′ , j ∈ Z n i,i',j\in\mathbb{Z}_n i , i ′ , j ∈ Z n . □Claim 4.25
For each j ∈ Z n j\in\mathbb{Z}_n j ∈ Z n , denote by m j m_j m j the message m j i m_j^i m j i , which is the same for every i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n .
Claim 4.26. For every i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n and p k ∈ H i p_k\in H_i p k ∈ H i , in σ i \sigma^i σ i the steps taken by p k p_k p k through its receipt of m i m_i m i consist of p k p_k p k ’s invocation step followed, in order, by one receive step for each message in the sequence
m k + f , m k + f + 1 , … , m i . (5) m_{k+f},m_{k+f+1},\ldots,m_i. \tag*{(5)} m k + f , m k + f + 1 , … , m i . (5) Proof. Fix i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n and p k ∈ H i p_k\in H_i p k ∈ H i , and consider the prefix σ i \sigma^i σ i . By (1), p k ∉ { p i − 1 , p i } p_k\notin\{p_{i-1},p_i\} p k ∈ / { p i − 1 , p i } , so p k p_k p k invokes during phase 1. We distinguish two cases according to whether p k ∈ H i − 1 p_k\in H_{i-1} p k ∈ H i − 1 :
If p k ∈ H i − 1 p_k\in H_{i-1} p k ∈ H i − 1 , then (4) and the construction of phase 2 imply that, after invoking, p k p_k p k receives m k + f , m k + f + 1 , … , m i − 1 m_{k+f},m_{k+f+1},\ldots,m_{i-1} m k + f , m k + f + 1 , … , m i − 1 in that order during phases 1 and 2. It then receives m i m_i m i during phase 3, completing the sequence in (5).
If p k ∉ H i − 1 p_k\notin H_{i-1} p k ∈ / H i − 1 , then p k ∈ H i ∖ H i − 1 p_k\in H_i\setminus H_{i-1} p k ∈ H i ∖ H i − 1 , which implies k + f = i k+f=i k + f = i . Thus the sequence in (5) consists only of m i m_i m i . By (3), no receiver set used in phase 1 contains p k p_k p k , so it receives no messages in that phase. Moreover, p k ∉ H i − 1 ∪ { p i − 1 } p_k\notin H_{i-1}\cup\{p_{i-1}\} p k ∈ / H i − 1 ∪ { p i − 1 } , so it does not receive m i − 1 m_{i-1} m i − 1 in phase 2 either. Hence p k p_k p k takes no receive step before receiving m i m_i m i in phase 3, as claimed. □Claim 4.26
Claim 4.27. For every i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n and p k ∈ H i p_k\in H_i p k ∈ H i , in σ i + 1 \sigma^{i+1} σ i + 1 the steps taken by p k p_k p k through its receipt of m i m_i m i consist of p k p_k p k ’s invocation step followed, in order, by one receive step for each message in the sequence (5).
Proof. Fix i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n and p k ∈ H i p_k\in H_i p k ∈ H i , and consider the prefix σ i + 1 \sigma^{i+1} σ i + 1 . By (1), p k ∉ { p i , p i + 1 } p_k\notin\{p_i,p_{i+1}\} p k ∈ / { p i , p i + 1 } , so p k p_k p k takes its invocation step during phase 1. In σ i + 1 \sigma^{i+1} σ i + 1 , (4) implies that during phase 1 process p k p_k p k receives, in order, exactly those messages in (5) that precede m i m_i m i , each in a separate receive step. During phase 2, it receives m i m_i m i in one more receive step because p k ∈ H i p_k\in H_i p k ∈ H i . These are precisely the steps stated in the claim. □Claim 4.27
Claim 4.28. For every i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n and p k ∈ H i ∪ { p i } p_k\in H_i\cup\{p_i\} p k ∈ H i ∪ { p i } ,
m ^ k , i i = m ^ k , i i + 1 . \widehat{m}_{k,i}^{i}=\widehat{m}_{k,i}^{i+1}. m k , i i = m k , i i + 1 . Proof. Fix i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n and p k ∈ H i ∪ { p i } p_k\in H_i\cup\{p_i\} p k ∈ H i ∪ { p i } . By (1), p i ∉ H i p_i\notin H_i p i ∈ / H i , so exactly one of the following cases holds:
If p k ∈ H i p_k\in H_i p k ∈ H i , then by Claims 4.26 and 4.27, p k p_k p k takes the same sequence of steps in σ i \sigma^i σ i and σ i + 1 \sigma^{i+1} σ i + 1 through its receive step for m i m_i m i . This step broadcasts m ^ k , i i \widehat{m}_{k,i}^{i} m k , i i in σ i \sigma^i σ i and m ^ k , i i + 1 \widehat{m}_{k,i}^{i+1} m k , i i + 1 in σ i + 1 \sigma^{i+1} σ i + 1 , so m ^ k , i i = m ^ k , i i + 1 \widehat{m}_{k,i}^{i}=\widehat{m}_{k,i}^{i+1} m k , i i = m k , i i + 1 .
If p k = p i p_k=p_i p k = p i , then Claim 4.25 implies that its first step in both σ i \sigma^i σ i and σ i + 1 \sigma^{i+1} σ i + 1 is its invocation step, which broadcasts m i m_i m i in each. By construction, its next step in each prefix is a receive step for m i m_i m i . These receive steps are therefore identical, so m ^ i , i i = m ^ i , i i + 1 \widehat{m}_{i,i}^{i}=\widehat{m}_{i,i}^{i+1} m i , i i = m i , i i + 1 . □Claim 4.28
For each i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n and p k ∈ H i ∪ { p i } p_k\in H_i\cup\{p_i\} p k ∈ H i ∪ { p i } , we denote by m ^ k , i \widehat{m}_{k,i} m k , i the message m ^ k , i i = m ^ k , i i + 1 \widehat{m}_{k,i}^{i}=\widehat{m}_{k,i}^{i+1} m k , i i = m k , i i + 1 .
Claim 4.29. For every i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n , b i = a i + 1 b^i=a^{i+1} b i = a i + 1 .
Proof. Fix i ∈ Z n i\in\mathbb{Z}_n i ∈ Z n , and compare the steps of p i p_i p i in σ i \sigma^i σ i and σ i + 1 \sigma^{i+1} σ i + 1 , which belong to phase 3 of the former and phase 2 of the latter. In both prefixes, p i p_i p i takes exactly three steps up to and including the last step of its round trip:
p i p_i p i invokes next() and broadcasts m i m_i m i ;
p i p_i p i receives m i m_i m i and broadcasts m ^ i , i \widehat{m}_{i,i} m i , i ; and
p i p_i p i receives all messages m ^ k , i \widehat{m}_{k,i} m k , i for p k ∈ H i ∪ { p i } p_k \in H_i \cup\{p_i\} p k ∈ H i ∪ { p i } .
By Claim 4.25, p i p_i p i ’s invocation is its first step in both prefixes and broadcasts the same message m i m_i m i . By construction, its next step in each prefix receives m i m_i m i , so steps 1 and 2 agree in the two prefixes. By Claim 4.28 , p i p_i p i receives the same set of messages in step 3, so this step agrees as well. By Lemma 4.21, p i p_i p i ’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 b i b^i b i in σ i \sigma^i σ i and a i + 1 a^{i+1} a i + 1 in σ i + 1 \sigma^{i+1} σ i + 1 , so b i = a i + 1 b^i = a^{i+1} b i = a i + 1 .
Contradiction. By Claims 4.24 and 4.29 , a i < b i = a i + 1 a^i < b^i = a^{i+1} a i < b i = a i + 1 for every i ∈ Z n i \in\mathbb{Z}_n i ∈ Z n . Chaining these inequalities around the cycle gives
a 0 < a 1 < ⋯ < a n − 1 < a 0 a^0 < a^1 < \cdots< a^{n-1} < a^0 a 0 < a 1 < ⋯ < a n − 1 < a 0
a contradiction. Thus every implementation of TS has worst-case message delay at least three.
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 > 2 f n > 2f n > 2 f .
We next state the optimal latency for implementations of TS under crash failures. When n > 2 f n > 2f n > 2 f and f ≥ 2 f \ge2 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 > 2 f n > 2f n > 2 f and f ≥ 2 f \ge2 f ≥ 2 , then the optimal latency of implementing TS is three message delays.
When n > 2 f n > 2f n > 2 f and f = 1 f = 1 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 > 2 f n > 2f n > 2 f and f = 1 f = 1 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.
Adapting to Byzantine Failures
We now adapt the system model and latency measure (§ 2 ) and the implementation requirements for TS (§ 3 ) to systems with Byzantine processes. These adaptations apply in both settings we consider: with digital signatures (§ 7 ) and without them (§ 11 ).
System Model and Latency
We continue to assume n ≥ 2 n \ge2 n ≥ 2 processes and 1 ≤ f < n 1 \le f < n 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 S S of algorithm A A A is an infinite sequence of steps in which at least n − f n-f n − f processes take infinitely many steps, all according to A A A ; these processes are correct in S S S . Every other process is faulty —it may crash, deviate arbitrarily from A A 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 § 2.1 and the latency definitions in § 2.2 carry over verbatim. The two consequences of finite worst-case message delay, Propositions 2.7 and 2.8, also carry over. (Their proofs in Appendix § 16 apply equally under crash and Byzantine failures.)
In the setting with digital signatures (§ 7 ), 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 § 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 A A . In particular, if a Byzantine process q q q takes infinitely many steps, every message m m m sent to q q q is eventually delivered. However, q q q may handle the delivered message arbitrarily: It may act as if it had not received m m m or as if it had received a different message m ′ ≠ m m' \ne m m ′ = m .
Implementations of the Timestamp Object
To adapt Definition 3.2 (implementation of TS) to Byzantine failures, we replace crash linearizability with Byzantine linearizability [6 Section 4] . Intuitively, the history H H H of a schedule S S S is Byzantine linearizable with respect to TS if there exists a history H ^ \hat{H} H ^ such that (1) the projection of H ^ \hat{H} H ^ onto the correct processes in S S S is the same as that of H H H , and (2) H ^ \hat{H} H ^ is crash linearizable with respect to TS. In other words, H H H can be made crash linearizable with respect to TS by adding, omitting, or modifying operations of processes that are faulty in S S S . Below, we underline the changes for Byzantine failures.
Definition 5.2 (TS implementation under Byzantine failures). Let A A A be an algorithm whose next() operation returns positive integers. We say that A A A implements TS in a system with Byzantine processes if every schedule S S S of A A A , with corresponding history H H H , satisfies the following conditions:
(BT1) Safety : H H H is Byzantine linearizable with respect to TS.
(BT2) Liveness : Every operation invoked by a correct process in S S 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 A A be an algorithm whose next() operation returns positive integers. Then A A A implements TS in a system with Byzantine processes if and only if every schedule S S S of A A A , with corresponding history H H H , satisfies the following conditions:
(BT1a) Ordering: If a complete operation O 1 O_1 O 1 precedes a complete operation O 2 O_2 O 2 in H H H , where both are invoked by correct processes in S S S , then O 1 O_1 O 1 returns a smaller value than O 2 O_2 O 2 .
(BT1b) Uniqueness: No two distinct complete operations in H H H invoked by correct processes in S S S return the same value.
(BT2) Liveness: Every operation invoked by a correct process in S S 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 S S of A A A with corresponding history H H H , (BT1) ⟺ \Longleftrightarrow ⟺ (BT1a) ∧ \land ∧ (BT1b). Each direction reuses the corresponding claim from the proof for systems with crash failures (Proposition 3.3 ).
(⟹ \Longrightarrow ⟹ ) Suppose that H H H is Byzantine linearizable with respect to TS (BT1). Then there exists H ^ \hat{H} H ^ that is crash linearizable with respect to TS (CT1) and whose projection onto the correct processes in S S S is the same as that of H H H . By Claim 3.4 , H ^ \hat{H} H ^ satisfies (CT1a) and (CT1b). Since H H H and H ^ \hat{H} H ^ have the same projection onto the correct processes in S S S , complete operations invoked by correct processes have the same return values and precedence in the two histories. Hence, H H H satisfies (BT1a) and (BT1b).
(⟸ \Longleftarrow ⟸ ) Suppose that H H H satisfies (BT1a) and (BT1b). Let H C H_C H C denote the projection of H H H onto the correct processes in S S S . Then H C H_C H C satisfies (CT1a) and (CT1b). Moreover, because correct processes follow A A A , every complete operation in H C H_C H C returns a positive integer. Hence, by Claim 3.5 , H C H_C H C is crash linearizable with respect to TS (CT1), which makes H H H Byzantine linearizable with respect to TS (BT1). □ \square □ Proposition 5.3
:::
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 n \ge2 n ≥ 2 processes, of which at most f ≥ 1 f \ge1 f ≥ 1 may be Byzantine.
Maximum Resilience
Proposition 6.1. In a system with Byzantine processes and digital signatures, there exists an implementation of TS only if n > 3 f n > 3f n > 3 f .
Proof. Suppose, toward a contradiction, that an implementation A \mathcal{A} A of TS exists in such a system. By Proposition 5.3 , A \mathcal{A} A satisfies ordering (BT1a). Because 2 ≤ n ≤ 3 f 2 \le n \le3f 2 ≤ n ≤ 3 f , we can choose pairwise disjoint sets A A A , B B B , C C C whose union is the set of processes, such that ∣ A ∣ |A| ∣ A ∣ , ∣ B ∣ |B| ∣ B ∣ , ∣ C ∣ ≤ f |C| \le f ∣ C ∣ ≤ f and A A A , C ≠ ∅ C \ne\emptyset C = ∅ . Fix processes p a ∈ A p_a \in A p a ∈ A and p c ∈ C p_c \in C p c ∈ C .
Consider a schedule of A \mathcal{A} A in which the processes in C C C crash before taking any steps (where ∣ C ∣ ≤ f |C| \le f ∣ C ∣ ≤ f ), the processes in A ∪ B A \cup B A ∪ B are correct, and p a p_a p a invokes next(). By liveness, this operation eventually returns some value r a r_a r a . Let σ A \sigma_A σ A be the schedule prefix of A \mathcal{A} A ending at its return; thus, σ A \sigma_A σ A contains no steps by processes in C C C . Symmetrically, let σ C \sigma_C σ C be a schedule prefix of A \mathcal{A} A in which p c p_c p c invokes next() and returns r c r_c r c and processes in A A A take no steps (where ∣ A ∣ ≤ f |A| \le f ∣ A ∣ ≤ f ). Without loss of generality, assume r a ≥ r c r_a \ge r_c r a ≥ r c .
Now consider the concatenation σ A ∘ σ C \sigma_A \circ\sigma_C σ A ∘ σ C . It extends to a schedule of A \mathcal{A} A in which the processes in B B B are Byzantine (where ∣ B ∣ ≤ f |B| \le f ∣ B ∣ ≤ f ) and those in A ∪ C A \cup C A ∪ C are correct. The processes in B B B first reproduce their steps in σ A \sigma_A σ A , and then “roll back” to their initial states and reproduce their steps in σ C \sigma_C σ C ; digital signatures do not prevent a Byzantine process from resetting its own state. The messages sent to C C C during σ A \sigma_A σ A and to A A A during σ C \sigma_C σ C are delayed until after both operations return, so that the processes in A ∪ C A \cup C A ∪ C follow A \mathcal{A} A throughout. Since p a , p c ∈ A ∪ C p_a, p_c \in A \cup C p a , p c ∈ A ∪ C are correct and p a p_a p a ’s operation returns before p c p_c p c ’s operation is invoked, condition (BT1a) implies r a < r c r_a < r_c r a < r c , a contradiction. □Proposition 6.1
:::
Latency Upper Bounds
When n > 3 f n > 3f n > 3 f , TS can be implemented with a worst-case message delay of three. In fact, Theorem 7.2 , proved in § 11.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 > 3 f n > 3f n > 3 f , then there exists an implementation of TS whose worst-case message delay is three.
For the special case f = 1 f = 1 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 > 3 f n > 3f n > 3 f and f = 1 f = 1 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 p 0 , … , p n − 1 p_0, \ldots, p_{n-1} p 0 , … , p n − 1 . The notation ⟨ m ⟩ σ i \langle m \rangle_{\sigma_i} ⟨ m ⟩ σ i denotes statement m m m carrying a digital signature by process p i p_i p i .
Definition 6.4. A label by process p i p_i p i has the form
ℓ = ⟨ L A B E L i , k , r ⟩ σ i , k , r ∈ Z ≥ 1 . \ell= \langle\mathrm{LABEL}\ i,k,r \rangle_{\sigma_i}, \qquad k,r \in\mathbb{Z}_{\ge1}. ℓ = ⟨ LABEL i , k , r ⟩ σ i , k , r ∈ Z ≥ 1 . We write
origin ( ℓ ) ≜ i \operatorname{origin}(\ell) \triangleq i origin ( ℓ ) ≜ i for the origin of ℓ \ell ℓ ,
seq ( ℓ ) ≜ k \operatorname{seq}(\ell) \triangleq k seq ( ℓ ) ≜ k for its sequence number ,
rank ( ℓ ) ≜ r \operatorname{rank}(\ell) \triangleq r rank ( ℓ ) ≜ r for its rank .
Successive invocations by a correct process p i p_i p i are identified by labels of origin i i i with consecutive sequence numbers.
Definition 6.5. An acknowledgment of label ℓ \ell ℓ by process p i p_i p i is ⟨ ℓ ⟩ σ i \langle\ell\rangle_{\sigma_i} ⟨ ℓ ⟩ σ i .
Definition 6.6. A quorum certificate for label ℓ \ell ℓ is a set of acknowledgments
C = { ⟨ ℓ ⟩ σ i : i ∈ Q } C = \{\langle\ell\rangle_{\sigma_i}: i \in Q\} C = {⟨ ℓ ⟩ σ i : i ∈ Q } where Q ⊆ { 0 , … , n − 1 } Q \subseteq\{0,\ldots,n-1\} Q ⊆ { 0 , … , n − 1 } and ∣ Q ∣ = n − 1 |Q| = n-1 ∣ Q ∣ = n − 1 .
A quorum certificate for ℓ \ell ℓ contains acknowledgments from n − 1 n-1 n − 1 distinct processes. Since at most one process is Byzantine, it proves that at least n − 2 n-2 n − 2 correct processes have handled a request carrying label ℓ \ell ℓ .
Definition 6.7. A certified label is either ⊥ \perp ⊥ or a pair
ℓ ^ = ( ℓ , C ) \widehat{\ell} = (\ell,C) ℓ = ( ℓ , C ) where ℓ \ell ℓ is a label and
if seq ( ℓ ) = 1 \operatorname{seq}(\ell) = 1 seq ( ℓ ) = 1 , then C = ∅ C = \emptyset C = ∅ ;
if seq ( ℓ ) > 1 \operatorname{seq}(\ell) > 1 seq ( ℓ ) > 1 , then C C C is a quorum certificate for some label ℓ − \ell^{-} ℓ − such that origin ( ℓ − ) = origin ( ℓ ) \operatorname{origin}(\ell^{-}) = \operatorname{origin}(\ell) origin ( ℓ − ) = origin ( ℓ ) and seq ( ℓ − ) = seq ( ℓ ) − 1 \operatorname{seq}(\ell^{-}) = \operatorname{seq}(\ell)-1 seq ( ℓ − ) = seq ( ℓ ) − 1 .
We say that ℓ ^ \widehat{\ell} ℓ contains label ℓ \ell ℓ .
For a non-⊥ \perp ⊥ certified label ℓ ^ = ( ℓ , C ) \widehat{\ell} = (\ell,C) ℓ = ( ℓ , C ) , define
label ( ℓ ^ ) ≜ ℓ , origin ( ℓ ^ ) ≜ origin ( ℓ ) , \operatorname{label}(\widehat{\ell}) \triangleq\ell,\qquad\operatorname{origin}(\widehat{\ell}) \triangleq\operatorname{origin}(\ell), label ( ℓ ) ≜ ℓ , origin ( ℓ ) ≜ origin ( ℓ ) , seq ( ℓ ^ ) ≜ seq ( ℓ ) , rank ( ℓ ^ ) ≜ rank ( ℓ ) . \operatorname{seq}(\widehat{\ell}) \triangleq\operatorname{seq}(\ell),\qquad\operatorname{rank}(\widehat{\ell}) \triangleq\operatorname{rank}(\ell). seq ( ℓ ) ≜ seq ( ℓ ) , rank ( ℓ ) ≜ rank ( ℓ ) . Set seq ( ⊥ ) ≜ 0 \operatorname{seq}(\perp) \triangleq0 seq ( ⊥ ) ≜ 0 and rank ( ⊥ ) ≜ 0 \operatorname{rank}(\perp) \triangleq0 rank ( ⊥ ) ≜ 0 .
Definition 6.8 (Frontier). Let F F F be a sequence of n n n certified labels. We call F F F a frontier if the following conditions hold for every i = 0 , … , n − 1 i = 0,\ldots,n-1 i = 0 , … , n − 1 :
origin ( F [ i ] ) = i \operatorname{origin}(F[i]) = i origin ( F [ i ]) = i whenever F [ i ] ≠ ⊥ F[i] \ne\perp F [ i ] = ⊥ ;
rank ( F [ i ] ) ≤ N ( F ) \operatorname{rank}(F[i]) \le N(F) rank ( F [ i ]) ≤ N ( F ) , where
N ( F ) ≜ ∑ k = 0 n − 1 seq ( F [ k ] ) . N(F) \triangleq\sum_{k=0}^{n-1} \operatorname{seq}(F[k]). N ( F ) ≜ k = 0 ∑ n − 1 seq ( F [ k ]) . The empty frontier is ⊥ n ≜ ( ⊥ , … , ⊥ ) \perp^n \triangleq(\perp,\ldots,\perp) ⊥ n ≜ ( ⊥ , … , ⊥ ) .
Definition 6.9 (Merge). For frontiers F F F and G G G , the merge of G G G into F F F , denoted F ◃ G F \triangleleft G F ◃ G , is the sequence of n n n certified labels defined by
( F ◃ G ) [ i ] ≜ { G [ i ] if seq ( G [ i ] ) > seq ( F [ i ] ) , F [ i ] otherwise. (F \triangleleft G)[i] \triangleq
\begin{cases}
G[i] & \text{if } \operatorname{seq}(G[i]) > \operatorname{seq}(F[i]),\\
F[i] & \text{otherwise.}
\end{cases} ( F ◃ G ) [ i ] ≜ { G [ i ] F [ i ] if seq ( G [ i ]) > seq ( F [ i ]) , otherwise.
This definition directly implies
seq ( ( F ◃ G ) [ i ] ) = max { seq ( F [ i ] ) , seq ( G [ i ] ) } for every i = 0 , … , n − 1. \operatorname{seq}((F \triangleleft G)[i]) = \max\{\operatorname{seq}(F[i]),\operatorname{seq}(G[i])\}\quad\text{for every }i=0,\ldots,n-1. seq (( F ◃ G ) [ i ]) = max { seq ( F [ i ]) , seq ( G [ i ])} for every i = 0 , … , n − 1.
Proposition 6.10. If F F F and G G G are frontiers, then F ◃ G F \triangleleft G F ◃ G is a frontier.
Proof. Write H ≜ F ◃ G H \mathrel{\triangleq} F \triangleleft G H ≜ F ◃ G . For each i = 0 , … , n − 1 i=0,\ldots,n-1 i = 0 , … , n − 1 , the certified label H [ i ] H[i] H [ i ] is either F [ i ] F[i] F [ i ] or G [ i ] G[i] G [ i ] , hence is ⊥ \perp ⊥ or has origin i i i . Furthermore,
rank ( H [ i ] ) ≤ max { rank ( F [ i ] ) , rank ( G [ i ] ) } ≤ max { N ( F ) , N ( G ) } ( F , G are frontiers ) = max { ∑ k = 0 n − 1 seq ( F [ k ] ) , ∑ k = 0 n − 1 seq ( G [ k ] ) } ≤ ∑ k = 0 n − 1 max { seq ( F [ k ] ) , seq ( G [ k ] ) } = ∑ k = 0 n − 1 seq ( H [ k ] ) (by the definition of ◃ ) = N ( H ) . \begin{aligned}
\operatorname{rank}(H[i]) &\le\max\{\operatorname{rank}(F[i]),\operatorname{rank}(G[i])\}\\
&\le\max\{N(F),N(G)\} && (F,G\text{ are frontiers})\\
&= \max\left\{\sum_{k=0}^{n-1}\operatorname{seq}(F[k]),\sum_{k=0}^{n-1}\operatorname{seq}(G[k])\right\}\\
&\le\sum_{k=0}^{n-1}\max\{\operatorname{seq}(F[k]),\operatorname{seq}(G[k])\}\\
&= \sum_{k=0}^{n-1}\operatorname{seq}(H[k]) && \text{(by the definition of }\triangleleft\text{)}\\
&= N(H).
\end{aligned} rank ( H [ i ]) ≤ max { rank ( F [ i ]) , rank ( G [ i ])} ≤ max { N ( F ) , N ( G )} = max { k = 0 ∑ n − 1 seq ( F [ k ]) , k = 0 ∑ n − 1 seq ( G [ k ]) } ≤ k = 0 ∑ n − 1 max { seq ( F [ k ]) , seq ( G [ k ])} = k = 0 ∑ n − 1 seq ( H [ k ]) = N ( H ) . ( F , G are frontiers ) (by the definition of ◃ )
Hence, H H H is a frontier.
Definition 6.11. For frontiers F F F and G G G , we write F ⪯ G F \preceq G F ⪯ G if
seq ( F [ i ] ) ≤ seq ( G [ i ] ) for every i = 0 , … , n − 1. \operatorname{seq}(F[i])\le\operatorname{seq}(G[i])\quad\text{for every }i=0,\ldots,n-1. seq ( F [ i ]) ≤ seq ( G [ i ]) for every i = 0 , … , n − 1.
Proposition 6.12. Let F F F and G G G be frontiers.
(a) The relation ⪯ \preceq ⪯ is a preorder on frontiers.7
(b) F ⪯ F ◃ G F \preceq F \triangleleft G F ⪯ F ◃ G and G ⪯ F ◃ G G \preceq F \triangleleft G G ⪯ F ◃ G .
(c) If F ⪯ G F \preceq G F ⪯ G , then N ( F ) ≤ N ( G ) N(F)\le N(G) N ( F ) ≤ N ( G ) .
Definition 6.13 (Messages). There are two kinds of valid messages:
A valid request from process p i p_i p i has the form ⟨ R E Q F ⟩ \langle\mathsf{REQ}\ F\rangle ⟨ REQ F ⟩ , where F F F is a frontier with F [ i ] ≠ ⊥ F[i]\ne\perp F [ i ] = ⊥ .
A valid reply from process p j p_j p j has the form ⟨ R E P L Y ⟨ ℓ ⟩ σ j , F ⟩ \langle\mathsf{REPLY}\ \langle\ell\rangle_{\sigma_j},F\rangle ⟨ REPLY ⟨ ℓ ⟩ σ j , F ⟩ , where ℓ \ell ℓ is a label and F F F is a frontier.
Part 2. Algorithm and timestamp encoding. Algorithm 3 gives the implementation. It computes base timestamps using the two functions T i T_i T i and E E E from lines 1 and 2; we explain the idea behind them here. For each operation, the algorithm computes a base-timestamp triple τ \tau τ of integers by applying T i T_i T i (line 25). The function T i T_i T i 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 τ \tau τ to a positive integer t t t (line 26) using the encoding E E E , which preserves the lexicographic order (Lemma 6.17). This integer t t t is the operation’s base timestamp ; the invoker p i p_i p i then returns n ⋅ t + i n\cdot t+i n ⋅ t + i (line 28), using its index i i i to break ties between operations with the same base timestamp.
Algorithm 3 A worst-case two-delay implementation of TS in a system with Byzantine processes and digital signatures where n > 3 f n > 3f n > 3 f and f = 1 f = 1 f = 1 . Each gray tag in the right margin records how the values immediately after its line correspond to the notation in Part 3.
T i ( F , o ) ≜ ( N ( F ) , min { r i , r o } , 1 { r i > r o } ) \mathcal{T}_i(F,o) \triangleq\left(N(F),\min\{r_i,r_o\},1\{r_i>r_o\}\right) T i ( F , o ) ≜ ( N ( F ) , min { r i , r o } , 1 { r i > r o } ) where r i = rank ( F [ i ] ) r_i=\operatorname{rank}(F[i]) r i = rank ( F [ i ]) , r o = rank ( F [ o ] ) r_o=\operatorname{rank}(F[o]) r o = rank ( F [ o ]) ▷ See Definition 6.14.
E ( ( s , m , δ ) ) ≜ s 2 + 2 m + δ \mathcal{E}((s,m,\delta)) \triangleq s^2+2m+\delta E (( s , m , δ )) ≜ s 2 + 2 m + δ ▷ See Definition 6.15.
Code for process p i p_i p i (0 ≤ i < n 0 \le i < n 0 ≤ i < n ):
f r o n t i e r i ← ⊥ n \mathit{frontier}_i \leftarrow\bot^n frontier i ← ⊥ n
l a b e l i ← ⊥ \mathit{label}_i \leftarrow\bot label i ← ⊥ ▷ Label for ongoing invocation, ⊥ \bot ⊥ while idle.
a c k s i ← ∅ \mathit{acks}_i \leftarrow\varnothing acks i ← ∅ ▷ Acknowledgments for ongoing invocation; latest label’s quorum certificate while idle.
upon invocation of next() do f r o n t i e r i = L γ \mathit{frontier}_i=L_\gamma frontier i = L γ
s e q ← seq ( f r o n t i e r i [ i ] ) + 1 \mathit{seq} \leftarrow\operatorname{seq}(\mathit{frontier}_i[i])+1 seq ← seq ( frontier i [ i ]) + 1
r a n k ← N ( f r o n t i e r i ) + 1 \mathit{rank} \leftarrow N(\mathit{frontier}_i)+1 rank ← N ( frontier i ) + 1
ℓ ← ⟨ L a b e l i , s e q , r a n k ⟩ σ i \ell\leftarrow\langle\mathit{Label}_i,\mathit{seq},\mathit{rank}\rangle_{\sigma_i} ℓ ← ⟨ Label i , seq , rank ⟩ σ i , ℓ = ℓ γ \ell=\ell_\gamma ℓ = ℓ γ
l a b e l i ← ℓ \mathit{label}_i \leftarrow\ell label i ← ℓ
f r o n t i e r i [ i ] ← ( ℓ , a c k s i ) \mathit{frontier}_i[i] \leftarrow(\ell,\mathit{acks}_i) frontier i [ i ] ← ( ℓ , acks i ) , f r o n t i e r i = F γ 0 \mathit{frontier}_i=F^0_\gamma frontier i = F γ 0
a c k s i ← ∅ \mathit{acks}_i \leftarrow\varnothing acks i ← ∅
send ⟨ R E Q f r o n t i e r i ⟩ \langle\mathsf{REQ}\ \mathit{frontier}_i\rangle ⟨ REQ frontier i ⟩ to every process
upon receive valid ⟨ R E Q F ⟩ \langle\mathsf{REQ}\ F\rangle ⟨ REQ F ⟩ from p j p_j p j do
f r o n t i e r i ← f r o n t i e r i ◃ F \mathit{frontier}_i \leftarrow\mathit{frontier}_i \triangleleft F frontier i ← frontier i ◃ F
ℓ ← l a b e l ( F [ j ] ) \ell\leftarrow\mathit{label}(F[j]) ℓ ← label ( F [ j ])
send ⟨ R E P L Y ⟨ ℓ ⟩ σ i , f r o n t i e r i ⟩ \langle\mathsf{REPLY}\ \langle\ell\rangle_{\sigma_i},\mathit{frontier}_i\rangle ⟨ REPLY ⟨ ℓ ⟩ σ i , frontier i ⟩ to p j p_j p j
upon receive valid ⟨ R E P L Y ⟨ ℓ ⟩ σ j , F ⟩ \langle\mathsf{REPLY}\ \langle\ell\rangle_{\sigma_j},F\rangle ⟨ REPLY ⟨ ℓ ⟩ σ j , F ⟩ from p j p_j p j do
if ℓ = l a b e l i ≠ ⊥ \ell=\mathit{label}_i\ne\bot ℓ = label i = ⊥ and ⟨ ℓ ⟩ σ j ∉ a c k s i \langle\ell\rangle_{\sigma_j}\notin\mathit{acks}_i ⟨ ℓ ⟩ σ j ∈ / acks i then F = F γ , j F=F_{\gamma,j} F = F γ , j
a c k s i ← a c k s i ∪ { ⟨ ℓ ⟩ σ j } \mathit{acks}_i \leftarrow\mathit{acks}_i\cup\{\langle\ell\rangle_{\sigma_j}\} acks i ← acks i ∪ {⟨ ℓ ⟩ σ j }
f r o n t i e r i ← f r o n t i e r i ◃ F \mathit{frontier}_i \leftarrow\mathit{frontier}_i\triangleleft F frontier i ← frontier i ◃ F
if ∣ a c k s i ∣ = n − 1 |\mathit{acks}_i|=n-1 ∣ acks i ∣ = n − 1 then f r o n t i e r i = F γ \mathit{frontier}_i=F_\gamma frontier i = F γ
Q ← { k ∈ { 0 , … , n − 1 } : ⟨ ℓ ⟩ σ k ∈ a c k s i } Q\leftarrow\{k\in\{0,\ldots,n-1\}:\langle\ell\rangle_{\sigma_k}\in\mathit{acks}_i\} Q ← { k ∈ { 0 , … , n − 1 } : ⟨ ℓ ⟩ σ k ∈ acks i } , Q = Q γ Q=Q_\gamma Q = Q γ
o ← o\leftarrow o ← the unique index in { 0 , … , n − 1 } ∖ Q \{0,\ldots,n-1\}\setminus Q { 0 , … , n − 1 } ∖ Q , o = o γ o=o_\gamma o = o γ
τ ← T i ( f r o n t i e r i , o ) \tau\leftarrow\mathcal{T}_i(\mathit{frontier}_i,o) τ ← T i ( frontier i , o ) , τ = τ γ \tau=\tau_\gamma τ = τ γ
t ← E ( τ ) t\leftarrow\mathcal{E}(\tau) t ← E ( τ ) ▷ Base timestamp. t = t γ t=t_\gamma t = t γ
l a b e l i ← ⊥ \mathit{label}_i\leftarrow\bot label i ← ⊥
return n ⋅ t + i n\cdot t+i n ⋅ t + i ▷ Completes the next() invocation.
Definition 6.14 (Base-timestamp triple). For a frontier F F F and process indices i , o ∈ { 0 , … , n − 1 } i,o \in\{0,\ldots,n-1\} i , o ∈ { 0 , … , n − 1 } , the base-timestamp triple is the triple of integers defined by
T i ( F , o ) ≜ ( N ( F ) , min { r i , r o } , 1 { r i > r o } ) \mathcal{T}_i(F,o) \mathrel{\triangleq} \left(N(F),\min\{r_i,r_o\},\mathbf{1}\{r_i>r_o\}\right) T i ( F , o ) ≜ ( N ( F ) , min { r i , r o } , 1 { r i > r o } ) where r i = rank ( F [ i ] ) r_i=\operatorname{rank}(F[i]) r i = rank ( F [ i ]) and r o = rank ( F [ o ] ) r_o=\operatorname{rank}(F[o]) r o = rank ( F [ o ]) , and where 1 { P } \mathbf{1}\{P\} 1 { P } denotes the indicator of a condition P P P , equal to 1 if P P P holds and to 0 otherwise.
We compare these triples lexicographically, writing τ < l e x τ ′ \tau<_{\mathrm{lex}} \tau' τ < lex τ ′ for the resulting strict total order.
Definition 6.15 (Encoding). The encoding of a base-timestamp triple τ = ( s , m , δ ) \tau=(s,m,\delta) τ = ( s , m , δ ) is the integer
E ( τ ) ≜ s 2 + 2 m + δ . \mathcal{E}(\tau) \mathrel{\triangleq} s^2+2m+\delta. E ( τ ) ≜ s 2 + 2 m + δ . Intuitively, a triple’s first component s s s confines its encoding to the interval [ s 2 , ( s + 1 ) 2 ) [s^2,(s+1)^2) [ s 2 , ( 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 τ = T i ( F , o ) \tau=\mathcal{T}_i(F,o) τ = T i ( F , o ) satisfies
N ( F ) 2 ≤ E ( τ ) < ( N ( F ) + 1 ) 2 . N(F)^2 \le\mathcal{E}(\tau) < (N(F)+1)^2. N ( F ) 2 ≤ E ( τ ) < ( N ( F ) + 1 ) 2 . Proof. Let r i = rank ( F [ i ] ) r_i=\operatorname{rank}(F[i]) r i = rank ( F [ i ]) and r o = rank ( F [ o ] ) r_o=\operatorname{rank}(F[o]) r o = rank ( F [ o ]) , so that τ = ( s , m , δ ) \tau=(s,m,\delta) τ = ( s , m , δ ) with s = N ( F ) s=N(F) s = N ( F ) , m = min { r i , r o } m=\min\{r_i,r_o\} m = min { r i , r o } , and δ = 1 { r i > r o } ∈ { 0 , 1 } \delta=\mathbf{1}\{r_i>r_o\}\in\{0,1\} δ = 1 { r i > r o } ∈ { 0 , 1 } . Because ranks are nonnegative and F F F is a frontier, 0 ≤ r i , r o ≤ s 0\le r_i,r_o\le s 0 ≤ r i , r o ≤ s , and so 0 ≤ m ≤ s 0\le m\le s 0 ≤ m ≤ s .
If r i ≤ r o r_i\le r_o r i ≤ r o , then 2 m + δ = 2 r i ≤ 2 s 2m+\delta=2r_i\le2s 2 m + δ = 2 r i ≤ 2 s . If r i > r o r_i>r_o r i > r o , then 2 m + δ = 2 r o + 1 < 2 ( r o + 1 ) ≤ 2 r i ≤ 2 s 2m+\delta=2r_o+1<2(r_o+1)\le2r_i\le2s 2 m + δ = 2 r o + 1 < 2 ( r o + 1 ) ≤ 2 r i ≤ 2 s . Thus 0 ≤ 2 m + δ ≤ 2 s 0\le2m+\delta\le2s 0 ≤ 2 m + δ ≤ 2 s in both cases, and therefore
s 2 ≤ E ( τ ) = s 2 + 2 m + δ ≤ s 2 + 2 s < ( s + 1 ) 2 , s^2 \le\mathcal{E}(\tau)=s^2+2m+\delta\le s^2+2s<(s+1)^2, s 2 ≤ E ( τ ) = s 2 + 2 m + δ ≤ s 2 + 2 s < ( s + 1 ) 2 , which proves the claim.
Lemma 6.17 (Encoding order). For any base-timestamp triples τ \tau τ and τ ′ \tau' τ ′ ,
τ < l e x τ ′ ⟺ E ( τ ) < E ( τ ′ ) . \tau<_{\mathrm{lex}} \tau' \quad\Longleftrightarrow\quad\mathcal{E}(\tau)<\mathcal{E}(\tau'). τ < lex τ ′ ⟺ E ( τ ) < E ( τ ′ ) . Proof. Since < l e x <_{\mathrm{lex}} < lex is a strict total order, it suffices to prove the forward implication. Suppose τ = ( s , m , δ ) < l e x ( s ′ , m ′ , δ ′ ) = τ ′ \tau=(s,m,\delta)<_{\mathrm{lex}}(s',m',\delta')=\tau' τ = ( s , m , δ ) < lex ( s ′ , m ′ , δ ′ ) = τ ′ . If s < s ′ s<s' s < s ′ , then s + 1 ≤ s ′ s+1\le s' s + 1 ≤ s ′ and Proposition 6.16 gives
E ( τ ) < ( s + 1 ) 2 ≤ ( s ′ ) 2 ≤ E ( τ ′ ) . \mathcal{E}(\tau)<(s+1)^2\le(s')^2\le\mathcal{E}(\tau'). E ( τ ) < ( s + 1 ) 2 ≤ ( s ′ ) 2 ≤ E ( τ ′ ) . Otherwise s = s ′ s=s' s = s ′ and ( m , δ ) < l e x ( m ′ , δ ′ ) (m,\delta)<_{\mathrm{lex}}(m',\delta') ( m , δ ) < lex ( m ′ , δ ′ ) , so 2 m + δ < 2 m ′ + δ ′ 2m+\delta<2m'+\delta' 2 m + δ < 2 m ′ + δ ′ (as m , m ′ m,m' m , m ′ are integers and δ , δ ′ ∈ { 0 , 1 } \delta,\delta'\in\{0,1\} δ , δ ′ ∈ { 0 , 1 } ), and adding s 2 s^2 s 2 gives E ( τ ) < E ( τ ′ ) \mathcal{E}(\tau)<\mathcal{E}(\tau') E ( τ ) < E ( τ ′ ) .
Preliminary properties
The following are some simple invariants used throughout the safety proof.
Proposition 6.18. The following hold at every correct process p i p_i p i :
(a) f r o n t i e r i frontier_i f r o n t i e r i is a frontier and is non-decreasing under ⪯ \preceq ⪯ .
(b) The sequence numbers and ranks of labels created by p i p_i p i strictly increase with creation order.
(c) Messages sent by p i p_i p i on lines 13 and 17 are valid requests and valid replies, respectively.
Proposition 6.18(b) immediately implies the following.
Corollary 6.19. Let ℓ \ell ℓ and ℓ ′ \ell' ℓ ′ be labels created by the same correct process. If seq ( ℓ ) ≥ seq ( ℓ ′ ) \operatorname{seq}(\ell)\ge\operatorname{seq}(\ell') seq ( ℓ ) ≥ seq ( ℓ ′ ) , then rank ( ℓ ) ≥ rank ( ℓ ′ ) \operatorname{rank}(\ell)\ge\operatorname{rank}(\ell') rank ( ℓ ) ≥ rank ( ℓ ′ ) .
Next, we state some properties of a complete operation invoked by a correct process. Throughout, we denote by γ \gamma γ such an operation and p i p_i p i its invoker, and use the following notation (which also appears as right-margin tags in Algorithm 3):
ℓ γ \ell_\gamma ℓ γ is the label created for γ \gamma γ on line 9.
L γ L_\gamma L γ is the invoker’s frontier at the start of γ \gamma γ (line 6).
F γ 0 F_\gamma^0 F γ 0 is the frontier carried by γ \gamma γ ’s request, namely the value of f r o n t i e r i \mathrm{frontier}_i frontier i after line 11.
Q γ Q_\gamma Q γ is the value of Q Q Q on line 23.
o γ o_\gamma o γ is the value of o o o from line 24. (So Q γ = { 0 , … , n − 1 } ∖ { o γ } Q_\gamma= \{0,\ldots,n-1\} \setminus\{o_\gamma\} Q γ = { 0 , … , n − 1 } ∖ { o γ } .)
For j ∈ Q γ j \in Q_\gamma j ∈ Q γ , F γ , j F_{\gamma,j} F γ , j is the frontier in the unique reply from p j p_j p j that p i p_i p i receives during γ \gamma γ and that passes the check on line 19.
F γ F_\gamma F γ is the value of f r o n t i e r i \mathrm{frontier}_i frontier i when the check on line 22 succeeds.
τ γ = T i ( F γ , o γ ) \tau_\gamma= T_i(F_\gamma,o_\gamma) τ γ = T i ( F γ , o γ ) is the base-timestamp triple computed on line 25.
t γ = E ( τ γ ) t_\gamma= \mathcal{E}(\tau_\gamma) t γ = E ( τ γ ) is the base timestamp computed on line 26.
Proposition 6.20. Let p j p_j p j be a correct process such that j ∈ Q γ j \in Q_\gamma j ∈ Q γ , and let F F F be a frontier. If F ⪯ f r o n t i e r j F \preceq\mathrm{frontier}_j F ⪯ frontier j holds at some point before γ \gamma γ is invoked, then F ⪯ F γ F \preceq F_\gamma F ⪯ F γ .
Proof. Because p j p_j p j is correct, F γ , j F_{\gamma,j} F γ , j is the value of f r o n t i e r j \mathrm{frontier}_j frontier j when p j p_j p j replies to γ \gamma γ ’s request on line 17, after γ \gamma γ is invoked; frontier monotonicity (Proposition 6.18(a)) therefore gives F ⪯ F γ , j F \preceq F_{\gamma,j} F ⪯ F γ , j . Since j ∈ Q γ j \in Q_\gamma j ∈ Q γ , process p i p_i p i receives p j p_j p j ’s reply before γ \gamma γ completes, merging F γ , j F_{\gamma,j} F γ , j into f r o n t i e r i \mathrm{frontier}_i frontier i on line 21, after which F γ , j ⪯ f r o n t i e r i F_{\gamma,j} \preceq\mathrm{frontier}_i F γ , j ⪯ frontier i . Frontier monotonicity preserves this until the check on line 22 succeeds, at which point f r o n t i e r i = F γ \mathrm{frontier}_i = F_\gamma frontier i = F γ , so F γ , j ⪯ F γ F_{\gamma,j} \preceq F_\gamma F γ , j ⪯ F γ . By the transitivity of ⪯ \preceq ⪯ (Proposition 6.12(a)), we have F ⪯ F γ F \preceq F_\gamma F ⪯ F γ .
Corollary 6.21. Let p j p_j p j be a correct process with j ∈ Q γ j \in Q_\gamma j ∈ Q γ . For any k ∈ { 0 , … , n − 1 } k \in\{0,\ldots,n-1\} k ∈ { 0 , … , n − 1 } and s ∈ Z ≥ 0 s \in\mathbb{Z}_{\ge0} s ∈ Z ≥ 0 , suppose that seq ( f r o n t i e r j [ k ] ) ≥ s \operatorname{seq}(\mathrm{frontier}_j[k]) \ge s seq ( frontier j [ k ]) ≥ s at some point before γ \gamma γ is invoked. Then seq ( F γ [ k ] ) ≥ s \operatorname{seq}(F_\gamma[k]) \ge s seq ( F γ [ k ]) ≥ s .
Proposition 6.22. After p i p_i p i executes line 11 in invocation γ \gamma γ , label ( f r o n t i e r i [ i ] ) = ℓ γ \operatorname{label}(\mathrm{frontier}_i[i]) = \ell_\gamma label ( frontier i [ i ]) = ℓ γ holds until γ \gamma γ returns.
Proof. Line 11 sets f r o n t i e r i [ i ] \mathrm{frontier}_i[i] frontier i [ i ] to the certified label ( ℓ γ , a c k s i ) (\ell_\gamma,\mathrm{acks}_i) ( ℓ γ , acks i ) , so F γ 0 [ i ] ≠ ⊥ F_\gamma^0[i] \ne\bot F γ 0 [ i ] = ⊥ and label ( F γ 0 [ i ] ) = ℓ γ \operatorname{label}(F_\gamma^0[i]) = \ell_\gamma label ( F γ 0 [ i ]) = ℓ γ immediately after. Fix a point between then and γ \gamma γ ’s return, and let F F F be the value of f r o n t i e r i \mathrm{frontier}_i frontier i at that point. Frontier monotonicity (Proposition 6.18(a)) gives F γ 0 ⪯ F F_\gamma^0 \preceq F F γ 0 ⪯ F , so
seq ( F [ i ] ) ≥ seq ( F γ 0 [ i ] ) = seq ( ℓ γ ) ≥ 1. \operatorname{seq}(F[i]) \ge\operatorname{seq}(F_\gamma^0[i]) = \operatorname{seq}(\ell_\gamma) \ge1. seq ( F [ i ]) ≥ seq ( F γ 0 [ i ]) = seq ( ℓ γ ) ≥ 1.
In particular F [ i ] ≠ ⊥ F[i] \ne\bot F [ i ] = ⊥ , and origin ( F [ i ] ) = i \operatorname{origin}(F[i]) = i origin ( F [ i ]) = i because F F F is a frontier. So label ( F [ i ] ) \operatorname{label}(F[i]) label ( F [ i ]) carries correct process p i p_i p i ’s (unforgeable) signature and was therefore created by p i p_i p i . Since labels are created only on line 9 and p i p_i p i has at most one outstanding invocation, p i p_i p i creates no label after ℓ γ \ell_\gamma ℓ γ before γ \gamma γ returns. Every label that p i p_i p i created before ℓ γ \ell_\gamma ℓ γ has a smaller sequence number by Proposition 6.18(b), so label ( F [ i ] ) = ℓ γ \operatorname{label}(F[i]) = \ell_\gamma label ( F [ i ]) = ℓ γ .
Proposition 6.23. The following equalities hold:
(a) ℓ γ = label ( F γ 0 [ i ] ) = label ( F γ [ i ] ) \ell_\gamma= \operatorname{label}(F_\gamma^0[i]) = \operatorname{label}(F_\gamma[i]) ℓ γ = label ( F γ 0 [ i ]) = label ( F γ [ i ]) .
(b) seq ( ℓ γ ) = seq ( F γ 0 [ i ] ) = seq ( F γ [ i ] ) \operatorname{seq}(\ell_\gamma) = \operatorname{seq}(F_\gamma^0[i]) = \operatorname{seq}(F_\gamma[i]) seq ( ℓ γ ) = seq ( F γ 0 [ i ]) = seq ( F γ [ i ]) .
(c) rank ( ℓ γ ) = rank ( F γ 0 [ i ] ) = rank ( F γ [ i ] ) \operatorname{rank}(\ell_\gamma) = \operatorname{rank}(F_\gamma^0[i]) = \operatorname{rank}(F_\gamma[i]) rank ( ℓ γ ) = rank ( F γ 0 [ i ]) = rank ( F γ [ i ]) .
(d) rank ( ℓ γ ) = N ( F γ 0 ) \operatorname{rank}(\ell_\gamma) = N(F_\gamma^0) rank ( ℓ γ ) = N ( F γ 0 ) .
Proof. During the invocation of γ \gamma γ , line 11 sets frontier i [ i ] \operatorname{frontier}_i[i] frontier i [ i ] to a certified label containing ℓ γ \ell_\gamma ℓ γ . Hence, ℓ γ = label ( F γ 0 [ i ] ) \ell_\gamma= \operatorname{label}(F^0_\gamma[i]) ℓ γ = label ( F γ 0 [ i ]) . Moreover, F γ F_\gamma F γ is the value of frontier i \operatorname{frontier}_i frontier i when the check on line 22 succeeds, which precedes γ \gamma γ ’s return, so Proposition 6.22 gives label ( F γ [ i ] ) = ℓ γ \operatorname{label}(F_\gamma[i]) = \ell_\gamma label ( F γ [ i ]) = ℓ γ . We have thus proved part (a).
Applying seq \operatorname{seq} seq and rank \operatorname{rank} 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. F^0_\gamma[k] = L_\gamma[k]\quad(k \ne i), \qquad\operatorname{seq}(F^0_\gamma[i]) = \operatorname{seq}(L_\gamma[i]) + 1. 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 ( ℓ γ ) N(F^0_\gamma) = N(L_\gamma) + 1 = \operatorname{rank}(\ell_\gamma) N ( F γ 0 ) = N ( L γ ) + 1 = rank ( ℓ γ ) , proving part (d). □Proposition 6.23
Safety
Fix complete operations α \alpha α and β \beta β , invoked by correct processes p a p_a p a and p b p_b p b , respectively, such that α \alpha α returns before β \beta β 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 β F^0_\alpha\preceq F_\beta F α 0 ⪯ F β .
Proof. Since ∣ Q α ∣ = ∣ Q β ∣ = n − 1 |Q_\alpha| = |Q_\beta| = n - 1 ∣ Q α ∣ = ∣ Q β ∣ = n − 1 , we have ∣ Q α ∩ Q β ∣ ≥ 2 ( n − 1 ) − n = n − 2 ≥ 2 |Q_\alpha\cap Q_\beta| \ge2(n - 1) - n = n - 2 \ge2 ∣ Q α ∩ Q β ∣ ≥ 2 ( n − 1 ) − n = n − 2 ≥ 2 . Since at most one process is Byzantine, Q α ∩ Q β Q_\alpha\cap Q_\beta Q α ∩ Q β contains a correct process p i p_i p i .
Because i ∈ Q α i \in Q_\alpha i ∈ Q α , process p i p_i p i merges F α 0 F^0_\alpha F α 0 into frontier i \operatorname{frontier}_i frontier i on line 15, before α \alpha α returns. Thus F α 0 ⪯ frontier i F^0_\alpha\preceq\operatorname{frontier}_i F α 0 ⪯ frontier i at some point before β \beta β is invoked. Since i ∈ Q β i \in Q_\beta i ∈ Q β , Proposition 6.20 gives F α 0 ⪯ F β F^0_\alpha\preceq F_\beta F α 0 ⪯ F β . □Proposition 6.24
Proposition 6.25. seq ( F β [ a ] ) ≥ seq ( F α [ a ] ) \operatorname{seq}(F_\beta[a]) \ge\operatorname{seq}(F_\alpha[a]) seq ( F β [ a ]) ≥ seq ( F α [ a ]) and rank ( F β [ a ] ) ≥ rank ( F α [ a ] ) \operatorname{rank}(F_\beta[a]) \ge\operatorname{rank}(F_\alpha[a]) 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 , \operatorname{seq}(F_\beta[a]) \ge\operatorname{seq}(F^0_\alpha[a]) = \operatorname{seq}(F_\alpha[a]) = \operatorname{seq}(\ell_\alpha) \ge1, 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 ] ≠ ⊥ F_\alpha[a], F_\beta[a] \ne\bot F α [ a ] , F β [ a ] = ⊥ , which means they contain labels that carry correct process p a p_a p a ’s (unforgeable) signature, and so were created by p a p_a p a . The second inequality then follows from Corollary 6.19 . □Proposition 6.25
Proposition 6.26. If a ∈ Q β a \in Q_\beta a ∈ Q β , then F α ⪯ F β F_\alpha\preceq F_\beta F α ⪯ F β .
Proof. When the check on line 22 succeeds during α \alpha α , frontier a = F α \operatorname{frontier}_a = F_\alpha frontier a = F α ; this point precedes β \beta β ’s invocation. Since p a p_a p a is correct and a ∈ Q β a \in Q_\beta a ∈ Q β , Proposition 6.20 gives F α ⪯ F β F_\alpha\preceq F_\beta F α ⪯ F β . □Proposition 6.26
Lemma 6.27. For any j ∈ { 0 , … , n − 1 } j \in\{0, \ldots, n - 1\} j ∈ { 0 , … , n − 1 } , if seq ( F β [ j ] ) < seq ( F α [ j ] ) \operatorname{seq}(F_\beta[j]) < \operatorname{seq}(F_\alpha[j]) seq ( F β [ j ]) < seq ( F α [ j ]) , then process p j p_j p j is Byzantine and seq ( F β [ j ] ) ≥ seq ( F α [ j ] ) − 1 \operatorname{seq}(F_\beta[j]) \ge\operatorname{seq}(F_\alpha[j]) - 1 seq ( F β [ j ]) ≥ seq ( F α [ j ]) − 1 .
Proof. Fix j ∈ { 0 , … , n − 1 } j \in\{0, \ldots, n - 1\} j ∈ { 0 , … , n − 1 } and suppose
seq ( F β [ j ] ) < seq ( F α [ j ] ) . (6) \operatorname{seq}(F_\beta[j]) < \operatorname{seq}(F_\alpha[j]). \tag*{(6)} seq ( F β [ j ]) < seq ( F α [ j ]) . (6)
This implies seq ( F α [ j ] ) ≥ 1 \operatorname{seq}(F_\alpha[j]) \ge1 seq ( F α [ j ]) ≥ 1 ; in particular, F α [ j ] ≠ ⊥ F_\alpha[j] \ne\bot F α [ j ] = ⊥ . We proceed by proving four claims.
Claim 6.28. o β = a o_\beta= a o β = a .
Proof. By (6) , F α ⪯̸ F β F_\alpha\not\preceq F_\beta F α ⪯ F β . The contrapositive of Proposition 6.26 therefore gives a ∉ Q β a \notin Q_\beta a ∈ / Q β . By line 24, Q β Q_\beta Q β omits exactly o β o_\beta o β , so o β = a o_\beta= a o β = a and Q β = { 0 , … , n − 1 } ∖ { a } Q_\beta= \{0, \ldots, n - 1\} \setminus\{a\} Q β = { 0 , … , n − 1 } ∖ { a } . □Claim 6.28
Claim 6.29. j ∈ Q β j \in Q_\beta j ∈ Q β .
Proof. If j = a j = a j = a , then Proposition 6.25 gives seq ( F β [ a ] ) ≥ seq ( F α [ a ] ) \operatorname{seq}(F_\beta[a]) \ge\operatorname{seq}(F_\alpha[a]) seq ( F β [ a ]) ≥ seq ( F α [ a ]) , contradicting (6) . Hence j ≠ a j \ne a j = a , and Claim 6.28 gives j ∈ Q β j \in Q_\beta j ∈ Q β . □Claim 6.29
Claim 6.30. Process p j p_j p j is Byzantine. Proof. Suppose for contradiction that p j p_j p j is correct. Let ℓ = label ( F α [ j ] ) \ell= \operatorname{label}(F_\alpha[j]) ℓ = label ( F α [ j ]) . Since origin ( ℓ ) = j \operatorname{origin}(\ell) = j origin ( ℓ ) = j , the label ℓ \ell ℓ carries correct process p j p_j p j ’s (unforgeable) signature; hence p j p_j p j created ℓ \ell ℓ on line 9. Line 11 then assigns to frontierj [ j ] _j[j] j [ j ] a certified label containing ℓ \ell ℓ . Because ℓ \ell ℓ appears in F α F_\alpha F α , this assignment precedes α \alpha α ’s return, and so it precedes β \beta β ’s invocation.
Immediately after the assignment,
seq ( frontier j [ j ] ) = seq ( ℓ ) = seq ( F α [ j ] ) . \operatorname{seq}(\texttt{frontier}_j[j]) = \operatorname{seq}(\ell) = \operatorname{seq}(F_\alpha[j]). seq ( frontier j [ j ]) = seq ( ℓ ) = seq ( F α [ j ]) .
Since j ∈ Q β j \in Q_\beta j ∈ Q β by Claim 6.29, Corollary 6.21 gives
seq ( F β [ j ] ) ≥ seq ( ℓ ) = seq ( F α [ j ] ) , \operatorname{seq}(F_\beta[j]) \ge\operatorname{seq}(\ell) = \operatorname{seq}(F_\alpha[j]), seq ( F β [ j ]) ≥ seq ( ℓ ) = seq ( F α [ j ]) ,
contradicting (6) . Hence p j p_j p j is Byzantine.
Claim 6.31
Claim 6.31. seq ( F β [ j ] ) ≥ seq ( F α [ j ] ) − 1 \operatorname{seq}(F_\beta[j]) \ge\operatorname{seq}(F_\alpha[j]) - 1 seq ( F β [ j ]) ≥ seq ( F α [ j ]) − 1 .
Proof. The claim is immediate if seq ( F α [ j ] ) = 1 \operatorname{seq}(F_\alpha[j]) = 1 seq ( F α [ j ]) = 1 . Assume henceforth that seq ( F α [ j ] ) > 1 \operatorname{seq}(F_\alpha[j]) > 1 seq ( F α [ j ]) > 1 . The certified label F α [ j ] F_\alpha[j] F α [ j ] carries a quorum certificate for a label ℓ − \ell^{-} ℓ − satisfying
origin ( ℓ − ) = j , seq ( ℓ − ) = seq ( F α [ j ] ) − 1. \operatorname{origin}(\ell^{-}) = j,\qquad\operatorname{seq}(\ell^{-}) = \operatorname{seq}(F_\alpha[j]) - 1. origin ( ℓ − ) = j , seq ( ℓ − ) = seq ( F α [ j ]) − 1.
The certificate contains acknowledgments of ℓ − \ell^{-} ℓ − (of the form ⟨ ℓ − ⟩ σ k \langle\ell^{-}\rangle_{\sigma_k} ⟨ ℓ − ⟩ σ k ) from n − 1 n - 1 n − 1 processes, at least n − 2 n - 2 n − 2 of which are correct. Since Q β Q_\beta Q β omits only one process, at least n − 3 ≥ 1 n - 3 \ge1 n − 3 ≥ 1 of these correct processes belong to Q β Q_\beta Q β . Fix one such process p i p_i p i .
The quorum certificate in F α [ j ] F_\alpha[j] F α [ j ] contains an acknowledgment carrying correct process p i p_i p i ’s (unforgeable) signature, so p i p_i p i sent that acknowledgment on line 17 before α \alpha α returns. Before sending the acknowledgment, on line 15 p i p_i p i merges into frontieri _i i a frontier F F F with label ( F [ j ] ) = ℓ − \operatorname{label}(F[j]) = \ell^{-} label ( F [ j ]) = ℓ − . Immediately after,
seq ( frontier i [ j ] ) ≥ seq ( F [ j ] ) = seq ( ℓ − ) . \operatorname{seq}(\texttt{frontier}_i[j]) \ge\operatorname{seq}(F[j]) = \operatorname{seq}(\ell^{-}). seq ( frontier i [ j ]) ≥ seq ( F [ j ]) = seq ( ℓ − ) .
This holds at some point before β \beta β is invoked.
Since i ∈ Q β i \in Q_\beta i ∈ Q β , Corollary 6.21 now gives
seq ( F β [ j ] ) ≥ seq ( ℓ − ) = seq ( F α [ j ] ) − 1. \operatorname{seq}(F_\beta[j]) \ge\operatorname{seq}(\ell^{-}) = \operatorname{seq}(F_\alpha[j]) - 1. seq ( F β [ j ]) ≥ seq ( ℓ − ) = seq ( F α [ j ]) − 1.
Claims 6.30 and 6.31 establish the two conclusions. Lemma 6.27
Proposition 6.32
Proposition 6.32. seq ( ℓ β ) > seq ( F α [ b ] ) \operatorname{seq}(\ell_\beta) > \operatorname{seq}(F_\alpha[b]) seq ( ℓ β ) > seq ( F α [ b ]) and rank ( ℓ β ) > rank ( F α [ b ] ) \operatorname{rank}(\ell_\beta) > \operatorname{rank}(F_\alpha[b]) rank ( ℓ β ) > rank ( F α [ b ]) .
Proof. If F α [ b ] = ⊥ F_\alpha[b] = \bot F α [ b ] = ⊥ , the claim is immediate. Otherwise, label ( F α [ b ] ) \operatorname{label}(F_\alpha[b]) label ( F α [ b ]) carries correct process p b p_b p b ’s (unforgeable) signature, so p b p_b p b created it before α \alpha α returned, whereas it created ℓ β \ell_\beta ℓ β after β \beta β was invoked. Thus, ℓ β \ell_\beta ℓ β comes after label ( F α [ b ] ) \operatorname{label}(F_\alpha[b]) label ( F α [ b ]) in p b p_b p b ’s label-creation order and therefore has a larger sequence number and rank by Proposition 6.18 (b).
Proposition 6.33
Proposition 6.33. If b ∈ Q α b \in Q_\alpha b ∈ Q α , then rank ( ℓ β ) > rank ( ℓ α ) \operatorname{rank}(\ell_\beta) > \operatorname{rank}(\ell_\alpha) rank ( ℓ β ) > rank ( ℓ α ) .
Proof. By Proposition 6.23 , N ( F α 0 ) = rank ( ℓ α ) N(F_\alpha^0) = \operatorname{rank}(\ell_\alpha) N ( F α 0 ) = rank ( ℓ α ) . Because b ∈ Q α b \in Q_\alpha b ∈ Q α , process p b p_b p b merges F α 0 F_\alpha^0 F α 0 into frontierb _b b on line 15 upon receiving a request for α \alpha α —so before α \alpha α returns. Since α \alpha α returns before β \beta β is invoked, frontier monotonicity (Proposition 6.18 (a)) gives F α 0 ⪯ L β F_\alpha^0 \preceq L_\beta F α 0 ⪯ L β . Thus, by line 8 during β \beta β and Proposition 6.12 (c),
rank ( ℓ β ) = N ( L β ) + 1 ≥ N ( F α 0 ) + 1 = rank ( ℓ α ) + 1 > rank ( ℓ α ) . \operatorname{rank}(\ell_\beta) = N(L_\beta) + 1 \ge N(F_\alpha^0) + 1 = \operatorname{rank}(\ell_\alpha) + 1 > \operatorname{rank}(\ell_\alpha). rank ( ℓ β ) = N ( L β ) + 1 ≥ N ( F α 0 ) + 1 = rank ( ℓ α ) + 1 > rank ( ℓ α ) .
Proposition 6.34
Proposition 6.34 (Ordering for base timestamps). In Algorithm 3, if α \alpha α and β \beta β are complete operations invoked by correct processes and α \alpha α returns before β \beta β is invoked, then their base timestamps satisfy t β > t α t_\beta> t_\alpha t β > t α . Proof. Write
x α ≜ rank ( F α [ a ] ) = rank ( ℓ α ) , ( “=” by x r e f ‘ P r o p o s i t i o n 6.23 ‘ ) y α ≜ rank ( F α [ o α ] ) , x β ≜ rank ( F β [ b ] ) = rank ( ℓ β ) , ( “=” by x r e f ‘ P r o p o s i t i o n 6.23 ‘ ) y β ≜ rank ( F β [ o β ] ) . \begin{aligned}
x_{\alpha} &\triangleq\operatorname{rank}(F_{\alpha}[a])=\operatorname{rank}(\ell_{\alpha}), &&(\text{“=” by }{xref}`Proposition 6.23`)\\
y_{\alpha} &\triangleq\operatorname{rank}(F_{\alpha}[o_{\alpha}]),\\
x_{\beta} &\triangleq\operatorname{rank}(F_{\beta}[b])=\operatorname{rank}(\ell_{\beta}), &&(\text{“=” by }{xref}`Proposition 6.23`)\\
y_{\beta} &\triangleq\operatorname{rank}(F_{\beta}[o_{\beta}]).
\end{aligned} x α y α x β y β ≜ rank ( F α [ a ]) = rank ( ℓ α ) , ≜ rank ( F α [ o α ]) , ≜ rank ( F β [ b ]) = rank ( ℓ β ) , ≜ rank ( F β [ o β ]) . ( “=” by x r e f ‘ P r o p os i t i o n 6.23‘ ) ( “=” by x r e f ‘ P r o p os i t i o n 6.23‘ )
so that
τ α = ( N ( F α ) , min { x α , y α } , 1 { x α > y α } ) , τ β = ( N ( F β ) , min { x β , y β } , 1 { x β > y β } ) . \begin{aligned}
\tau_{\alpha}&=(N(F_{\alpha}),\min\{x_{\alpha},y_{\alpha}\},1\{x_{\alpha}>y_{\alpha}\}),\\
\tau_{\beta}&=(N(F_{\beta}),\min\{x_{\beta},y_{\beta}\},1\{x_{\beta}>y_{\beta}\}).
\end{aligned} τ α τ β = ( N ( F α ) , min { x α , y α } , 1 { x α > y α }) , = ( N ( F β ) , min { x β , y β } , 1 { x β > y β }) .
Since E \mathcal{E} E respects the lexicographic order of these triples (Lemma 6.17 ), it suffices to prove that τ β > l e x τ α \tau_{\beta}>_{\mathrm{lex}}\tau_{\alpha} τ β > lex τ α . We prove this via three claims, each comparing one component of τ α \tau_{\alpha} τ α and τ β \tau_{\beta} τ β under the assumption that the preceding components are equal.
Claim 6.35. N ( F β ) ≥ N ( F α ) N(F_{\beta})\ge N(F_{\alpha}) N ( F β ) ≥ N ( F α ) .
Proof. First, by Propositions 6.23 and 6.32,
seq ( F β [ b ] ) = seq ( ℓ β ) ≥ seq ( F α [ b ] ) + 1. (7) \operatorname{seq}(F_{\beta}[b])=\operatorname{seq}(\ell_{\beta})\ge\operatorname{seq}(F_{\alpha}[b])+1. \tag*{(7)} seq ( F β [ b ]) = seq ( ℓ β ) ≥ seq ( F α [ b ]) + 1. (7)
Next, since at most one process is Byzantine and p b p_b p b is correct, Lemma 6.27 ensures that there exists at most one index j ≠ b j\ne b j = b such that seq ( F β [ j ] ) < seq ( F α [ j ] ) \operatorname{seq}(F_{\beta}[j])<\operatorname{seq}(F_{\alpha}[j]) seq ( F β [ j ]) < seq ( F α [ j ]) , and that if such j j j exists, then seq ( F β [ j ] ) ≥ seq ( F α [ j ] ) − 1 \operatorname{seq}(F_{\beta}[j])\ge\operatorname{seq}(F_{\alpha}[j])-1 seq ( F β [ j ]) ≥ seq ( F α [ j ]) − 1 . Summing over i ≠ b i\ne b i = b therefore gives
∑ i ≠ b seq ( F β [ i ] ) ≥ ∑ i ≠ b seq ( F α [ i ] ) − 1. (8) \sum_{i\ne b}\operatorname{seq}(F_{\beta}[i])\ge\sum_{i\ne b}\operatorname{seq}(F_{\alpha}[i])-1. \tag*{(8)} i = b ∑ seq ( F β [ i ]) ≥ i = b ∑ seq ( F α [ i ]) − 1. (8)
Putting together (7) and (8), we get
N ( F β ) = seq ( F β [ b ] ) + ∑ i ≠ b seq ( F β [ i ] ) ≥ ( seq ( F α [ b ] ) + 1 ) + ( ∑ i ≠ b seq ( F α [ i ] ) − 1 ) = N ( F α ) , \begin{aligned}
N(F_{\beta})&=\operatorname{seq}(F_{\beta}[b])+\sum_{i\ne b}\operatorname{seq}(F_{\beta}[i])\\
&\ge\left(\operatorname{seq}(F_{\alpha}[b])+1\right)+\left(\sum_{i\ne b}\operatorname{seq}(F_{\alpha}[i])-1\right)\\
&=N(F_{\alpha}),
\end{aligned} N ( F β ) = seq ( F β [ b ]) + i = b ∑ seq ( F β [ i ]) ≥ ( seq ( F α [ b ]) + 1 ) + i = b ∑ seq ( F α [ i ]) − 1 = N ( F α ) ,
as claimed.
Claim 6.36. If N ( F β ) = N ( F α ) N(F_{\beta})=N(F_{\alpha}) N ( F β ) = N ( F α ) , then
y β ≥ x α ≥ min { x α , y α } , (9) y_{\beta}\ge x_{\alpha}\ge\min\{x_{\alpha},y_{\alpha}\}, \tag*{(9)} y β ≥ x α ≥ min { x α , y α } , (9) x β > min { x α , y α } . (10) x_{\beta}>\min\{x_{\alpha},y_{\alpha}\}. \tag*{(10)} x β > min { x α , y α } . (10) Consequently,
min { x β , y β } ≥ min { x α , y α } . \min\{x_{\beta},y_{\beta}\}\ge\min\{x_{\alpha},y_{\alpha}\}. min { x β , y β } ≥ min { x α , y α } .
Proof. Assume that N ( F β ) = N ( F α ) N(F_{\beta})=N(F_{\alpha}) N ( F β ) = N ( F α ) . We first show that a ∉ Q β a\notin Q_{\beta} a ∈ / Q β . Suppose instead that a ∈ Q β a\in Q_{\beta} a ∈ Q β . Then Proposition 6.26 gives F α ⪯ F β F_{\alpha}\preceq F_{\beta} F α ⪯ F β , so seq ( F β [ i ] ) ≥ seq ( F α [ i ] ) \operatorname{seq}(F_{\beta}[i])\ge\operatorname{seq}(F_{\alpha}[i]) seq ( F β [ i ]) ≥ seq ( F α [ i ]) for every i i i . But seq ( F β [ b ] ) > seq ( F α [ b ] ) \operatorname{seq}(F_{\beta}[b])>\operatorname{seq}(F_{\alpha}[b]) seq ( F β [ b ]) > seq ( F α [ b ]) by (7). Summing over all i i i then yields N ( F β ) > N ( F α ) N(F_{\beta})>N(F_{\alpha}) N ( F β ) > N ( F α ) , contradicting our assumption.
Since Q β Q_{\beta} Q β omits only one index, we conclude that o β = a o_{\beta}=a o β = a , so y β = rank ( F β [ a ] ) y_{\beta}=\operatorname{rank}(F_{\beta}[a]) y β = rank ( F β [ a ]) . Proposition 6.25 immediately gives y β ≥ x α y_{\beta}\ge x_{\alpha} y β ≥ x α , proving (9).
For (10), if b ∈ Q α b\in Q_{\alpha} b ∈ Q α , then Proposition 6.33 gives x β > x α ≥ min { x α , y α } x_{\beta}>x_{\alpha}\ge\min\{x_{\alpha},y_{\alpha}\} x β > x α ≥ min { x α , y α } ; otherwise, o α = b o_{\alpha}=b o α = b , so y α = rank ( F α [ b ] ) y_{\alpha}=\operatorname{rank}(F_{\alpha}[b]) y α = rank ( F α [ b ]) and Proposition 6.32 gives x β > y α ≥ min { x α , y α } x_{\beta}>y_{\alpha}\ge\min\{x_{\alpha},y_{\alpha}\} x β > y α ≥ min { x α , y α } . So in both cases, x β > min { x α , y α } x_{\beta}>\min\{x_{\alpha},y_{\alpha}\} x β > min { x α , y α } .
Inequalities (9) and (10) together imply that min { x β , y β } ≥ min { x α , y α } \min\{x_{\beta},y_{\beta}\}\ge\min\{x_{\alpha},y_{\alpha}\} min { x β , y β } ≥ min { x α , y α } .
Claim 6.37. If N ( F β ) = N ( F α ) N(F_{\beta}) = N(F_{\alpha}) N ( F β ) = N ( F α ) and min { x β , y β } = min { x α , y α } \min\{x_{\beta}, y_{\beta}\} = \min\{x_{\alpha}, y_{\alpha}\} min { x β , y β } = min { x α , y α } , then
1 { x β > y β } > 1 { x α > y α } . 1\{x_{\beta} > y_{\beta}\} > 1\{x_{\alpha} > y_{\alpha}\}. 1 { x β > y β } > 1 { x α > y α } . Proof. Suppose N ( F β ) = N ( F α ) N(F_{\beta}) = N(F_{\alpha}) N ( F β ) = N ( F α ) and min { x β , y β } = min { x α , y α } \min\{x_{\beta}, y_{\beta}\} = \min\{x_{\alpha}, y_{\alpha}\} min { x β , y β } = min { x α , y α } . By Claim 6.36 , inequalities (9) and (10) hold. By (10), x β > min { x β , y β } x_{\beta} > \min\{x_{\beta}, y_{\beta}\} x β > min { x β , y β } , so y β = min { x β , y β } = min { x α , y α } y_{\beta} = \min\{x_{\beta}, y_{\beta}\} = \min\{x_{\alpha}, y_{\alpha}\} y β = min { x β , y β } = min { x α , y α } . Combined with (9), this gives y β = x α = min { x α , y α } y_{\beta} = x_{\alpha} = \min\{x_{\alpha}, y_{\alpha}\} 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. \begin{aligned}
x_{\alpha} &= \min\{x_{\alpha}, y_{\alpha}\} \le y_{\alpha}, && \text{so } 1\{x_{\alpha} > y_{\alpha}\} = 0;\\
x_{\beta} &> \min\{x_{\beta}, y_{\beta}\} = y_{\beta}, && \text{so } 1\{x_{\beta} > y_{\beta}\} = 1.
\end{aligned} x α x β = min { x α , y α } ≤ y α , > min { x β , y β } = y β , so 1 { x α > y α } = 0 ; so 1 { x β > y β } = 1. This proves 1 { x β > y β } > 1 { x α > y α } 1\{x_{\beta} > y_{\beta}\} > 1\{x_{\alpha} > y_{\alpha}\} 1 { x β > y β } > 1 { x α > y α } .
Claims 6.35 to 6.37 together show that τ β > l e x τ α \tau_{\beta} >_{\mathrm{lex}} \tau_{\alpha} τ β > lex τ α . Therefore, t β = E ( τ β ) > E ( τ α ) = t α t_{\beta} = \mathcal{E}(\tau_{\beta}) > \mathcal{E}(\tau_{\alpha}) = t_{\alpha} t β = E ( τ β ) > E ( τ α ) = t α .
Proposition 6.38 (Return values). Algorithm 3 returns positive integers from next() and satisfies ordering ( B T 1 a ) (BT1a) ( B T 1 a ) and uniqueness ( B T 1 b ) (BT1b) ( B T 1 b ) .
Proof. Consider a complete operation γ \gamma γ at a correct process p i p_i p i . By Proposition 6.23 (b), N ( F γ ) ≥ seq ( F γ [ i ] ) = seq ( ℓ γ ) ≥ 1 N(F_{\gamma}) \ge\operatorname{seq}(F_{\gamma}[i]) = \operatorname{seq}(\ell_{\gamma}) \ge1 N ( F γ ) ≥ seq ( F γ [ i ]) = seq ( ℓ γ ) ≥ 1 . Thus, Proposition 6.16 gives t γ ≥ N ( F γ ) 2 ≥ 1 t_{\gamma} \ge N(F_{\gamma})^2 \ge1 t γ ≥ N ( F γ ) 2 ≥ 1 , so both t γ t_{\gamma} t γ and n ⋅ t γ + i n \cdot t_{\gamma} + i n ⋅ t γ + i are positive integers.
For ( B T 1 a ) (BT1a) ( B T 1 a ) , suppose a complete operation α \alpha α at a correct process p a p_a p a precedes a complete operation β \beta β at a correct process p b p_b p b . By Proposition 6.34, t α < t β t_{\alpha} < t_{\beta} t α < t β , so n ⋅ t α + a < n ⋅ ( t α + 1 ) ≤ n ⋅ t β + b n \cdot t_{\alpha} + a < n \cdot(t_{\alpha} + 1) \le n \cdot t_{\beta} + b n ⋅ t α + a < n ⋅ ( t α + 1 ) ≤ n ⋅ t β + b .
For ( B T 1 b ) (BT1b) ( B T 1 b ) , timestamps returned by different correct processes differ modulo n n n , and those returned by the same correct process are distinct by ( B T 1 a ) (BT1a) ( B T 1 a ) since its operations are sequential.
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 n - 1 n − 1 processes, including the invoker itself, are correct, so eventually the invoker accepts n − 1 n - 1 n − 1 replies, the check on line 22 succeeds, and the invoker returns on line 28.
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:
Figure 9.
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.
Latency Lower Bounds
The latency lower bounds for systems with crash failures (§ 5 ) 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 f \ge2 f ≥ 2 , then any implementation of TS has worst-case message delay at least three.
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 > 3 f n > 3f n > 3 f .
We next state the optimal latency for implementations of TS in systems with Byzantine processes and digital signatures. When n > 3 f n > 3f n > 3 f and f ≥ 2 f \ge2 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 > 3 f n > 3f n > 3 f and f ≥ 2 f \ge2 f ≥ 2 , then the optimal latency of implementing TS is three message delays.
When n > 3 f n > 3f n > 3 f and f = 1 f = 1 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 > 3 f n > 3f n > 3 f and f = 1 f = 1 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.
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 n \ge2 n ≥ 2 processes, of which at most f ≥ 1 f \ge1 f ≥ 1 may be Byzantine.
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 > 3 f n > 3f n > 3 f .
Latency Upper Bound
Theorem 7.2. In a system with Byzantine processes, if n > 3 f n > 3f n > 3 f , then there exists an implementation of TS (Algorithm 4) whose worst-case message delay is three.
Proof. The algorithm uses three types of messages. We call a message valid if it has one of the following forms:
a request ⟨ R e q q ⟩ \langle\mathrm{Req}\ q\rangle ⟨ Req q ⟩ , where q q q is an integer;
a proposal ⟨ P r o p ⟨ k , q ⟩ , v ⟩ \langle\mathrm{Prop}\ \langle k,q\rangle,v\rangle ⟨ Prop ⟨ k , q ⟩ , v ⟩ , where k ∈ { 0 , … , n − 1 } k \in\{0,\ldots,n-1\} k ∈ { 0 , … , n − 1 } and q q q and v v v are integers;
an echo ⟨ E c h o q , j , v ⟩ \langle\mathrm{Echo}\ q,j,v\rangle ⟨ Echo q , j , v ⟩ , where j ∈ { 0 , … , n − 1 } j \in\{0,\ldots,n-1\} j ∈ { 0 , … , n − 1 } and q q q and v v 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 p i p_i p i , its local clock x i x_i x i is non-decreasing.
Proof. After initialization, the only assignments to x i x_i x i are on lines 14 and 19, neither of which decreases x i x_i x i .
Claim 7.4. If the set c e r t i f i e d certified cer t i f i e d computed by a correct process p i p_i p i on line 25 contains ⟨ j , v ⟩ \langle j,v\rangle ⟨ j , v ⟩ , then at that time, at least n − 2 f n-2f n − 2 f correct processes p k p_k p k satisfy x k ≥ v x_k \ge v x k ≥ v .
Proof. Let S = { k : e c h o V a l i [ j , k ] = v } S = \{k : echoVal_i[j,k] = v\} S = { k : ec h o V a l i [ j , k ] = v } when p i p_i p i executes line 25. Then ∣ S ∣ ≥ n − f |S| \ge n-f ∣ S ∣ ≥ n − f , so at least n − 2 f n-2f n − 2 f indices in S S S belong to correct processes. For each such correct index k k k , process p k p_k p k sent its Echo message only after line 19 made x k ≥ v x_k \ge v x k ≥ v . By Claim 7.3, x k ≥ v x_k \ge v x k ≥ v still holds when p i p_i p i executes line 25.
Claim 7.5. If an invocation of n e x t ( ) \mathrm{next}() next ( ) by a correct process computes base timestamp t t t on line 29, then at the time of return, at least n − 2 f n-2f n − 2 f correct processes p k p_k p k satisfy x k ≥ t x_k \ge t x k ≥ t .
Proof. By line 29, ⟨ j , t ⟩ ∈ c e r t i f i e d \langle j,t\rangle\in certified ⟨ j , t ⟩ ∈ cer t i f i e d for some j j j . By Claim 7.4, x k ≥ t x_k \ge t x k ≥ t for at least n − 2 f n-2f n − 2 f correct processes p k p_k p k when c e r t i f i e d certified cer t i f i e d is computed, and Claim 7.3 implies that these inequalities still hold when the invocation returns.
Claim 7.6. If the set c e r t i f i e d certified cer t i f i e d computed by a correct process p i p_i p i on line 25 contains both ⟨ j , v ⟩ \langle j,v\rangle ⟨ j , v ⟩ and ⟨ j , v ′ ⟩ \langle j,v'\rangle ⟨ j , v ′ ⟩ , then v = v ′ v=v' v = v ′ .
Proof. Let S u = { k : e c h o V a l i [ j , k ] = u } S_u = \{k : echoVal_i[j,k] = u\} S u = { k : ec h o V a l i [ j , k ] = u } when p i p_i p i executes line 25. Suppose v ≠ v ′ v \ne v' v = v ′ . Since both pairs belong to c e r t i f i e d certified cer t i f i e d , we have ∣ S v ∣ , ∣ S v ′ ∣ ≥ n − f |S_v|,|S_{v'}| \ge n-f ∣ S v ∣ , ∣ S v ′ ∣ ≥ n − f . Since each entry e c h o V a l i [ j , k ] echoVal_i[j,k] ec h o V a l i [ j , k ] records at most one non-⊥ \perp ⊥ value, S v ∩ S v ′ = ∅ S_v \cap S_{v'} = \varnothing S v ∩ S v ′ = ∅ . But ∣ S v ∩ S v ′ ∣ = ∣ S v ∣ + ∣ S v ′ ∣ − ∣ S v ∪ S v ′ ∣ ≥ 2 ( n − f ) − n = n − 2 f > 0 |S_v \cap S_{v'}| = |S_v|+|S_{v'}|-|S_v \cup S_{v'}| \ge2(n-f)-n = n-2f > 0 ∣ S v ∩ S v ′ ∣ = ∣ S v ∣ + ∣ S v ′ ∣ − ∣ S v ∪ S v ′ ∣ ≥ 2 ( n − f ) − n = n − 2 f > 0 , a contradiction.
Claim 7.7 (Ordering for base timestamps). Suppose two n e x t ( ) \mathrm{next}() next ( ) operations invoked by correct processes compute base timestamps t t t and t ′ t' t ′ on line 29, respectively. If the first returns before the second is invoked, then t < t ′ t<t' t < t ′ .
Proof. By Claim 7.5, when the first operation returns, there is a set C C C of process indices such that ∣ C ∣ ≥ n − 2 f |C| \ge n-2f ∣ C ∣ ≥ n − 2 f and for every k ∈ C k \in C k ∈ C , p k p_k p k is correct and x k ≥ t x_k \ge t x k ≥ t . By Claim 7.3, these inequalities still hold when the second operation is invoked and thereafter.
Let p j p_j p j be the process performing the second operation, let q j q_j q j be the value of s e q j seq_j se q j when it is invoked, let c e r t i f i e d ′ certified' cer t i f i e d ′ be p j p_j p j ’s certified set when it returns on line 30, and let P = { k : ⟨ k , − ⟩ ∈ c e r t i f i e d ′ } P = \{k : \langle k,-\rangle\in certified'\} P = { k : ⟨ k , − ⟩ ∈ cer t i f i e d ′ } . The check on line 26 ensures that ∣ c e r t i f i e d ′ ∣ ≥ n − f |certified'| \ge n-f ∣ cer t i f i e d ′ ∣ ≥ n − f . By Claim 7.6, distinct pairs in c e r t i f i e d ′ certified' cer t i f i e d ′ have distinct first components, so ∣ P ∣ = ∣ c e r t i f i e d ′ ∣ ≥ n − f |P| = |certified'| \ge n-f ∣ P ∣ = ∣ cer t i f i e d ′ ∣ ≥ n − f . Hence,
∣ C ∩ P ∣ = ∣ C ∣ + ∣ P ∣ − ∣ C ∪ P ∣ ≥ ( n − 2 f ) + ( n − f ) − n = n − 3 f > 0 |C \cap P| = |C| + |P| - |C \cup P| \ge(n-2f) + (n-f) - n = n-3f > 0 ∣ C ∩ P ∣ = ∣ C ∣ + ∣ P ∣ − ∣ C ∪ P ∣ ≥ ( n − 2 f ) + ( n − f ) − n = n − 3 f > 0
so we may fix some ℓ ∈ C ∩ P \ell\in C \cap P ℓ ∈ C ∩ P ; process p ℓ p_\ell p ℓ is correct.
Since ℓ ∈ P \ell\in P ℓ ∈ P , there is a value v ℓ v_\ell v ℓ such that ⟨ ℓ , v ℓ ⟩ ∈ c e r t i f i e d ′ \langle\ell,v_\ell\rangle\in certified' ⟨ ℓ , v ℓ ⟩ ∈ cer t i f i e d ′ . By line 25, process p j p_j p j received an ⟨ E c h o q j , ℓ , v ℓ ⟩ \langle\mathrm{Echo}\ q_j,\ell,v_\ell\rangle ⟨ Echo q j , ℓ , v ℓ ⟩ message from at least n − f n-f n − f distinct processes; at least n − 2 f > 0 n-2f>0 n − 2 f > 0 of them are correct, so fix one such correct process p m p_m p m . By line 20, p m p_m p m sent that Echo only after receiving from p ℓ p_\ell p ℓ the message
Algorithm 4 A worst-case three-delay implementation of TS in a system with Byzantine processes where n > 3 f n > 3f n > 3 f .
Code for process p i p_i p i (0 ≤ i < n 0 \le i < n 0 ≤ i < n ):
1: x_i ← 0 ▷ p_i’s local clock.
2: seq_i ← 0 ▷ Sequence number of p_i’s ongoing invocation, or of its next invocation when idle.
3: reqSeq_i[k] ← −1 for each k ▷ Largest q in a ⟨Req q⟩ received from p_k.
4: propSeq_i[k, j] ← −1 for each k, j ▷ Largest q in a ⟨Prop ⟨k, q⟩, −⟩ received from p_j.
5: phase_i ← idle ▷ Whether p_i is idle or has an ongoing invocation.
6: echoVal_i[j, k] ← ⊥ for each j, k ▷ p_j’s proposal for p_i’s ongoing invocation as echoed by p_k.
7: upon invocation of next() do
8: phase_i ← ongoing
9: echoVal_i[j, k] ← ⊥ for each j, k
10: send ⟨Req seq_i⟩ to every process
11: upon receive valid ⟨Req q⟩ from p_k do
12: if q > reqSeq_i[k] then
13: reqSeq_i[k] ← q
14: x_i ← x_i + 1
15: send ⟨Prop ⟨k, q⟩, x_i⟩ to every process
16: upon receive valid ⟨Prop ⟨k, q⟩, v⟩ from p_j do
17: if q > propSeq_i[k, j] then
18: propSeq_i[k, j] ← q
19: x_i ← max(x_i, v)
20: send ⟨Echo q, j, v⟩ to p_k ▷ p_i says to p_k: “p_j proposed v for your invocation q.”
21: upon receive valid ⟨Echo q, j, v⟩ from p_k do
22: if phase_i = ongoing and q = seq_i then
23: if echoVal_i[j, k] = ⊥ then
24: echoVal_i[j, k] ← v
25: certified ← {⟨j′, v′⟩ : v′ ≠ ⊥, |{k′ : echoVal_i[j′, k′] = v′}| ≥ n − f}
▷ The proposal by p_j′ of value v′ is certified once it is echoed by n − f distinct processes p_k′.
26: if |certified| ≥ n − f then
27: phase_i ← idle
28: seq_i ← seq_i + 1
29: t ← max{v′ : ⟨j′, v′⟩ ∈ certified} ▷ Base timestamp.
30: return n · t + i ▷ Completes the next() invocation.
⟨ P r o p ⟨ j , q j ⟩ , v ℓ ⟩ \langle\mathrm{Prop}\ \langle j,q_j\rangle,v_\ell\rangle ⟨ Prop ⟨ j , q j ⟩ , v ℓ ⟩ . As p ℓ p_\ell p ℓ is correct, it sent that P r o p \mathrm{Prop} Prop to every process on line 15 immediately after executing x ℓ ← x ℓ + 1 x_\ell\leftarrow x_\ell+1 x ℓ ← x ℓ + 1 on line 14, upon receiving the R e q \mathrm{Req} Req message that p j p_j p j sent at the start of the second operation. Because ℓ ∈ C \ell\in C ℓ ∈ C , x ℓ ≥ t x_\ell\geq t x ℓ ≥ t immediately before this assignment, so v ℓ ≥ t + 1 > t v_\ell\geq t+1>t v ℓ ≥ t + 1 > t . Since line 29 computes the base timestamp as the maximum value in c e r t i f i e d ′ certified' cer t i f i e d ′ , we have t ′ ≥ v ℓ > t t' \geq v_\ell> t t ′ ≥ v ℓ > t . □Claim 7.7
Claim 7.8 (Return values). Algorithm 4 returns positive integers from next ( ) \operatorname{next}() next ( ) and satisfies ordering (BT1a) and uniqueness (BT1b).
Proof. Consider a complete operation at a correct process p i p_i p i with base timestamp t t t , and let c e r t i f i e d certified cer t i f i e d be the set from which t t t is computed. By the check on line 26, this set contains at least n − f n-f n − f pairs, whose first components are distinct by Claim 7.6. Since n − f > f n-f>f n − f > f , c e r t i f i e d certified cer t i f i e d contains a pair ⟨ ℓ , v ℓ ⟩ \langle\ell,v_\ell\rangle ⟨ ℓ , v ℓ ⟩ such that p ℓ p_\ell p ℓ is correct. Some correct process echoed v ℓ v_\ell v ℓ after receiving it in a P r o p \mathrm{Prop} Prop message from p ℓ p_\ell p ℓ , which sent that message right after incrementing x ℓ x_\ell x ℓ on line 14; hence v ℓ ≥ 1 v_\ell\geq1 v ℓ ≥ 1 . Moreover, every value in c e r t i f i e d certified cer t i f i e d is an integer, since it comes from a valid E c h o \mathrm{Echo} Echo message. Thus, t t t , the maximum of these values, is a positive integer, and so is n ⋅ t + i n\cdot t+i n ⋅ t + i .
For (BT1a), suppose a complete operation at a correct process p i p_i p i with base timestamp t t t precedes one at a correct process p j p_j p j with base timestamp t ′ t' t ′ . By Claim 7.7, t < t ′ t<t' t < t ′ , so n ⋅ t + i < n ⋅ ( t + 1 ) ≤ n ⋅ t ′ + j n\cdot t+i<n\cdot(t+1)\leq n\cdot t'+j n ⋅ t + i < n ⋅ ( t + 1 ) ≤ n ⋅ t ′ + j .
For (BT1b), timestamps returned by different correct processes differ modulo n n 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 ( ) \operatorname{next}() next ( ) by a correct process eventually returns.
Proof. Every message sent by a correct process is valid, since seq i \operatorname{seq}_i seq i and x i x_i x i always hold integers and every other field is either a process index or copied from a valid message. Let p i p_i p i be a correct process that invokes next ( ) \operatorname{next}() next ( ) , and let q q q be the value of seq i \operatorname{seq}_i seq i at that invocation. By initialization (lines 2 and 3) and the increment of seq i \operatorname{seq}_i seq i after each return (line 28), the R e q \mathrm{Req} Req message for q q q is fresh at every correct process. Hence every correct process eventually receives it, passes the check on line 12, and sends a corresponding P r o p \mathrm{Prop} Prop message to every process.
Until the invocation returns, p i p_i p i remains in phase ongoing with seq i = q \operatorname{seq}_i=q seq i = q and sends no request with a higher sequence number. Likewise, by initialization (lines 2 and 4) and the increment of seq i \operatorname{seq}_i seq i after each return (line 28), every P r o p \mathrm{Prop} Prop message for q q q from a correct proposer is fresh at every correct process, which eventually passes the check on line 17 and sends the corresponding E c h o \mathrm{Echo} Echo to p i p_i p i . Thus, for each of at least n − f n-f n − f correct proposers, p i p_i p i eventually receives n − f n-f n − f matching E c h o \mathrm{Echo} Echo messages.
Since the corresponding echoVal i \operatorname{echoVal}_i echoVal i entries were reset to ⊥ \perp ⊥ when the invocation began, p i p_i p i records all n − f n-f n − f echoes on line 24; together, the resulting entries certify the proposal. Consequently, the condition ∣ c e r t i f i e d ∣ ≥ n − f |certified|\geq n-f ∣ cer t i f i e d ∣ ≥ n − f eventually holds, and p i p_i p i 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 R e q \mathrm{Req} Req delay, one P r o p \mathrm{Prop} Prop delay, and one E c h o \mathrm{Echo} Echo delay, as illustrated below (where a thin arrow denotes a single message and a thick arrow denotes multiple messages):
Figure 10 (PDF p. 33).
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
Latency Lower Bounds
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 \mathcal{A} 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 \mathcal{A} A be an implementation of TS. Then there exists a loquacious implementation A ′ \mathcal{A}' A ′ of TS such that δ ( A ′ ) ≤ δ ( A ) \delta(\mathcal{A}') \le\delta(\mathcal{A}) δ ( A ′ ) ≤ δ ( A ) .
We defer its proof to Appendix § 17 .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 Q Q must follow A \mathcal{A} A throughout the prefix. Without this requirement, p p p may deviate from the algorithm and fail to return; alternatively, another process q ∈ Q q \in Q q ∈ Q may send a reply that p p p recognizes as invalid, in which case p p p may, without violating the two-delay bound, disregard it and wait for a reply from a process outside Q Q 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 μ \mu μ , we write μ [ i . . j ] \mu[i..j] μ [ i .. j ] for the contiguous subsequence μ [ i ] , … , μ [ j ] \mu[i], \ldots, \mu[j] μ [ i ] , … , μ [ j ] .)
Lemma 7.12 (Byzantine version of Lemma 4.21). In a system with Byzantine processes, let A \mathcal{A} A be a loquacious algorithm with δ ( A ) ≤ 2 \delta(\mathcal{A}) \le2 δ ( A ) ≤ 2 . Let p p p be a process, and let Q Q Q be a set of processes such that ∣ Q ∣ = n − f |Q| = n - f ∣ Q ∣ = n − f and p ∈ Q p \in Q p ∈ Q .
Suppose that σ \sigma σ is a schedule prefix of A \mathcal{A} A in which the following hold:
Process p p p invokes an operation and broadcasts a message m m m in step σ [ a ] \sigma[a] σ [ a ] .
For each q ∈ Q q \in Q q ∈ Q , process q q q receives m m m and broadcasts a message m q m_q m q in step σ [ j q ] \sigma[j_q] σ [ j q ] .
Process p p p receives the set of messages { m q : q ∈ Q } \{m_q : q \in Q\} { m q : q ∈ Q } in step σ [ b ] \sigma[b] σ [ b ] .
Between steps σ [ a ] \sigma[a] σ [ a ] and σ [ b ] \sigma[b] σ [ b ] , inclusive, the only steps are those specified above.
Processes in Q Q Q follow the algorithm A \mathcal{A} A throughout σ [ 0.. b ] \sigma[0..b] σ [ 0.. b ] .
Then the operation invoked by p p p in step σ [ a ] \sigma[a] σ [ a ] returns no later than step σ [ b ] \sigma[b] σ [ b ] .
Its proof is very close to that of Lemma 4.21; we defer it to Appendix § 17 .3.2.
The Bounds
The latency lower bounds for systems with crash failures (§ 5 ) 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 f \ge2 f ≥ 2 , then any implementation of TS has worst-case message delay at least three.
When f = 1 f = 1 f = 1 , the best lower bound we obtain for n > 4 n > 4 n > 4 is two delays (from Observation 7.13 ). However, in the boundary case n = 4 n = 4 n = 4 , we prove a stronger lower bound of three delays.
Theorem 7.15. In a system with Byzantine processes, if n = 4 n = 4 n = 4 and f = 1 f = 1 f = 1 , then any implementation of TS has worst-case message delay at least three.
Proof. Consider a system with n = 4 n = 4 n = 4 processes named { p 0 , p 1 , p 2 , p 3 } \{p_0,p_1,p_2,p_3\} { p 0 , p 1 , p 2 , p 3 } , at most f = 1 f = 1 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 \mathcal{A} A of TS with δ ( A ) < 3 \delta(\mathcal{A}) < 3 δ ( A ) < 3 . Since finite worst-case message delays are integers (Proposition 2.8), δ ( A ) ≤ 2 \delta(\mathcal{A}) \le2 δ ( A ) ≤ 2 . By Proposition 5.3 , A \mathcal{A} A satisfies ordering (BT1a).
We construct four schedule prefixes of A \mathcal{A} A : two auxiliary prefixes α 0 \alpha_0 α 0 and α 1 \alpha_1 α 1 as shown in Figure 2 a, and two principal prefixes σ 01 \sigma_{01} σ 01 and σ 10 \sigma_{10} σ 10 as shown in Figure 2 b.
Figure 2. Figure 2: Proof of Theorem 7.15 . In a system with n = 4 n = 4 n = 4 processes, at most f = 1 f = 1 f = 1 of which may be Byzantine, suppose toward a contradiction that some loquacious implementation A \mathcal{A} A of TS has δ ( A ) ≤ 2 \delta(\mathcal{A}) \le2 δ ( 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 r r indicates that it has returned r r 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 \mathcal{A} 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 p 0 p_0 p 0 in α 0 \alpha_0 α 0 and p 1 p_1 p 1 in α 1 \alpha_1 α 1 return by the final depicted steps; let r 0 r_0 r 0 and r 1 r_1 r 1 denote their respective return values. Process p 0 p_0 p 0 cannot distinguish either principal prefix from α 0 \alpha_0 α 0 , and p 1 p_1 p 1 cannot distinguish either from α 1 \alpha_1 α 1 . Thus, in both principal prefixes, p 0 p_0 p 0 returns r 0 r_0 r 0 and p 1 p_1 p 1 returns r 1 r_1 r 1 . Condition (BT1a) then gives r 0 < r 1 r_0 < r_1 r 0 < r 1 in σ 01 \sigma_{01} σ 01 and r 1 < r 0 r_1 < r_0 r 1 < r 0 in σ 10 \sigma_{10} σ 10 , a contradiction.
First consider the auxiliary prefixes α 0 \alpha_0 α 0 and α 1 \alpha_1 α 1 , shown in Figure 2 a. Schedule prefix α 0 \alpha_0 α 0 begins with process p 1 p_1 p 1 invoking an operation and p 2 p_2 p 2 receiving its broadcast. Next, p 0 p_0 p 0 invokes an operation and broadcasts a message. Processes p 0 p_0 p 0 , p 2 p_2 p 2 , p 3 p_3 p 3 each receive this message and broadcast a reply, in three separate steps, after which p 0 p_0 p 0 receives all three replies in a single step. All processes follow A \mathcal{A} A , so by Lemma 7.12 (with p = p 0 p = p_0 p = p 0 and Q = { p 0 , p 2 , p 3 } Q = \{p_0,p_2,p_3\} Q = { p 0 , p 2 , p 3 } ), p 0 p_0 p 0 ’s operation has returned by the final step; let r 0 r_0 r 0 be the value returned. Similarly, in α 1 \alpha_1 α 1 , process p 0 p_0 p 0 invokes an operation and p 3 p_3 p 3 receives its broadcast before p 1 p_1 p 1 invokes an operation and completes an analogous round trip with p 1 p_1 p 1 , p 2 p_2 p 2 , p 3 p_3 p 3 . Again, by Lemma 7.12 (with p = p 1 p = p_1 p = p 1 and Q = { p 1 , p 2 , p 3 } Q = \{p_1,p_2,p_3\} Q = { p 1 , p 2 , p 3 } ), p 1 p_1 p 1 ’s operation has returned by the final step; let r 1 r_1 r 1 be the value returned.
Next, construct σ 01 \sigma_{01} σ 01 as shown in Figure 2 b: Process p 0 p_0 p 0 completes a round trip with p 0 p_0 p 0 , p 2 p_2 p 2 , p 3 p_3 p 3 , followed by p 1 p_1 p 1 with p 1 p_1 p 1 , p 2 p_2 p 2 , p 3 p_3 p 3 . Processes p 0 p_0 p 0 , p 1 p_1 p 1 , p 3 p_3 p 3 follow A \mathcal{A} A , whereas p 2 p_2 p 2 deviates from A \mathcal{A} A by sending its reply from α 0 \alpha_0 α 0 to p 0 p_0 p 0 and its reply from α 1 \alpha_1 α 1 to p 1 p_1 p 1 .8 Process p 3 p_3 p 3 receives p 0 p_0 p 0 ’s invocation message and then p 1 p_1 p 1 ’s, so its state at each reply is the one it has in α 0 \alpha_0 α 0 and in α 1 \alpha_1 α 1 ; it therefore sends those replies to p 0 p_0 p 0 and p 1 p_1 p 1 , respectively. All remaining messages are delayed until after σ 01 \sigma_{01} σ 01 . These steps form a schedule prefix of A \mathcal{A} A , which extends to a schedule in which p 2 p_2 p 2 is the only Byzantine process. Prefix σ 01 \sigma_{01} σ 01 is indistinguishable from α 0 \alpha_0 α 0 to p 0 p_0 p 0 and from α 1 \alpha_1 α 1 to p 1 p_1 p 1 , so their operations return r 0 r_0 r 0 and r 1 r_1 r 1 , respectively. The former returns before the latter is invoked, so applying condition (BT1a) to the extended schedule yields r 0 < r 1 r_0 < r_1 r 0 < r 1 .
Symmetrically, construct σ 10 \sigma_{10} σ 10 as shown in Figure 2 b, with p 1 p_1 p 1 ’s operation first and p 0 p_0 p 0 ’s second. Here, processes p 0 p_0 p 0 , p 1 p_1 p 1 , p 2 p_2 p 2 follow A \mathcal{A} A , whereas p 3 p_3 p 3 deviates from A \mathcal{A} A by sending its reply from α 1 \alpha_1 α 1 to p 1 p_1 p 1 and its reply from α 0 \alpha_0 α 0 to p 0 p_0 p 0 . As above, σ 10 \sigma_{10} σ 10 extends to a schedule of A \mathcal{A} A in which p 3 p_3 p 3 is the only Byzantine process. It is indistinguishable from α 1 \alpha_1 α 1 to p 1 p_1 p 1 and from α 0 \alpha_0 α 0 to p 0 p_0 p 0 , so the operations return r 1 r_1 r 1 and r 0 r_0 r 0 , respectively. Applying condition (BT1a) to the extended schedule yields r 1 < r 0 r_1 < r_0 r 1 < r 0 , contradicting r 0 < r 1 r_0 < r_1 r 0 < r 1 . □Theorem 7.15
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 > 3 f n > 3f n > 3 f .
We now turn to the optimal latency. When n > 3 f n > 3f n > 3 f and f ≥ 2 f \ge2 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 > 3 f n > 3f n > 3 f and f ≥ 2 f \ge2 f ≥ 2 , then the optimal latency of implementing TS is three message delays.
When n = 4 n = 4 n = 4 and f = 1 f = 1 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 n = 4 n = 4 and f = 1 f = 1 f = 1 , then the optimal latency of implementing TS is three message delays.
One case remains open: n > 4 n > 4 n > 4 and f = 1 f = 1 f = 1 . Here the upper bound is three delays (Theorem 7.2 ), whereas the lower bound is two delays (Observation 7.13 ).
Question 7.19. In a system with Byzantine processes, if n > 4 n > 4 n > 4 and f = 1 f = 1 f = 1 , what is the optimal latency of implementing TS?
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 [15 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 [14 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 [16 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 > 2 f n > 2f n > 2 f . 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 f = 1 f = 1 (Algorithm 1) and three when f ≥ 2 f \ge2 f ≥ 2 (Algorithm 2).
As mentioned in § 4.2.2 , Algorithm 2 adopts the max-min technique [8 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 n - f 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 > 3 f n > 3f n > 3 f . 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 f f (permanent) crashes.
Timestamp abstractions in shared memory. Aspnes et al. [1 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 [10 Section 4] , designed for anonymous systems, and fetch-and-increment with multiplicity of Castañeda, Rajsbaum, and Raynal [7 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 these shared-memory constructions can be run in message-passing systems via register emulation [2 , 16 ] , but the resulting implementations do not achieve the optimal latency of implementing TS. Ellen, Fatourou, and Ruppert [9 ] and Helmi et al. [11 ] study how many read/write registers are needed to implement variants of TS, whereas we study latency in message-passing systems.
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 n > 4 n > 4 and f = 1 f = 1 f = 1 : Do two message delays suffice, or are three necessary? When n = 4 n = 4 n = 4 and f = 1 f = 1 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 n > 4 n > 4 .
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 > 3 f n > 3f n > 3 f , and one without signatures for n > 4 f n > 4f n > 4 f . GPT proposed an implementation without signatures for n = 4 n = 4 n = 4 and f = 1 f = 1 f = 1 , and then generalized it to all n > 3 f n > 3f n > 3 f . 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.
Auxiliary Notations
We use the following notation for finite sequences of steps:
∣ σ ∣ |\sigma| ∣ σ ∣ is the number of steps in a schedule prefix σ \sigma σ ; and
⟨ s 1 , … , s k ⟩ \langle s_1,\ldots,s_k\rangle ⟨ s 1 , … , s k ⟩ is the finite sequence consisting of the steps s 1 , … , s k s_1,\ldots,s_k s 1 , … , s k , 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 ] I=\left[(a,b\right] I = [ ( a , b ] and J = [ ( c , d ] J=\left[(c,d\right] J = [ ( c , d ] be bounded real intervals with the same endpoint types, where a < b a < b a < b and c < d c < d c < d . We write
Affine I → J : I → J \operatorname{Affine}_{I\to J}: I \to J Affine I → J : I → J for the map defined by
Affine I → J ( x ) ≜ c + d − c b − a ( x − a ) . \operatorname{Affine}_{I\to J}(x) \mathrel{\triangleq} c + \frac{d-c}{b-a}(x-a). Affine I → J ( x ) ≜ c + b − a d − c ( x − a ) . We use the same notation for half-infinite intervals bounded on the same side and having the same finite-endpoint type:
Affine [ ( a , + ∞ ) → [ ( c , + ∞ ) ( x ) ≜ x + ( c − a ) , \operatorname{Affine}_{[(a,+\infty)}\to[(c,+\infty)(x) \mathrel{\triangleq} x+(c-a), Affine [( a , + ∞ ) → [( c , + ∞ ) ( x ) ≜ x + ( c − a ) , Affine ( − ∞ , b ] → ( − ∞ , d ] ( x ) ≜ x + ( d − b ) . \operatorname{Affine}_{(-\infty,b]\to(-\infty,d]}(x) \mathrel{\triangleq} x+(d-b). Affine ( − ∞ , b ] → ( − ∞ , d ] ( x ) ≜ x + ( d − b ) .
Proposition A.2. Affine I → J \operatorname{Affine}_{I\to J} Affine I → J is a strictly increasing bijection from I I I to J J J .
Properties of Finite Worst-Case Message Delay
In this section, we prove the two consequences of finite worst-case message delay stated in § 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.
Finite Worst-Case Message Delay Implies Liveness
We first prove Proposition 2.7, restated below.
Proposition 2.7. If δ ( A ) < ∞ \delta(\mathcal{A})<\infty δ ( A ) < ∞ , then A \mathcal{A} A satisfies liveness: In every schedule of A \mathcal{A} A , every operation invoked by a correct process eventually returns.
Proof. Let A \mathcal{A} A be an algorithm with finite worst-case message delay α \alpha α . Let S S S be an (infinite) schedule of A \mathcal{A} A , and let O O O be an operation in S S S invoked by a correct process in step S [ a ] S[a] S [ a ] . We show that O O O returns in S S S .
We assign times to the steps of S S S , obtaining a run in which every received message has latency at most one. For each i ≥ 0 i\ge0 i ≥ 0 , let e i e_i e i be the largest index j j j such that step S [ j ] S[j] S [ j ] receives a message sent in step S [ i ] S[i] S [ i ] ; if no such message is received, set e i = i e_i=i e i = i .
Partition the step indices into consecutive finite blocks B k = [ b k , b k + 1 ) B_k=[b_k,b_{k+1}) B k = [ b k , b k + 1 ) , for k ≥ 0 k\ge0 k ≥ 0 , as follows. Set b 0 = 0 b_0=0 b 0 = 0 , and choose each b k + 1 > b k b_{k+1}>b_k b k + 1 > b k large enough that e i < b k + 1 e_i<b_{k+1} e i < b k + 1 for every i < b k i<b_k i < b k . By construction, if a message sent in block B k B_k B k is later received, then its receive step lies in either block B k B_k B k or B k + 1 B_{k+1} B k + 1 .
Assign times T T T to the steps in S S S so that the steps in each block B k B_k B k get strictly increasing times in the interval [ k / 2 , ( k + 1 ) / 2 ) [k/2,(k+1)/2) [ k /2 , ( k + 1 ) /2 ) . These intervals are disjoint, ordered by k k k , and unbounded, so T T T is strictly increasing and unbounded, and therefore R = ( S , T ) R=(S,T) R = ( S , T ) is a run of A \mathcal{A} A .
Now consider any message sent in block B k B_k B k and later received. By the preceding paragraph, its receive step lies in B k B_k B k or B k + 1 B_{k+1} B k + 1 . Its send time is at least k / 2 k/2 k /2 , and its receive time is less than k / 2 + 1 k/2+1 k /2 + 1 , so its latency is less than 1. Hence every message that is received has latency at most one in R R R .
Every message sent to a process that takes infinitely many steps is received, and so messages are timely during O O O in R R R . Since A \mathcal{A} A has worst-case message delay α \alpha α , we have δ ( O ) ≤ α < ∞ \delta(O)\le\alpha<\infty δ ( O ) ≤ α < ∞ . Hence O O O is complete in R R R , and thus returns in schedule S S S .
:::
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 \mathcal{A} A be an algorithm. If δ ( A ) ≤ α \delta(\mathcal{A})\le\alpha δ ( A ) ≤ α for some nonnegative real number α \alpha α , then δ ( A ) ≤ ⌊ α ⌋ \delta(\mathcal{A})\le\lfloor\alpha\rfloor δ ( A ) ≤ ⌊ α ⌋ .
Proof. Let k ≜ ⌊ α ⌋ k \mathrel{\triangleq} \lfloor\alpha\rfloor k ≜ ⌊ α ⌋ . If α = k \alpha= k α = k , the claim is immediate, so assume k < α < k + 1 k < \alpha< k + 1 k < α < k + 1 .
Suppose, for the sake of contradiction, that δ ( A ) > k \delta(\mathcal{A}) > k δ ( A ) > k . Then there exist a run R = ( S , T ) R = (S,T) R = ( S , T ) of A \mathcal{A} A , and an operation O O O invoked by a correct process, such that messages are timely during O O O in R R R and δ R ( O ) > k \delta_R(O) > k δ R ( O ) > k . By the definition of worst-case message delay, δ R ( O ) ≤ δ ( A ) ≤ α < ∞ \delta_R(O) \le\delta(\mathcal{A}) \le\alpha< \infty δ R ( O ) ≤ δ ( A ) ≤ α < ∞ ; hence O O O is complete. Let O O O be invoked in step S [ a ] S[a] S [ a ] and return in step S [ b ] S[b] S [ b ] , so δ R ( O ) = T [ b ] − T [ a ] \delta_R(O) = T[b] - T[a] δ R ( O ) = T [ b ] − T [ a ] . Putting the inequalities together, we have
k < δ R ( O ) ≤ α < k + 1. (11) k < \delta_R(O) \le\alpha< k + 1. \tag*{(11)} k < δ R ( O ) ≤ α < k + 1. (11)
By subtracting T [ a ] T[a] T [ a ] from every entry of T T T , we may assume without loss of generality that T [ a ] = 0 T[a] = 0 T [ a ] = 0 . Then T [ b ] = δ R ( O ) T[b] = \delta_R(O) T [ b ] = δ R ( O ) .
We will now retime R R R to obtain another run R ′ R' R ′ with schedule S S S such that δ R ′ ( O ) > α \delta_{R'}(O) > \alpha δ R ′ ( O ) > α ; see Figure 3 . Set
Figure 3. Proof of Lemma B.1: retiming the run R = ( S , T ) R=(S,T) R = ( S , T ) (top) into the run R ′ = ( S , T ′ ) R'=(S,T') R ′ = ( S , T ′ ) (bottom) when k < α < k + 1 k<\alpha<k+1 k < α < k + 1 . For each integer i ≥ 1 i\ge1 i ≥ 1 , the unit interval ( i − 1 , i ] (i-1,i] ( i − 1 , i ] in T T T is compressed into ( i − η , i ] (i-\eta,i] ( i − η , i ] in T ′ T' T ′ , where η = ( k + 1 − α ) / 2 ∈ ( 0 , 1 / 2 ) \eta=(k+1-\alpha)/2\in(0,1/2) η = ( k + 1 − α ) /2 ∈ ( 0 , 1/2 ) . In T ′ T' T ′ , “○” marks open interval endpoints, “•” marks closed interval endpoints, and dashed segments mark times at which no step is taken. Every message m m m sent during O O O in R R R with δ R ( m ) ≤ 1 \delta_R(m)\le1 δ R ( m ) ≤ 1 still satisfies δ R ′ ( m ) ≤ 1 \delta_{R'}(m)\le1 δ R ′ ( m ) ≤ 1 (as illustrated by cases ①, ②, and ③). The operation satisfies δ R ( O ) ≤ α \delta_R(O)\le\alpha δ R ( O ) ≤ α , but this choice of η \eta η ensures that δ R ′ ( O ) = ϕ ( δ R ( O ) ) > α \delta_{R'}(O)=\phi(\delta_R(O))>\alpha δ R ′ ( O ) = ϕ ( δ R ( O )) > α .
η ≜ k + 1 − α 2 . \eta\mathrel{\triangleq} \frac{k + 1 - \alpha}{2}. η ≜ 2 k + 1 − α .
Since k < α < k + 1 k < \alpha< k + 1 k < α < k + 1 , we have 0 < η < 1 / 2 0 < \eta< 1/2 0 < η < 1/2 . We construct a time mapping ϕ : R → R \phi: \mathbb{R} \to\mathbb{R} ϕ : R → R that leaves times at or before 0 0 0 unchanged and, for each integer i ≥ 1 i \ge1 i ≥ 1 , compresses the unit interval ( i − 1 , i ] (i - 1, i] ( i − 1 , i ] affinely onto the shorter interval ( i − η , i ] (i - \eta, i] ( i − η , i ] :
ϕ ( t ) ≜ { t , t ≤ 0 , Affine ( i − 1 , i ] → ( i − η , i ] ( t ) , i − 1 < t ≤ i for some i ≥ 1. \phi(t) \mathrel{\triangleq}
\begin{cases}
t, & t \le0,\\
\operatorname{Affine}_{(i-1,i]\to(i-\eta,i]}(t), & i - 1 < t \le i \text{ for some } i \ge1.
\end{cases} ϕ ( t ) ≜ { t , Affine ( i − 1 , i ] → ( i − η , i ] ( t ) , t ≤ 0 , i − 1 < t ≤ i for some i ≥ 1.
Then ϕ \phi ϕ is strictly increasing and unbounded.
Define the infinite sequence T ′ T' T ′ by T ′ [ i ] ≜ ϕ ( T [ i ] ) T'[i] \mathrel{\triangleq} \phi(T[i]) T ′ [ i ] ≜ ϕ ( T [ i ]) , and let R ′ ≜ ( S , T ′ ) R' \mathrel{\triangleq} (S,T') R ′ ≜ ( S , T ′ ) . Since ϕ \phi ϕ is strictly increasing and unbounded, R ′ R' R ′ is a run of A \mathcal{A} A ; moreover, it has the same correct processes as R R R . By construction,
I R ′ ( O ) = [ T ′ [ a ] , T ′ [ b ] ] = [ ϕ ( T [ a ] ) , ϕ ( T [ b ] ) ] = [ 0 , ϕ ( δ R ( O ) ) ] . I_{R'}(O) = [T'[a],T'[b]] = [\phi(T[a]),\phi(T[b])] = [0,\phi(\delta_R(O))]. I R ′ ( O ) = [ T ′ [ a ] , T ′ [ b ]] = [ ϕ ( T [ a ]) , ϕ ( T [ b ])] = [ 0 , ϕ ( δ R ( O ))] .
Claim B.2. Messages are timely during O O O in R ′ R' R ′ .
Proof. Fix an arbitrary message m m m sent during O O O in R ′ R' R ′ to a process that takes infinitely many steps. Let s < t s < t s < t denote, respectively, the send and receive times of m m m in R R R . Since T ′ = ϕ ∘ T T' = \phi\circ T T ′ = ϕ ∘ T , its send and receive times in R ′ R' R ′ are ϕ ( s ) \phi(s) ϕ ( s ) and ϕ ( t ) \phi(t) ϕ ( t ) , respectively.
Thus, ϕ ( 0 ) ≤ ϕ ( s ) ≤ ϕ ( δ R ( O ) ) \phi(0) \le\phi(s) \le\phi(\delta_R(O)) ϕ ( 0 ) ≤ ϕ ( s ) ≤ ϕ ( δ R ( O )) . Because ϕ \phi ϕ is strictly increasing, this implies 0 ≤ s ≤ δ R ( O ) 0 \le s \le\delta_R(O) 0 ≤ s ≤ δ R ( O ) , so m m m is sent during O O O in R R R . Since messages are timely during O O O in R R R , δ R ( m ) = t − s ≤ 1 \delta_R(m) = t - s \le1 δ R ( m ) = t − s ≤ 1 .
It remains to show that δ R ′ ( m ) = ϕ ( t ) − ϕ ( s ) ≤ 1 \delta_{R'}(m) = \phi(t) - \phi(s) \le1 δ R ′ ( m ) = ϕ ( t ) − ϕ ( s ) ≤ 1 . Given that 0 < t − s ≤ 1 0 < t - s \le1 0 < t − s ≤ 1 , there are three cases for the positions of s s s and t t t , exemplified by messages labeled ①, ②, and ③ in Figure 3 :
If s = 0 s = 0 s = 0 , then 0 < t ≤ 1 0 < t \le1 0 < t ≤ 1 , and we get ϕ ( t ) − ϕ ( s ) = ϕ ( t ) ≤ ϕ ( 1 ) = 1 \phi(t) - \phi(s) = \phi(t) \le\phi(1) = 1 ϕ ( t ) − ϕ ( s ) = ϕ ( t ) ≤ ϕ ( 1 ) = 1 .
If s , t ∈ ( i − 1 , i ] s,t \in(i - 1,i] s , t ∈ ( i − 1 , i ] for some i ≥ 1 i \ge1 i ≥ 1 , then since ϕ \phi ϕ is affine on ( i − 1 , i ] (i - 1,i] ( i − 1 , i ] with slope η \eta η ,
ϕ ( t ) − ϕ ( s ) = η ( t − s ) ≤ η < 1. \phi(t) - \phi(s) = \eta(t - s) \le\eta< 1. ϕ ( t ) − ϕ ( s ) = η ( t − s ) ≤ η < 1.
Otherwise, s ∈ ( i − 1 , i ] s \in(i - 1,i] s ∈ ( i − 1 , i ] and t ∈ ( i , i + 1 ] t \in(i,i + 1] t ∈ ( i , i + 1 ] for some i ≥ 1 i \ge1 i ≥ 1 . Then
ϕ ( t ) − ϕ ( s ) = [ ( i + 1 − η ) + η ( t − i ) ] − [ ( i − η ) + η ( s − ( i − 1 ) ) ] = 1 + η ( t − s − 1 ) ≤ 1. \phi(t) - \phi(s) = \left[(i + 1 - \eta) + \eta(t - i)\right] - \left[(i - \eta) + \eta(s - (i - 1))\right] = 1 + \eta(t - s - 1) \le1. ϕ ( t ) − ϕ ( s ) = [ ( i + 1 − η ) + η ( t − i ) ] − [ ( i − η ) + η ( s − ( i − 1 )) ] = 1 + η ( t − s − 1 ) ≤ 1.
Thus, δ R ′ ( m ) ≤ 1 \delta_{R'}(m) \le1 δ R ′ ( m ) ≤ 1 in every case. Since m m m was arbitrary, messages are timely during O O O in R ′ R' R ′ . □
Claim B.3. δ R ′ ( O ) > α \delta_{R'}(O) > \alpha δ R ′ ( O ) > α .
Proof. By (11) , δ R ( O ) ∈ ( k , k + 1 ] \delta_R(O) \in(k,k+1] δ R ( O ) ∈ ( k , k + 1 ] . Since ϕ \phi ϕ maps ( k , k + 1 ] (k,k+1] ( k , k + 1 ] onto ( k + 1 − η , k + 1 ] (k+1-\eta,k+1] ( k + 1 − η , k + 1 ] , it follows that
ϕ ( δ R ( O ) ) > k + 1 − η . \phi(\delta_R(O)) > k + 1 - \eta. ϕ ( δ R ( O )) > k + 1 − η .
Therefore,
δ R ′ ( O ) = ϕ ( δ R ( O ) ) − ϕ ( 0 ) > k + 1 − η = k + 1 + α 2 > α . \delta_{R'}(O) = \phi(\delta_R(O)) - \phi(0) > k + 1 - \eta= \frac{k + 1 + \alpha}{2} > \alpha. δ R ′ ( O ) = ϕ ( δ R ( O )) − ϕ ( 0 ) > k + 1 − η = 2 k + 1 + α > α .
By the first claim and the definition of worst-case message delay, δ R ′ ( O ) ≤ δ ( A ) ≤ α \delta_{R'}(O) \le\delta(A) \le\alpha δ R ′ ( O ) ≤ δ ( A ) ≤ α , contradicting the second claim. Hence, δ ( A ) ≤ k = ⌊ α ⌋ \delta(A) \le k = \lfloor\alpha\rfloor δ ( A ) ≤ k = ⌊ α ⌋ .
Proposition 2.8, which we restate below, immediately follows from this lemma.
Proposition 2.8. If δ ( A ) < ∞ \delta(A) < \infty δ ( A ) < ∞ , then δ ( A ) = k \delta(A) = k δ ( A ) = k for some nonnegative integer k k k .
Proof. Let the algorithm’s worst-case message delay be α < ∞ \alpha< \infty α < ∞ . Since operation latencies are nonnegative, we have α ≥ 0 \alpha\ge0 α ≥ 0 . By Lemma B.1 , the algorithm’s worst-case message delay is at most ⌊ α ⌋ \lfloor\alpha\rfloor ⌊ α ⌋ , so α ≤ ⌊ α ⌋ \alpha\le\lfloor\alpha\rfloor α ≤ ⌊ α ⌋ . Since always ⌊ α ⌋ ≤ α \lfloor\alpha\rfloor\le\alpha ⌊ α ⌋ ≤ α , it follows that α = ⌊ α ⌋ \alpha= \lfloor\alpha\rfloor α = ⌊ α ⌋ . Thus α \alpha α is a nonnegative integer.
Auxiliary Results for Latency Lower Bounds
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.
Crash Failures
We first prove Lemma 4.20 from § 4 , restated below for convenience.
Lemma 4.20. In a system with crash failures, let A A A be an implementation of T S TS T S . Then there exists a loquacious implementation A ′ A' A ′ of T S TS T S such that δ ( A ′ ) ≤ δ ( A ) \delta(A') \le\delta(A) δ ( A ′ ) ≤ δ ( A ) .
Proof. We construct an algorithm A ′ A' A ′ in which each process simulates its counterpart in A A A but broadcasts one packed message in every step. A packed message encodes a finite, possibly empty set of pairs ( m , q ) (m,q) ( m , q ) , where m m m is an original message of A A A and q q q is its destination.
For each process p p p , we define the automaton A p ′ A'_p A p ′ that A ′ A' A ′ assigns to p p p in terms of the automaton A p A_p A p that A A A assigns to p p p . The local states and initial state of A p ′ A'_p A p ′ are those of A p A_p A p . From every state s s s , set M ′ M' M ′ of received messages, and operation invocation (if any), A p ′ A'_p A p ′ has a unique transition, which:
extracts from the packed messages in M ′ M' M ′ the set M M M of original messages paired with destination p p p ;
follows the unique transition t t t of A p A_p A p from state s s s on M M M and the same operation invocation, if any, moving to the state that t t t moves to;
broadcasts the packed message containing the pair ( m , q ) (m,q) ( m , q ) for every original message m m m that t t t sends to a process q q q ; and
returns the same value as t t t , if t t t returns from an operation.
By construction, A ′ A' A ′ is loquacious.
Given a schedule S ′ S' S ′ of A ′ A' A ′ , define an infinite sequence S S S step by step. For each i i i , let p p p be the process that takes step S ′ [ i ] S'[i] S ′ [ i ] . Step S [ i ] S[i] S [ i ] is taken by p p p and is defined as follows:
S [ i ] S[i] S [ i ] invokes an operation iff S ′ [ i ] S'[i] S ′ [ i ] does;
for every process q q q , step S [ i ] S[i] S [ i ] receives from q q q precisely those original messages m m m for which ( m , p ) (m,p) ( m , p ) appears in a packed message received from q q q in S ′ [ i ] S'[i] S ′ [ i ] ;
for every process q q q , step S [ i ] S[i] S [ i ] sends to q q q precisely those original messages m m m for which ( m , q ) (m,q) ( m , q ) appears in the packed message broadcast in S ′ [ i ] S'[i] S ′ [ i ] ; and
S [ i ] S[i] S [ i ] returns from an operation with value v v v iff S ′ [ i ] S'[i] S ′ [ i ] does with the same value.
We now isolate the properties of S S S that we will later need.
Claim C.1. Let S S S be defined as above from S ′ S' S ′ . Then:
(a) For every i i i , steps S [ i ] S[i] S [ i ] and S ′ [ i ] S'[i] 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 S S as in S ′ S' S ′ .
(c) Every process correct in S ′ S' S ′ is correct in S S S .9
(d) If a message sent in S [ i ] S[i] S [ i ] is received in S [ j ] S[j] S [ j ] , then some message sent in S ′ [ i ] S'[i] S ′ [ i ] is received in S ′ [ j ] S'[j] S ′ [ j ] .
(e) S S S is a schedule of A \mathcal{A} A .
Proof. An induction on i i i shows that every step S [ i ] S[i] S [ i ] follows A \mathcal{A} A : It performs precisely the transition of A \mathcal{A} A that S ′ [ i ] S'[i] S ′ [ i ] simulates, from the same local state. Moreover, corresponding steps of S S S and S ′ S' S ′ are taken by the same process and have the same invocation and return. Thus (a) and (b) hold. Since every step of S S S follows A \mathcal{A} A , (b) implies (c).
For every original message m m m sent to q q q in S [ i ] S[i] S [ i ] , let m ′ m' m ′ be the copy of the packed message broadcast in S ′ [ i ] S'[i] S ′ [ i ] that is sent to q q q . By construction, m ′ m' m ′ contains the pair ( m , q ) (m,q) ( m , q ) , and m m m is received in S [ j ] S[j] S [ j ] iff m ′ m' m ′ is received in S ′ [ j ] S'[j] S ′ [ j ] , proving (d). Together with (b) and the fact that S ′ S' S ′ is a schedule, this correspondence implies that in S S 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 n-f n − f processes take infinitely many steps in S S S , since they do in S ′ S' S ′ . By (a), each process’s operations remain sequential. Thus S S S is a schedule of A \mathcal{A} A , proving (e).
Claim C.2. A ′ \mathcal{A}' A ′ is an implementation of TS.
Proof. Let S ′ S' S ′ be any schedule of A ′ \mathcal{A}' A ′ and let S S S be as defined above. By Claim C.1 (e), S S S is a schedule of A \mathcal{A} A . By Claim C.1 (a), S S S and S ′ S' S ′ have the same history. Since A \mathcal{A} A satisfies the safety condition (CT1), this history is linearizable with respect to TS, so A ′ \mathcal{A}' A ′ satisfies (CT1) as well.
To show that A ′ \mathcal{A}' A ′ satisfies the liveness condition (CT2), let O ′ O' O ′ be any operation in S ′ S' S ′ invoked by a correct process p p p . By Claim C.1 (a), S S S has a corresponding operation O O O invoked by the same process p p p . By Claim C.1 (c), p p p is correct in S S S as well. Since S S S is a schedule of A \mathcal{A} A , which implements TS, O O O eventually returns. By Claim C.1 (a), the corresponding return occurs in S ′ S' S ′ , so O ′ O' O ′ eventually returns as well.
Claim C.3. δ ( A ′ ) ≤ δ ( A ) \delta(\mathcal{A}') \leq\delta(\mathcal{A}) δ ( A ′ ) ≤ δ ( A ) .
Proof. Let R ′ = ( S ′ , T ′ ) R'=(S',T') R ′ = ( S ′ , T ′ ) be any run of A ′ \mathcal{A}' A ′ , and let R = ( S , T ′ ) R=(S,T') R = ( S , T ′ ) , where S S S is as defined above. We first verify that R R R is a run of A \mathcal{A} A :
By Claim C.1 (e), S S S is a schedule of A \mathcal{A} A .
Since R ′ R' R ′ is a run, T ′ T' T ′ is non-decreasing and unbounded.
If a message is sent in S [ i ] S[i] S [ i ] and received in S [ j ] S[j] S [ j ] , then Claim C.1 (d) gives a message sent in S ′ [ i ] S'[i] S ′ [ i ] and received in S ′ [ j ] S'[j] S ′ [ j ] ; hence T ′ [ i ] < T ′ [ j ] T'[i] < T'[j] T ′ [ i ] < T ′ [ j ] .
Likewise, if S [ i ] S[i] S [ i ] and S [ j ] S[j] S [ j ] , with i < j i<j i < j , are taken by the same process, then Claim C.1 (a) implies that S ′ [ i ] S'[i] S ′ [ i ] and S ′ [ j ] S'[j] S ′ [ j ] are taken by the same process; hence again T ′ [ i ] < T ′ [ j ] T'[i] < T'[j] T ′ [ i ] < T ′ [ j ] .
Thus all conditions of the definition of a run are satisfied.
Let O ′ O' O ′ be any operation in R ′ R' R ′ invoked by a correct process p p p such that messages are timely during O ′ O' O ′ . By Claim C.1 (a), S S S has a corresponding operation O O O invoked by p p p , with the same invocation- and return-step indices. Since R R R and R ′ R' R ′ share the time sequence T ′ T' T ′ ,
I ( O ) = I ( O ′ ) and hence δ ( O ) = δ ( O ′ ) . \mathcal{I}(O) = \mathcal{I}(O') \quad\text{and hence} \quad\delta(O) = \delta(O'). I ( O ) = I ( O ′ ) and hence δ ( O ) = δ ( O ′ ) .
By Claim C.1 (c), p p p is correct in R R R as well.
We now show that messages are timely during O O O in R R R . Let m m m be any message sent during O O O to a process q q q that takes infinitely many steps in S S S , so m m m is eventually received. Suppose it is sent in step S [ i ] S[i] S [ i ] and received in step S [ j ] S[j] S [ j ] . By Claim C.1 (d), some message m ′ m' m ′ is sent in S ′ [ i ] S'[i] S ′ [ i ] and received in S ′ [ j ] S'[j] S ′ [ j ] , and so
δ ( m ′ ) = T ′ [ j ] − T ′ [ i ] = δ ( m ) . \delta(m') = T'[j] - T'[i] = \delta(m). δ ( m ′ ) = T ′ [ j ] − T ′ [ i ] = δ ( m ) .
By Claim C.1 (a), step S ′ [ j ] S'[j] S ′ [ j ] is taken by q q q , so m ′ m' m ′ is sent to q q q . By Claim C.1 (b), q q q takes infinitely many steps in S ′ S' S ′ . Moreover, because m m m and m ′ m' m ′ are sent at the same time and I ( O ) = I ( O ′ ) I(O) = I(O') I ( O ) = I ( O ′ ) , message m ′ m' m ′ is sent during O ′ O' O ′ . Because messages are timely during O ′ O' O ′ in R ′ R' R ′ , we have
δ ( m ) = δ ( m ′ ) ≤ 1. \delta(m) = \delta(m') \le1. δ ( m ) = δ ( m ′ ) ≤ 1.
Thus every message sent during O O O to a process that takes infinitely many steps has latency at most one, so messages are timely during O O O in R R R .
Since O O O is invoked by a correct process, the definition of δ ( A ) \delta(\mathcal{A}) δ ( A ) yields
δ ( O ′ ) = δ ( O ) ≤ δ ( A ) . \delta(O') = \delta(O) \le\delta(\mathcal{A}). δ ( O ′ ) = δ ( O ) ≤ δ ( A ) .
Taking the supremum over all such R ′ R' R ′ and O ′ O' O ′ yields δ ( A ′ ) ≤ δ ( A ) \delta(\mathcal{A}') \le\delta(\mathcal{A}) δ ( A ′ ) ≤ δ ( A ) . Claim C.3
The construction and the latter two claims establish the result. Lemma 4.20
Byzantine Failures
We next restate Lemma 7.11 from § 11.3.1 and sketch its proof.
Lemma 7.11 (Byzantine version of Lemma 4.20). In a system with Byzantine processes, let A \mathcal{A} A be an implementation of T S TS T S . Then there exists a loquacious implementation A ′ \mathcal{A}' A ′ of T S TS T S such that δ ( A ′ ) ≤ δ ( A ) \delta(\mathcal{A}') \le\delta(\mathcal{A}) δ ( A ′ ) ≤ δ ( A ) .
Proof sketch. We reuse the construction of A ′ \mathcal{A}' A ′ and the transformation of S ′ S' S ′ into S S S from the proof of the crash-failure counterpart, Lemma 4.20, modifying only how the messages sent in S [ i ] S[i] S [ i ] are defined:
For every process q q q , step S [ i ] S[i] S [ i ] sends to q q q precisely those original messages m m m for which ( m , q ) (m,q) ( m , q ) appears in a packed message sent to q q q in S ′ [ i ] S'[i] S ′ [ i ] .
This modification is necessary because the crash-failure transformation refers to the packed message broadcast in S ′ [ i ] S'[i] S ′ [ i ] , whereas a Byzantine process may send different messages to different recipients or send no message at all.
Because the construction of A ′ \mathcal{A}' 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 ′ S' S ′ are simply ignored, as desired. This is because both the construction of A ′ \mathcal{A}' A ′ and the transformation of S ′ S' S ′ into S S S consider only (valid) packed messages.
A process that is faulty in S ′ S' S ′ and takes infinitely many steps may nevertheless be correct in S S S , if all of its transformed steps happen to conform to A \mathcal{A} A . This is harmless: Claim C.1 requires only that every process correct in S ′ S' S ′ also be correct in S S S . The subsequent arguments use this implication only in that direction.
Let S ′ S' S ′ be any schedule of A ′ \mathcal{A}' A ′ , and let S S S be the sequence obtained by the modified transformation. Since A \mathcal{A} A satisfies the safety condition (BT1), there is a history H ˉ \bar{H} H ˉ that is linearizable with respect to T S TS T S and agrees with the history of S S S on the processes correct in S S S . By Claim C.1 , S S S and S ′ S' S ′ have the same history, and every process correct in S ′ S' S ′ is correct in S S S . Hence H ˉ \bar{H} H ˉ agrees with the history of S ′ S' S ′ on the processes correct in S ′ S' S ′ , so A ′ \mathcal{A}' A ′ satisfies the safety condition (BT1). The liveness and latency arguments carry over unchanged, using (BT2) for the liveness condition.
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 ) R=(S,T) R = ( S , T ) and an interval I ⊆ R I \subseteq R I ⊆ R , we say that messages are timely during I I I in R R R if δ ( m ) ≤ 1 \delta(m) \le1 δ ( m ) ≤ 1 for every message m m m sent at a time in I I I to a process that takes infinitely many steps in S S S . Timeliness during an operation O O O (Definition 2.5 ) is the special case I = I R ( O ) I=I_R(O) I = I R ( 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 ) R=(S,T) R = ( S , T ) be a run, and let O O O be an operation in R R R . We say that messages are ultimately timely during O O O in R R R if either of the following applies:
O O O is incomplete, and messages are timely during O O O in R R R ; or
O O O is complete, having been invoked in step S [ a ] S[a] S [ a ] and returned in step S [ b ] S[b] S [ b ] , and messages are timely during [ T [ a ] , T [ b ] − 1 ] [T[a],T[b]-1] [ T [ a ] , T [ b ] − 1 ] in R R R .
Note that if δ ( O ) < 1 \delta(O)<1 δ ( O ) < 1 , then messages are vacuously ultimately timely during O O O .
Lemma C.5. Let A A A be an algorithm, let R R R be a run of A A A , and let O O O be an operation in R R R invoked by a correct process. If messages are ultimately timely during O O O in R R R , then δ ( O ) ≤ δ ( A ) \delta(O)\le\delta(A) δ ( O ) ≤ δ ( A ) .
Proof. Write R = ( S , T ) R = (S,T) R = ( S , T ) . If messages are timely during O O O in R R 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 O O must be complete. Let O O O be invoked in step S [ a ] S[a] S [ a ] and return in step S [ b ] S[b] S [ b ] . We will construct a run R ′ = ( S , T ′ ) R' = (S,T') R ′ = ( S , T ′ ) such that δ R ′ ( O ) = δ R ( O ) \delta_{R'}(O) = \delta_R(O) δ R ′ ( O ) = δ R ( O ) and messages are timely during O O O in R ′ R' R ′ ; see Figure 4 .
Figure 4. Proof of Lemma C.5: retiming the run R = ( S , T ) R=(S,T) R = ( S , T ) (top) into the run R ′ = ( S , T ′ ) R'=(S,T') R ′ = ( S , T ′ ) (bottom). Both runs share the same schedule S S S , which contains an invocation at step S [ a ] S[a] S [ a ] and a corresponding response at step S [ b ] S[b] 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 R R , messages are ultimately timely, but not timely, during the operation (denoted O O O ). The shaded band is the ultimate interval ( T [ b ] − 1 , T [ b ] ] (T[b]-1,T[b]] ( T [ b ] − 1 , T [ b ]] . Time τ \tau τ is the earliest sending time of a message in M u l t M_{\mathrm{ult}} M ult ; time μ \mu μ is the latest receiving time of such a message. T ′ T' T ′ is constructed from T T T by compressing the time interval ( T [ b ] , μ ] (T[b],\mu] ( T [ b ] , μ ] into ( T [ b ] , τ + 1 ] (T[b],\tau+1] ( T [ b ] , τ + 1 ] , pulling late message receptions to within 1 time unit of the send times. The operation O O O has the same latency in R ′ R' R ′ as in R R R , but messages are timely during O O O in R ′ R' R ′ .
Let M M M denote the set of messages sent during O O O in R R R to a process that takes infinitely many steps. Since S S S is a schedule, every message in M M M is eventually received. Let M u l t ⊆ M M_{\mathrm{ult}} \subseteq M M ult ⊆ M consist of the messages sent during the ultimate interval ( T [ b ] − 1 , T [ b ] ] (T[b]-1,T[b]] ( T [ b ] − 1 , T [ b ]] . Since T T T is non-decreasing and unbounded, only finitely many steps occur during this interval, hence M u l t M_{\mathrm{ult}} M ult is finite. Because messages are ultimately timely but not timely during O O O in R R R , some message in M u l t M_{\mathrm{ult}} M ult has latency exceeding 1 1 1 , so M u l t ≠ ∅ M_{\mathrm{ult}} \ne\varnothing M ult = ∅ .
Let τ \tau τ and μ \mu μ be, respectively, the earliest send time and latest receive time of a message in M u l t M_{\mathrm{ult}} M ult . These times are well-defined because M u l t M_{\mathrm{ult}} M ult is finite, nonempty, and consists of messages that are received. By definition, τ > T [ b ] − 1 \tau> T[b]-1 τ > T [ b ] − 1 . Moreover, if some message m ∈ M u l t m \in M_{\mathrm{ult}} m ∈ M ult with δ R ( m ) > 1 \delta_R(m) > 1 δ R ( m ) > 1 is sent at time s s s and received at time r r r , then
μ ≥ r > s + 1 ≥ τ + 1. \mu\ge r > s + 1 \ge\tau+ 1. μ ≥ r > s + 1 ≥ τ + 1.
Thus, T [ b ] < τ + 1 < μ T[b] < \tau+ 1 < \mu T [ b ] < τ + 1 < μ .
We “retime” R R R by compressing the interval ( T [ b ] , μ ] (T[b],\mu] ( T [ b ] , μ ] into ( T [ b ] , τ + 1 ] (T[b],\tau+1] ( T [ b ] , τ + 1 ] and leaving other times unchanged. Define ϕ : R → R \phi:\mathbb{R}\to\mathbb{R} ϕ : R → R by
ϕ ( t ) ≜ { t , t ≤ T [ b ] , Affine ( T [ b ] , μ ] → ( T [ b ] , τ + 1 ] ( t ) , T [ b ] < t ≤ μ , t , t > μ . \phi(t) \triangleq
\begin{cases}
t, & t \le T[b],\\
\operatorname{Affine}_{(T[b],\mu]\to(T[b],\tau+1]}(t), & T[b] < t \le\mu,\\
t, & t > \mu.
\end{cases} ϕ ( t ) ≜ ⎩ ⎨ ⎧ t , Affine ( T [ b ] , μ ] → ( T [ b ] , τ + 1 ] ( t ) , t , t ≤ T [ b ] , T [ b ] < t ≤ μ , t > μ .
Since T [ b ] < τ + 1 < μ T[b] < \tau+ 1 < \mu T [ b ] < τ + 1 < μ , the map ϕ \phi ϕ is strictly increasing and unbounded.
Define T ′ [ i ] ≜ ϕ ( T [ i ] ) T'[i] \triangleq\phi(T[i]) T ′ [ i ] ≜ ϕ ( T [ i ]) . Because T T T is non-decreasing and unbounded, so is T ′ T' T ′ . Moreover, since ϕ \phi ϕ is strictly increasing, T [ i ] < T [ j ] T[i] < T[j] T [ i ] < T [ j ] iff T ′ [ i ] < T ′ [ j ] T'[i] < T'[j] T ′ [ i ] < T ′ [ j ] for all indices i i i and j j j . Thus, R ′ = ( S , T ′ ) R' = (S,T') R ′ = ( S , T ′ ) is a run of A \mathcal{A} A with the same schedule as R R R . Since T [ a ] ≤ T [ b ] T[a] \le T[b] T [ a ] ≤ T [ b ] , we have T ′ [ a ] = ϕ ( T [ a ] ) = T [ a ] T'[a] = \phi(T[a]) = T[a] T ′ [ a ] = ϕ ( T [ a ]) = T [ a ] and T ′ [ b ] = ϕ ( T [ b ] ) = T [ b ] T'[b] = \phi(T[b]) = T[b] T ′ [ b ] = ϕ ( T [ b ]) = T [ b ] , so δ R ′ ( O ) = δ R ( O ) \delta_{R'}(O) = \delta_R(O) δ R ′ ( O ) = δ R ( O ) .
It remains to show that messages are timely during O O O in R ′ R' R ′ . Because ϕ \phi ϕ is strictly increasing and fixes T [ a ] T[a] T [ a ] and T [ b ] T[b] T [ b ] , for any time t t t we have
t ∈ I R ( O ) ⟺ ϕ ( t ) ∈ I R ′ ( O ) . (12) t \in I_R(O) \quad\Longleftrightarrow\quad\phi(t) \in I_{R'}(O). \tag*{(12)} t ∈ I R ( O ) ⟺ ϕ ( t ) ∈ I R ′ ( O ) . (12)
Fix any message m m m sent during O O O in R ′ R' R ′ to a process that takes infinitely many steps. Let S [ i ] S[i] S [ i ] be its send step and set s ≜ T [ i ] s \triangleq T[i] s ≜ T [ i ] . Its send time in R ′ R' R ′ is ϕ ( s ) ∈ I R ′ ( O ) \phi(s) \in I_{R'}(O) ϕ ( s ) ∈ I R ′ ( O ) , so (12) implies s ∈ I R ( O ) s \in I_R(O) s ∈ I R ( O ) , i.e., m m m is also sent during O O O in R R R . Hence m ∈ M m \in M m ∈ M . Let S [ j ] S[j] S [ j ] be its receive step and set r ≜ T [ j ] r \triangleq T[j] r ≜ T [ j ] . Since s ≤ T [ b ] s \le T[b] s ≤ T [ b ] , we have ϕ ( s ) = s \phi(s) = s ϕ ( s ) = s , and therefore
δ R ′ ( m ) = ϕ ( r ) − ϕ ( s ) = ϕ ( r ) − s . \delta_{R'}(m) = \phi(r) - \phi(s) = \phi(r) - s. δ R ′ ( m ) = ϕ ( r ) − ϕ ( s ) = ϕ ( r ) − s .
There are two cases, depending on whether m m m was sent before or during the ultimate interval:
If s ≤ T [ b ] − 1 s \le T[b]-1 s ≤ T [ b ] − 1 , ultimate timeliness during O O O in R R R implies r − s ≤ 1 r-s \le1 r − s ≤ 1 , and hence r ≤ T [ b ] r \le T[b] r ≤ T [ b ] . Thus ϕ ( r ) = r \phi(r)=r ϕ ( r ) = r , so
δ R ′ ( m ) = ϕ ( r ) − s = r − s ≤ 1. \delta_{R'}(m) = \phi(r)-s = r-s \le1. δ R ′ ( m ) = ϕ ( r ) − s = r − s ≤ 1.
If s > T [ b ] − 1 s > T[b]-1 s > T [ b ] − 1 , then m ∈ M u l t m \in M_{\mathrm{ult}} m ∈ M ult , so s ≥ τ s \ge\tau s ≥ τ and r ≤ μ r \le\mu r ≤ μ . Therefore,
δ R ′ ( m ) = ϕ ( r ) − s ≤ ϕ ( μ ) − τ = ( τ + 1 ) − τ = 1. \delta_{R'}(m) = \phi(r)-s \le\phi(\mu)-\tau= (\tau+1)-\tau= 1. δ R ′ ( m ) = ϕ ( r ) − s ≤ ϕ ( μ ) − τ = ( τ + 1 ) − τ = 1.
In both cases, δ R ′ ( m ) ≤ 1 \delta_{R'}(m) \le1 δ R ′ ( m ) ≤ 1 . So every message sent during O O O in R ′ R' R ′ to a process that takes infinitely many steps has latency at most one, meaning messages are timely during O O O in R ′ R' R ′ .
By the definition of worst-case message delay, δ R ′ ( O ) ≤ δ ( A ) \delta_{R'}(O) \le\delta(\mathcal{A}) δ R ′ ( O ) ≤ δ ( A ) . Since δ R ( O ) = δ R ′ ( O ) \delta_R(O) = \delta_{R'}(O) δ R ( O ) = δ R ′ ( O ) , the claim follows.
□Lemma C.5
We can weaken the timeliness requirement once more. Write t t t for the time a complete operation returns. The idea is to additionally exempt messages sent during the time interval ( t − 2 , t − 1 ] (t-2,t-1] ( t − 2 , t − 1 ] to processes other than the invoker p p 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 t-1 t − 1 . Since p p p is not the recipient of any such message, this transformation leaves p p 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 ) R=(S,T) R = ( S , T ) be a run, and let O O O be an operation in R R R . We say that messages are penultimately timely during O O O in R R R if either of the following applies:
O O O is incomplete and messages are timely during O O O in R R R ; or
O O O is complete, having been invoked by a process p p p in step S [ a ] S[a] S [ a ] and returned in step S [ b ] S[b] S [ b ] ; writing
I e a r l y ≜ [ T [ a ] , T [ b ] − 2 ] and I p e n ≜ [ T [ a ] , T [ b ] − 1 ] ∖ I e a r l y , I_{\mathrm{early}} \mathrel{\triangleq} [T[a],T[b]-2] \qquad\text{and} \qquad I_{\mathrm{pen}} \mathrel{\triangleq} [T[a],T[b]-1]\setminus I_{\mathrm{early}}, I early ≜ [ T [ a ] , T [ b ] − 2 ] and I pen ≜ [ T [ a ] , T [ b ] − 1 ] ∖ I early , both of the following conditions apply:
(a) messages are timely during I e a r l y I_{\mathrm{early}} I early in R R R ; and
(b) if p p p takes infinitely many steps in S S S , then every message sent to p p p during I p e n I_{\mathrm{pen}} I pen has latency at most one in R R R .
Note that condition (2)(a) holds vacuously when δ ( O ) < 2 \delta(O)<2 δ ( O ) < 2 , and condition (2)(b) holds vacuously when p p p crashes or when δ ( O ) < 1 \delta(O)<1 δ ( O ) < 1 . In particular, if δ ( O ) < 1 \delta(O)<1 δ ( O ) < 1 , then messages are penultimately timely during O O O .
Lemma C.7. Let A A A be an algorithm, let R R R be a run of A A A , and let O O O be an operation in R R R invoked by a correct process. If messages are penultimately timely during O O O in R R R , then δ ( O ) ≤ δ ( A ) \delta(O)\leq\delta(A) δ ( O ) ≤ δ ( A ) .
Proof. Write R = ( S , T ) R=(S,T) R = ( S , T ) . If messages are timely during O O O in R R 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 O O must be complete. Let O O O be invoked by a correct process p p p in step S [ a ] S[a] S [ a ] and return in step S [ b ] S[b] S [ b ] .
If messages are ultimately timely during O O O in R R R , the claim follows from Lemma C.5, so assume messages are not ultimately timely during O O O in R R R . This means δ ( O ) ≥ 1 \delta(O)\geq1 δ ( O ) ≥ 1 , and hence a < b a<b a < b .
Proof plan. The remainder of the proof is devoted to constructing a run R ′ R' R ′ of A A A in which O O O is invoked by a correct process, messages are ultimately timely during O O O , and δ R ′ ( O ) = δ R ( O ) \delta_{R'}(O)=\delta_R(O) δ R ′ ( O ) = δ R ( O ) ; see Figure 5 . Given such a run, Lemma C.5 would give δ R ( O ) = δ R ′ ( O ) ≤ δ ( A ) \delta_{R}(O)=\delta_{R'}(O)\leq\delta(A) δ R ( O ) = δ R ′ ( O ) ≤ δ ( A ) , completing the proof.
Figure 5. Proof of Lemma C.7 : transforming the run R = ( S , T ) R = (S,T) R = ( S , T ) (top) into the run R ′ = ( S ′ , T ′ ) R' = (S',T') R ′ = ( S ′ , T ′ ) (bottom), by way of the intermediate run R ~ = ( S , T ~ ) \widetilde{R} = (S,\widetilde{T}) R = ( S , T ) (middle). 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 indicate no step is taken. Top: A correct process p p p invokes the operation O O O in step S [ a ] S[a] S [ a ] and returns in step S [ b ] S[b] S [ b ] . Messages are penultimately timely, but not ultimately timely, during O O O in R R R . τ \tau τ is the earliest sending time of a message in M p e n M_{\mathrm{pen}} M pen , and λ ∈ ( T [ b ] − 1 , τ + 1 ) \lambda\in(T[b] - 1,\tau+ 1) λ ∈ ( T [ b ] − 1 , τ + 1 ) . Penultimate timeliness forbids a red arc from the shaded band into step S [ b ] S[b] S [ b ] , which is taken by p p p ; hence the “▲” step is taken by a process other than p p p . Middle: R ~ \widetilde{R} R keeps the schedule S S S and compresses the time interval ( T [ b ] − 1 , T [ b ] ] (T[b] - 1,T[b]] ( T [ b ] − 1 , T [ b ]] into ( T [ b ] − 1 , λ ] (T[b] - 1,\lambda] ( T [ b ] − 1 , λ ] for the steps before the return, leaving the return step S [ b ] S[b] S [ b ] at time T [ b ] T[b] T [ b ] . δ R ~ ( O ) = δ R ( O ) \delta_{\widetilde{R}}(O) = \delta_R(O) δ R ( O ) = δ R ( O ) . Bottom: R ′ R' R ′ keeps the steps in S [ 0.. ( b − 1 ) ] S[0..(b - 1)] S [ 0.. ( b − 1 )] at their times in R ~ \widetilde{R} R , inserts k k k receive steps “▮” in the time interval ( λ , τ + 1 ) (\lambda,\tau+ 1) ( λ , τ + 1 ) for the messages in M l a t e M_{\mathrm{late}} M late , keeps the return step at time T [ b ] T[b] T [ b ] , and continues with a new infinite suffix (the wavy portion). In R ′ R' R ′ , the operation O O O is invoked in step S ′ [ a ] = S [ a ] S'[a] = S[a] S ′ [ a ] = S [ a ] and returns in step S ′ [ b + k ] = S [ b ] S'[b+k] = S[b] S ′ [ b + k ] = S [ b ] . Messages are ultimately timely during O O O in R ′ R' R ′ . Thus Lemma C.5 gives δ R ′ ( O ) ≤ δ ( A ) \delta_{R'}(O) \leq\delta(\mathcal{A}) δ R ′ ( O ) ≤ δ ( A ) ; since the construction preserves the latency of O O O , we have δ R ( O ) = δ R ~ ( O ) = δ R ′ ( O ) ≤ δ ( A ) \delta_R(O) = \delta_{\widetilde{R}}(O) = \delta_{R'}(O) \leq\delta(\mathcal{A}) δ R ( O ) = δ R ( O ) = δ R ′ ( O ) ≤ δ ( A ) , as desired.
Since messages are already timely during I e a r l y I_{\mathrm{early}} I early in R R R , only messages sent during I p e n I_{\mathrm{pen}} I pen to processes that take infinitely many steps can prevent ultimate timeliness. Let M p e n M_{\mathrm{pen}} M pen denote the set of such messages; we must ensure that each message in M p e n M_{\mathrm{pen}} M pen has latency at most one in R ′ R' R ′ .
A message in M p e n M_{\mathrm{pen}} M pen received in S [ b ] S[b] S [ b ] is received by p p p . Because p p 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 M p e n M_{\mathrm{pen}} M pen in two stages of construction:
First, we will retime R R R into an intermediate run R ~ \widetilde{R} R in which every step preceding S [ b ] S[b] S [ b ] occurs early enough to make those messages received before S [ b ] S[b] S [ b ] timely. This retiming also clears a stretch of time that precedes S [ b ] S[b] S [ b ] and yet lies less than one time unit after every message in M p e n M_{\mathrm{pen}} M pen is sent.
We now give the full proof following the plan.
Setup. Let I e a r l y I_{\mathrm{early}} I early and I p e n I_{\mathrm{pen}} I pen be as in Definition C.6 (2) for O O O ; recall that they partition [ T [ a ] , T [ b ] − 1 ] [T[a], T[b]-1] [ T [ a ] , T [ b ] − 1 ] . Let M M M denote the (finite) set of messages in R R R sent during [ T [ a ] , T [ b ] − 1 ] [T[a], T[b]-1] [ T [ a ] , T [ b ] − 1 ] to a process that takes infinitely many steps, and let M p e n ⊆ M M_{\mathrm{pen}} \subseteq M M pen ⊆ M consist of those sent during I p e n I_{\mathrm{pen}} I pen . Recall that by condition (2)(a), messages are timely during I e a r l y I_{\mathrm{early}} I early in R R R . Since messages are not ultimately timely during O O O , M p e n M_{\mathrm{pen}} M pen must contain a message whose latency exceeds one, hence M p e n ≠ ∅ M_{\mathrm{pen}} \ne\varnothing M pen = ∅ .
Let τ \tau τ be the earliest send time of a message in M p e n M_{\mathrm{pen}} M pen , so that T [ a ] ≤ τ ≤ T [ b ] − 1 T[a] \le\tau\le T[b]-1 T [ a ] ≤ τ ≤ T [ b ] − 1 and τ > T [ b ] − 2 \tau> T[b]-2 τ > T [ b ] − 2 . Since τ + 1 > T [ b ] − 1 \tau+1 > T[b]-1 τ + 1 > T [ b ] − 1 , we may fix an arbitrary time λ ∈ ( T [ b ] − 1 , τ + 1 ) \lambda\in(T[b]-1,\tau+1) λ ∈ ( T [ b ] − 1 , τ + 1 ) , obtaining
T [ b ] − 1 < λ < τ + 1 ≤ T [ b ] . (13) T[b]-1 < \lambda< \tau+1 \le T[b]. \tag*{(13)} T [ b ] − 1 < λ < τ + 1 ≤ T [ b ] . (13)
An intermediate run. We now retime R R R so that every step preceding the response step S [ b ] S[b] S [ b ] occurs at time at most λ \lambda λ : For such steps we will compress the interval ( T [ b ] − 1 , T [ b ] ] (T[b]-1,T[b]] ( T [ b ] − 1 , T [ b ]] into ( T [ b ] − 1 , λ ] (T[b]-1,\lambda] ( T [ b ] − 1 , λ ] , while S [ b ] S[b] S [ b ] and every later step keeps its time.
To do so, define ϕ : ( − ∞ , T [ b ] ] → R \phi: (-\infty,T[b]] \to\mathbb{R} ϕ : ( − ∞ , T [ b ]] → R by
ϕ ( t ) ≜ { t , t ≤ T [ b ] − 1 , Affine ( T [ b ] − 1 , T [ b ] ] → ( T [ b ] − 1 , λ ] ( t ) , T [ b ] − 1 < t ≤ T [ b ] . \phi(t) \triangleq
\begin{cases}
t, & t \le T[b]-1,\\
\operatorname{Affine}_{(T[b]-1,T[b]]\to(T[b]-1,\lambda]}(t), & T[b]-1 < t \le T[b].
\end{cases} ϕ ( t ) ≜ { t , Affine ( T [ b ] − 1 , T [ b ]] → ( T [ b ] − 1 , λ ] ( t ) , t ≤ T [ b ] − 1 , T [ b ] − 1 < t ≤ T [ b ] .
By (13) , the map ϕ \phi ϕ is strictly increasing; ϕ ( t ) = t \phi(t)=t ϕ ( t ) = t for all t ≤ T [ b ] − 1 t \le T[b]-1 t ≤ T [ b ] − 1 ; and the range of ϕ \phi ϕ is contained in ( − ∞ , λ ] (-\infty,\lambda] ( − ∞ , λ ] . Define the infinite sequence T ~ \widetilde{T} T by
T ~ [ i ] ≜ { ϕ ( T [ i ] ) , i < b , T [ i ] , i ≥ b . \widetilde{T}[i] \triangleq
\begin{cases}
\phi(T[i]), & i < b,\\
T[i], & i \ge b.
\end{cases} T [ i ] ≜ { ϕ ( T [ i ]) , T [ i ] , i < b , i ≥ b .
The sequence T ~ \widetilde{T} T is non-decreasing and unbounded. Furthermore, it can be verified that T [ i ] < T [ j ] T[i] < T[j] T [ i ] < T [ j ] only if T ~ [ i ] < T ~ [ j ] \widetilde{T}[i] < \widetilde{T}[j] T [ i ] < T [ j ] . Thus, R ~ = ( S , T ~ ) \widetilde{R}=(S,\widetilde{T}) R = ( S , T ) is a run of A A A with the same schedule, and hence the same correct processes, as R R R . Since a < b a < b a < b and T [ a ] ≤ T [ b ] − 1 T[a] \le T[b]-1 T [ a ] ≤ T [ b ] − 1 , we have T ~ [ a ] = ϕ ( T [ a ] ) = T [ a ] \widetilde{T}[a]=\phi(T[a])=T[a] T [ a ] = ϕ ( T [ a ]) = T [ a ] ; also, T ~ [ b ] = T [ b ] \widetilde{T}[b]=T[b] T [ b ] = T [ b ] . Hence δ R ~ ( O ) = δ R ( O ) \delta_{\widetilde{R}}(O)=\delta_R(O) δ R ( O ) = δ R ( O ) .
Since T ~ [ a ] = T [ a ] \widetilde{T}[a]=T[a] T [ a ] = T [ a ] and T ~ [ b ] = T [ b ] \widetilde{T}[b]=T[b] T [ b ] = T [ b ] , and since T ~ \widetilde{T} T agrees with T T T at every step whose time is at most T [ b ] − 1 T[b]-1 T [ b ] − 1 in either run, M M M is also the set of messages in R ~ \widetilde{R} R sent during [ T ~ [ a ] , T ~ [ b ] − 1 ] [\widetilde{T}[a],\widetilde{T}[b]-1] [ T [ a ] , T [ b ] − 1 ] that timeliness constrains, and each has the same send time in both runs. Let M l a t e ⊆ M M_{\mathrm{late}} \subseteq M M late ⊆ M consist of the (finitely many) messages received in a step S [ j ] S[j] S [ j ] with j > b j>b j > b .
Claim C.8. Fix a message m ∈ M m \in M m ∈ M with send time s s s , and let S [ i ] S[i] S [ i ] and S [ j ] S[j] S [ j ] be its send and receive steps. Then:
(a) i < b i < b i < b and T [ i ] = T ~ [ i ] = s T[i]=\widetilde{T}[i]=s T [ i ] = T [ i ] = s .
(b) If s ≤ T [ b ] − 2 s \le T[b]-2 s ≤ T [ b ] − 2 , then T [ j ] ≤ s + 1 ≤ T [ b ] − 1 T[j] \le s+1 \le T[b]-1 T [ j ] ≤ s + 1 ≤ T [ b ] − 1 and j < b j < b j < b .
(c) If s > T [ b ] − 2 s > T[b]-2 s > T [ b ] − 2 , then s ∈ I p e n s \in I_{\mathrm{pen}} s ∈ I pen , so m ∈ M p e n m \in M_{\mathrm{pen}} m ∈ M pen and s ≥ τ s \ge\tau s ≥ τ .
Proof. We prove each part in turn.
(a) The monotonicity of T ~ \widetilde{T} T , with T ~ [ i ] = s ≤ T [ b ] − 1 < T ~ [ b ] \widetilde{T}[i]=s \le T[b]-1 < \widetilde{T}[b] T [ i ] = s ≤ T [ b ] − 1 < T [ b ] , yields i < b i < b i < b . The definitions of ϕ \phi ϕ and T ~ \widetilde{T} T then give T [ i ] = T ~ [ i ] = s T[i]=\widetilde{T}[i]=s T [ i ] = T [ i ] = s .
(b) Since s ∈ I e a r l y s \in I_{\mathrm{early}} s ∈ I early , condition (2)(a) of penultimate timeliness gives δ R ( m ) ≤ 1 \delta_R(m) \le1 δ R ( m ) ≤ 1 , and hence T [ j ] ≤ T [ i ] + 1 = s + 1 ≤ T [ b ] − 1 < T [ b ] T[j] \le T[i]+1=s+1 \le T[b]-1 < T[b] T [ j ] ≤ T [ i ] + 1 = s + 1 ≤ T [ b ] − 1 < T [ b ] . The monotonicity of T T T therefore implies j < b j < b j < b .
(c) Since s ∈ [ T [ a ] , T [ b ] − 1 ] s \in[T[a],T[b]-1] s ∈ [ T [ a ] , T [ b ] − 1 ] and s > T [ b ] − 2 s > T[b]-2 s > T [ b ] − 2 , we have s ∈ I p e n s \in I_{\mathrm{pen}} s ∈ I pen and hence m ∈ M p e n m \in M_{\mathrm{pen}} m ∈ M pen . By the definition of τ \tau τ , it follows that s ≥ τ s \ge\tau s ≥ τ .
Claim C.9. In R ~ \widetilde{R} R , the following hold:
(a) Every i < b i < b i < b satisfies T ~ [ i ] ≤ λ \widetilde{T}[i] \le\lambda T [ i ] ≤ λ , while
T ~ [ b ] − 1 < λ < τ + 1 ≤ T ~ [ b ] . \widetilde{T}[b] - 1 < \lambda< \tau+ 1 \le\widetilde{T}[b]. T [ b ] − 1 < λ < τ + 1 ≤ T [ b ] . (b) Every message m ∈ M l a t e m \in M_{\mathrm{late}} m ∈ M late is sent to a process other than p p p , in a step S [ i ] S[i] S [ i ] with i < b i < b i < b and T ~ [ i ] ≥ τ \widetilde{T}[i] \ge\tau T [ i ] ≥ τ .
(c) Every message in M ∖ M l a t e M \setminus M_{\mathrm{late}} M ∖ M late is received in a step S [ j ] S[j] S [ j ] with j ≤ b j \le b j ≤ b and has latency at most one.
Proof. (a) For every i < b i < b i < b , we have T ~ [ i ] = ϕ ( T [ i ] ) ≤ λ \widetilde{T}[i] = \phi(T[i]) \le\lambda T [ i ] = ϕ ( T [ i ]) ≤ λ because the range of ϕ \phi ϕ is contained in ( − ∞ , λ ] (-\infty,\lambda] ( − ∞ , λ ] . Moreover, since T ~ [ b ] = T [ b ] \widetilde{T}[b] = T[b] T [ b ] = T [ b ] , the displayed inequalities are a restatement of (13) .
(b) Fix a message m ∈ M l a t e m \in M_{\mathrm{late}} m ∈ M late , let S [ i ] S[i] S [ i ] and S [ j ] S[j] S [ j ] be its send and receive steps, and write s ≜ T ~ [ i ] s \mathrel{\triangleq} \widetilde{T}[i] s ≜ T [ i ] . The definition of M l a t e M_{\mathrm{late}} M late gives j > b j > b j > b . Claim C.8 (a) gives i < b i < b i < b . Claim C.8 (b) then rules out s ≤ T [ b ] − 2 s \le T[b] - 2 s ≤ T [ b ] − 2 , so Claim C.8 (c) applies and gives s ∈ I p e n s \in I_{\mathrm{pen}} s ∈ I pen and s ≥ τ s \ge\tau s ≥ τ . Finally, if m m m were sent to p p p , then S [ b ] S[b] S [ b ] and S [ j ] S[j] S [ j ] would both be steps of p p p , implying T [ j ] > T [ b ] T[j] > T[b] T [ j ] > T [ b ] . But p p p takes infinitely many steps and s ∈ I p e n s \in I_{\mathrm{pen}} s ∈ I pen , so condition (2)(b) of penultimate timeliness would yield T [ j ] ≤ s + 1 ≤ T [ b ] T[j] \le s + 1 \le T[b] T [ j ] ≤ s + 1 ≤ T [ b ] , a contradiction.
(c) Fix a message m ∈ M ∖ M l a t e m \in M \setminus M_{\mathrm{late}} m ∈ M ∖ M late with send time s s s , and let S [ i ] S[i] S [ i ] and S [ j ] S[j] S [ j ] be its send and receive steps. Claim C.8 applies to m m m , and the definition of M l a t e M_{\mathrm{late}} M late gives j ≤ b j \le b j ≤ b . We bound δ ~ R ( m ) = T ~ [ j ] − s \widetilde{\delta}_{R}(m) = \widetilde{T}[j] - s δ R ( m ) = T [ j ] − s in three cases.
If s ≤ T [ b ] − 2 s \le T[b] - 2 s ≤ T [ b ] − 2 , then Claim C.8 (b) gives j < b j < b j < b and T [ j ] ≤ s + 1 ≤ T [ b ] − 1 T[j] \le s + 1 \le T[b] - 1 T [ j ] ≤ s + 1 ≤ T [ b ] − 1 . Thus ϕ ( T [ j ] ) = T [ j ] \phi(T[j]) = T[j] ϕ ( T [ j ]) = T [ j ] , and δ ~ R ( m ) = T [ j ] − s ≤ 1 \widetilde{\delta}_{R}(m) = T[j] - s \le1 δ R ( m ) = T [ j ] − s ≤ 1 .
Now suppose s > T [ b ] − 2 s > T[b] - 2 s > T [ b ] − 2 . By Claim C.8 (c), s ∈ I p e n s \in I_{\mathrm{pen}} s ∈ I pen and s ≥ τ s \ge\tau s ≥ τ . If j < b j < b j < b , then T ~ [ j ] ≤ λ \widetilde{T}[j] \le\lambda T [ j ] ≤ λ by part (a), so δ ~ R ( m ) ≤ λ − τ < 1 \widetilde{\delta}_{R}(m) \le\lambda- \tau< 1 δ R ( m ) ≤ λ − τ < 1 . If instead j = b j = b j = b , then m m m is received by p p p , which takes infinitely many steps, so condition (2)(b) of penultimate timeliness gives T [ b ] − s ≤ 1 T[b] - s \le1 T [ b ] − s ≤ 1 . Hence δ ~ R ( m ) = T [ b ] − s ≤ 1 \widetilde{\delta}_{R}(m) = T[b] - s \le1 δ R ( m ) = T [ b ] − s ≤ 1 .
Inserting receive steps
Let σ 0 ≜ S [ 0.. ( b − 1 ) ] \sigma_0 \mathrel{\triangleq} S[0..(b - 1)] σ 0 ≜ S [ 0.. ( b − 1 )] , a schedule prefix of A \mathcal{A} A . By Claim C.9 (b), every message in M l a t e M_{\mathrm{late}} M late is sent in σ 0 \sigma_0 σ 0 to a process other than p p p . Moreover, its receive step in S S S has index greater than b b b , so it has not yet been received by the end of σ 0 \sigma_0 σ 0 .
We may therefore extend σ 0 \sigma_0 σ 0 by a finite sequence σ 1 \sigma_1 σ 1 of steps, all taken by processes other than p p p , in which every message in M l a t e M_{\mathrm{late}} M late is received: A recipient that is correct in S S S takes a step according to A \mathcal{A} A , and a recipient that is faulty in S S S —possible only under Byzantine failures, since these recipients take infinitely many steps—takes an arbitrary step receiving the message. Write k ≜ ∣ σ 1 ∣ k \mathrel{\triangleq} |\sigma_1| k ≜ ∣ σ 1 ∣ . Because σ 1 \sigma_1 σ 1 contains no step of p p p and step S [ b ] S[b] S [ b ] is a step of p p p ,
σ ′ ≜ σ 0 ∘ σ 1 ∘ ⟨ S [ b ] ⟩ \sigma' \mathrel{\triangleq} \sigma_0 \mathbin{\circ} \sigma_1 \mathbin{\circ} \langle S[b]\rangle σ ′ ≜ σ 0 ∘ σ 1 ∘ ⟨ S [ b ]⟩
is a schedule prefix of A \mathcal{A} A by commutativity. Extend σ ′ \sigma' σ ′ to a schedule S ′ S' S ′ of A \mathcal{A} A such that exactly the processes that take infinitely many steps in S S S do so in S ′ S' S ′ , and every correct process in S S S is correct in S ′ S' S ′ . In particular, p p p is correct in S ′ S' S ′ . By construction,
S ′ [ 0.. ( b − 1 ) ] = S [ 0.. ( b − 1 ) ] , S ′ [ b . . ( b + k − 1 ) ] = σ 1 , S ′ [ b + k ] = S [ b ] . S'[0..(b-1)] = S[0..(b-1)], \qquad S'[b..(b+k-1)] = \sigma_1, \qquad S'[b+k] = S[b]. S ′ [ 0.. ( b − 1 )] = S [ 0.. ( b − 1 )] , S ′ [ b .. ( b + k − 1 )] = σ 1 , S ′ [ b + k ] = S [ b ] .
Assigning times
To construct R ′ R' R ′ , we keep the steps in S [ 0.. ( b − 1 ) ] S[0..(b-1)] S [ 0.. ( b − 1 )] at their times in R ~ \widetilde{R} R , place the k k k inserted steps in the interval ( λ , τ + 1 ) (\lambda,\tau+1) ( λ , τ + 1 ) , and keep the return step at time T ~ [ b ] \widetilde{T}[b] T [ b ] . Specifically, define
T ′ [ i ] ≜ { T ~ [ i ] , i < b , Affine ( b − 1 , b + k ) → ( λ , τ + 1 ) ( i ) , b ≤ i < b + k , Affine [ b + k , + ∞ ) → [ T ~ [ b ] , + ∞ ) ( i ) , i ≥ b + k . T'[i] \mathrel{\triangleq}
\begin{cases}
\widetilde{T}[i], & i < b,\\
\operatorname{Affine}_{(b-1,b+k)\to(\lambda,\tau+1)}(i), & b \le i < b+k,\\
\operatorname{Affine}_{[b+k,+\infty)\to[\widetilde{T}[b],+\infty)}(i), & i \ge b+k.
\end{cases} T ′ [ i ] ≜ ⎩ ⎨ ⎧ T [ i ] , Affine ( b − 1 , b + k ) → ( λ , τ + 1 ) ( i ) , Affine [ b + k , + ∞ ) → [ T [ b ] , + ∞ ) ( i ) , i < b , b ≤ i < b + k , i ≥ b + k .
By Claim C.9 (a), every step in S [ 0.. ( b − 1 ) ] S[0..(b-1)] S [ 0.. ( b − 1 )] has time at most λ \lambda λ . The inserted steps have strictly increasing times in ( λ , τ + 1 ) (\lambda,\tau+1) ( λ , τ + 1 ) , the return step has time T ~ [ b ] ≥ τ + 1 \widetilde{T}[b] \ge\tau+1 T [ b ] ≥ τ + 1 , and all subsequent steps have strictly increasing times exceeding T ~ [ b ] \widetilde{T}[b] T [ b ] . Thus T ′ T' T ′ is non-decreasing and unbounded. Moreover, all required strict inequalities are either inherited from R ~ \widetilde{R} R or follow from these strict separations. Thus R ′ = ( S ′ , T ′ ) R'=(S',T') R ′ = ( S ′ , T ′ ) is a run of A A A .
In R ′ R' R ′ , the operation O O O is invoked in step S ′ [ a ] = S [ a ] S'[a]=S[a] S ′ [ a ] = S [ a ] and returns in step S ′ [ b + k ] = S [ b ] S'[b+k]=S[b] S ′ [ b + k ] = S [ b ] ; it is invoked by p p p , which is correct in S ′ S' S ′ . Since T ′ [ a ] = T ~ [ a ] T'[a]=\widetilde{T}[a] T ′ [ a ] = T [ a ] and T ′ [ b + k ] = T ~ [ b ] T'[b+k]=\widetilde{T}[b] T ′ [ b + k ] = T [ b ] , we have δ R ′ ( O ) = δ R ~ ( O ) \delta_{R'}(O)=\delta_{\widetilde{R}}(O) δ R ′ ( O ) = δ R ( O ) .
Claim C.10. Messages are ultimately timely during O O O in R ′ R' R ′ .
Proof. Fix a message m m m sent at a time in [ T ′ [ a ] , T ′ [ b + k ] − 1 ] = [ T ~ [ a ] , T ~ [ b ] − 1 ] [T'[a],T'[b+k]-1]=[\widetilde{T}[a],\widetilde{T}[b]-1] [ T ′ [ a ] , T ′ [ b + k ] − 1 ] = [ T [ a ] , T [ b ] − 1 ] to a process that takes infinitely many steps in S ′ S' S ′ , and let S ′ [ i ] S'[i] S ′ [ i ] be its send step. By the definition of T ′ T' T ′ and Claim C.9(a), every ℓ ≥ b \ell\ge b ℓ ≥ b satisfies T ′ [ ℓ ] > λ > T ~ [ b ] − 1 T'[\ell]>\lambda>\widetilde{T}[b]-1 T ′ [ ℓ ] > λ > T [ b ] − 1 . Hence i < b i<b i < b , so S ′ [ i ] = S [ i ] S'[i]=S[i] S ′ [ i ] = S [ i ] and T ′ [ i ] = T ~ [ i ] T'[i]=\widetilde{T}[i] T ′ [ i ] = T [ i ] ; in particular, m m m is also sent in R ~ \widetilde{R} R , with the same send time, and by the choice of S ′ S' S ′ its recipient is the same in both schedules and takes infinitely many steps in each. Thus m ∈ M m\in M m ∈ M .
If m ∉ M l a t e m\notin M_{\mathrm{late}} m ∈ / M late , then by Claim C.9(c), m m m is received in a step S ′ [ j ] S'[j] S ′ [ j ] with j ≤ b j\le b j ≤ b and δ R ~ ( m ) ≤ 1 \delta_{\widetilde{R}}(m)\le1 δ R ( m ) ≤ 1 . Its receive step in R ′ R' R ′ is S ′ [ j ] S'[j] S ′ [ j ] if j < b j<b j < b , and S ′ [ b + k ] S'[b+k] S ′ [ b + k ] if j = b j=b j = b ; in either case, its receive time is the same in R ′ R' R ′ as in R ~ \widetilde{R} R . Therefore δ R ′ ( m ) = δ R ~ ( m ) ≤ 1 \delta_{R'}(m)=\delta_{\widetilde{R}}(m)\le1 δ R ′ ( m ) = δ R ( m ) ≤ 1 .
If m ∈ M l a t e m\in M_{\mathrm{late}} m ∈ M late , then Claim C.9(b) gives T ′ [ i ] = T ~ [ i ] ≥ τ T'[i]=\widetilde{T}[i]\ge\tau T ′ [ i ] = T [ i ] ≥ τ . By construction, m m m is received in an inserted step S ′ [ j ] S'[j] S ′ [ j ] with b ≤ j ′ < b + k b\le j'<b+k b ≤ j ′ < b + k ; the definition of T ′ T' T ′ therefore gives T ′ [ j ′ ] < τ + 1 T'[j']<\tau+1 T ′ [ j ′ ] < τ + 1 . Hence δ R ′ ( m ) = T ′ [ j ′ ] − T ′ [ i ] < ( τ + 1 ) − τ = 1 \delta_{R'}(m)=T'[j']-T'[i]<(\tau+1)-\tau=1 δ R ′ ( m ) = T ′ [ j ′ ] − T ′ [ i ] < ( τ + 1 ) − τ = 1 .
Since m m m was arbitrary, messages are ultimately timely during O O O in R ′ R' R ′ .
By Lemma C.5, δ R ′ ( O ) ≤ δ ( A ) \delta_{R'}(O)\le\delta(A) δ R ′ ( O ) ≤ δ ( A ) . Since δ R ( O ) = δ R ~ ( O ) = δ R ′ ( O ) \delta_R(O)=\delta_{\widetilde{R}}(O)=\delta_{R'}(O) δ R ( O ) = δ R ( O ) = δ R ′ ( O ) , the claim follows. Lemma C.7
Proofs of the Completion Lemmas
We prove the crash- and Byzantine-failure completion lemmas in turn.
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 A A be a loquacious algorithm with δ ( A ) ≤ 2 \delta(A)\le2 δ ( A ) ≤ 2 . Let p p p be a process, and let Q Q Q be a set of processes such that ∣ Q ∣ = n − f |Q|=n-f ∣ Q ∣ = n − f and p ∈ Q p\in Q p ∈ Q .
Suppose that σ \sigma σ is a schedule prefix of A A A in which the following hold:
Process p p p invokes an operation and broadcasts a message m m m in step σ [ a ] \sigma[a] σ [ a ] .
For each q ∈ Q q\in Q q ∈ Q , process q q q receives message m m m and broadcasts a message m q m_q m q in step σ [ j q ] \sigma[j_q] σ [ j q ] .
Process p p p receives the set of messages { m q : q ∈ Q } \{m_q:q\in Q\} { m q : q ∈ Q } in step σ [ b ] \sigma[b] σ [ b ] .
Between steps σ [ a ] \sigma[a] σ [ a ] and σ [ b ] \sigma[b] σ [ b ] , inclusive, the only steps are those specified above.
Then the operation invoked by p p p in step σ [ a ] \sigma[a] σ [ a ] returns no later than step σ [ b ] \sigma[b] σ [ b ] .
Proof. In a system with crash failures, let A A A be a loquacious algorithm with δ ( A ) ≤ 2 \delta(A)\le2 δ ( A ) ≤ 2 , and let σ \sigma σ be a schedule prefix of A A A that satisfies the assumptions in the lemma statement.
Suppose, for the sake of contradiction, that process p p p has not returned from the operation by step σ [ b ] \sigma[b] σ [ b ] . Extend the prefix σ [ 0.. b ] \sigma[0..b] σ [ 0.. b ] to a schedule S S S of A A A in which every process in Q Q Q takes infinitely many further steps and receives every message sent to it, while every remaining process takes no further steps. Since p p p is correct in S S S and δ ( A ) < ∞ \delta(A)<\infty δ ( A ) < ∞ , Proposition 2.7 implies that the operation invoked in step S [ a ] = σ [ a ] S[a]=\sigma[a] S [ a ] = σ [ a ] eventually returns, in some step S [ c ] S[c] S [ c ] with c > b c>b c > b .
Now, define the time sequence T T T as follows (see Figure 6 ):
Figure 6. Proof of Lemma 4.21. Let A \mathcal{A} A be a loquacious algorithm with δ ( A ) ≤ 2 \delta(\mathcal{A}) \le2 δ ( A ) ≤ 2 , and suppose toward a contradiction that the operation O O O , invoked by p p p in step a a a , has not returned by step b b b . Extend the schedule prefix so that exactly the processes in Q Q Q are correct; then O O O returns in some step c > b c > b c > b , and the times T T T give δ ( O ) = T [ c ] − T [ a ] = 5 / 2 \delta(O) = T[c] - T[a] = 5/2 δ ( O ) = T [ c ] − T [ a ] = 5/2 . The figure depicts the instance n = 4 n = 4 n = 4 , f = 1 f = 1 f = 1 , and Q = { p , q , r } Q = \{p,q,r\} Q = { p , q , r } , in which p p p , q q q , and r r r are correct and s s s crashes; in general ∣ Q ∣ = n − f |Q| = n-f ∣ Q ∣ = n − f . The shaded bands show the two intervals from Definition C.6 (2) of penultimately timely: (a) I e a r l y = [ 0 , 1 / 2 ] I_{\mathrm{early}} = [0,1/2] I early = [ 0 , 1/2 ] ; and (b) I p e n = ( 1 / 2 , 3 / 2 ] I_{\mathrm{pen}} = (1/2,3/2] I pen = ( 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 O O , and Lemma C.7 gives δ ( O ) ≤ δ ( A ) ≤ 2 \delta(O) \le\delta(\mathcal{A}) \le2 δ ( O ) ≤ δ ( A ) ≤ 2 , contradicting δ ( O ) = 5 / 2 \delta(O) = 5/2 δ ( O ) = 5/2 .
T [ i ] ≜ { Affine ( − ∞ , a ] → ( − ∞ , 0 ] ( i ) , i ≤ a , Affine ( a , b ) → ( 3 / 4 , 1 ) ( i ) , a < i < b , Affine [ b , c ] → [ 7 / 4 , 5 / 2 ] ( i ) , b ≤ i ≤ c , Affine ( c , + ∞ ) → ( 5 / 2 , + ∞ ) ( i ) , i > c . T[i] \mathrel{\triangleq} \begin{cases}
\operatorname{Affine}_{(-\infty,a]\to(-\infty,0]}(i), & i \le a,\\
\operatorname{Affine}_{(a,b)\to(3/4,1)}(i), & a < i < b,\\
\operatorname{Affine}_{[b,c]\to[7/4,5/2]}(i), & b \le i \le c,\\
\operatorname{Affine}_{(c,+\infty)\to(5/2,+\infty)}(i), & i > c.
\end{cases} T [ i ] ≜ ⎩ ⎨ ⎧ Affine ( − ∞ , a ] → ( − ∞ , 0 ] ( i ) , Affine ( a , b ) → ( 3/4 , 1 ) ( i ) , Affine [ b , c ] → [ 7/4 , 5/2 ] ( i ) , Affine ( c , + ∞ ) → ( 5/2 , + ∞ ) ( i ) , i ≤ a , a < i < b , b ≤ i ≤ c , i > c .
It can be verified that T T T is strictly increasing and unbounded, so R = ( S , T ) R = (S,T) R = ( S , T ) is a run of A \mathcal{A} A . Let O O O denote the operation in R R R invoked in step S [ a ] S[a] S [ a ] and returning in step S [ c ] S[c] S [ c ] . It follows that δ ( O ) = T [ c ] − T [ a ] = 5 / 2 \delta(O) = T[c] - T[a] = 5/2 δ ( O ) = T [ c ] − T [ a ] = 5/2 .
Claim. Messages are penultimately timely during O O O in R R R .
Proof. Since O O O is complete, we must verify conditions (2)(a) and (2)(b) of Definition C.6 .
I e a r l y = [ T [ a ] , T [ c ] − 2 ] = [ 0 , 1 2 ] I_{\mathrm{early}} = [T[a],T[c]-2] = \left[0,\frac{1}{2}\right] I early = [ T [ a ] , T [ c ] − 2 ] = [ 0 , 2 1 ]
(blue interval in Figure 6 ).
The only step in this interval is S [ a ] S[a] S [ a ] , so the messages sent during this interval to a process that takes infinitely many steps are precisely the copies of m m m sent in step S [ a ] S[a] S [ a ] to processes in Q Q Q . By assumption 2, each such message is received in some step S [ j q ] S[j_q] S [ j q ] with a < j q < b a < j_q < b a < j q < b , and hence before time 1. Since these messages are sent at time 0, each has latency less than 1.
I p e n = [ T [ a ] , T [ c ] − 1 ] ∖ I e a r l y = ( 1 2 , 3 2 ] I_{\mathrm{pen}} = [T[a],T[c]-1] \setminus I_{\mathrm{early}} = \left(\frac{1}{2},\frac{3}{2}\right] I pen = [ T [ a ] , T [ c ] − 1 ] ∖ I early = ( 2 1 , 2 3 ]
(orange interval in Figure 6 ).
Since p p p takes infinitely many steps, we must examine the messages sent in this interval to p p p . Let m ~ \tilde{m} m ~ be such a message, sent in step S [ j ] S[j] S [ j ] . Since
T [ a ] = 0 < 1 2 < T [ j ] ≤ 3 2 < 7 4 = T [ b ] (14) T[a] = 0 < \frac{1}{2} < T[j] \le\frac{3}{2} < \frac{7}{4} = T[b] \tag*{(14)} T [ a ] = 0 < 2 1 < T [ j ] ≤ 2 3 < 4 7 = T [ b ] (14)
and T T T is strictly increasing, we have a < j < b a < j < b a < j < b . So by assumptions 2 and 4, we have m ~ = m q \tilde{m} = m_q m ~ = m q for some q ∈ Q q \in Q q ∈ Q . By assumption 3, message m ~ \tilde{m} m ~ is received in step S [ b ] S[b] S [ b ] . Furthermore, j > a j > a j > a implies T [ j ] > 3 / 4 T[j] > 3/4 T [ j ] > 3/4 by the definition of T T T . Therefore,
δ ( m ~ ) = T [ b ] − T [ j ] < 7 4 − 3 4 = 1. \delta(\tilde{m}) = T[b] - T[j] < \frac{7}{4} - \frac{3}{4} = 1. δ ( m ~ ) = T [ b ] − T [ j ] < 4 7 − 4 3 = 1.
By Lemma C.7 , the claim implies δ ( O ) ≤ δ ( A ) ≤ 2 \delta(O) \leq\delta(A) \leq2 δ ( O ) ≤ δ ( A ) ≤ 2 . This contradicts δ ( O ) = 5 / 2 \delta(O) = 5/2 δ ( O ) = 5/2 .
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 A A be a loquacious algorithm with δ ( A ) ≤ 2 \delta(A) \leq2 δ ( A ) ≤ 2 . Let p p p be a process, and let Q Q Q be a set of processes such that ∣ Q ∣ = n − f |Q| = n - f ∣ Q ∣ = n − f and p ∈ Q p \in Q p ∈ Q . Suppose that σ \sigma σ is a schedule prefix of A A A in which the following hold:
Process p p p invokes an operation and broadcasts a message m m m in step σ [ a ] \sigma[a] σ [ a ] .
For each q ∈ Q q \in Q q ∈ Q , process q q q receives m m m and broadcasts a message m q m_q m q in step σ [ j q ] \sigma[j_q] σ [ j q ] .
Process p p p receives the set of messages { m q : q ∈ Q } \{m_q : q \in Q\} { m q : q ∈ Q } in step σ [ b ] \sigma[b] σ [ b ] .
Between steps σ [ a ] \sigma[a] σ [ a ] and σ [ b ] \sigma[b] σ [ b ] , inclusive, the only steps are those specified above.
Processes in Q Q Q follow the algorithm A A A throughout σ [ 0.. b ] \sigma[0..b] σ [ 0.. b ] .
Then the operation invoked by p p p in step σ [ a ] \sigma[a] σ [ a ] returns no later than step σ [ b ] \sigma[b] σ [ b ] .
Proof. The proof of Lemma 4.21 applies with only one change: We must justify its initial extension of σ [ 0.. b ] \sigma[0..b] σ [ 0.. b ] to a schedule of A A A . Since every process in Q Q Q follows A A A throughout σ [ 0.. b ] \sigma[0..b] σ [ 0.. b ] , we can extend this prefix to a schedule of A A A by letting these processes take infinitely many further steps according to A A 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 Q Q are exactly the ones that take infinitely many steps and exactly the correct ones, and so there are n − ∣ Q ∣ = f n - |Q| = f n − ∣ Q ∣ = f faulty processes. Because p p 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.
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 § 5 . The proof relies on the following lemma.
Lemma D.1. In a system with crash failures, let A A A be a loquacious algorithm with δ ( A ) ≤ 1 \delta(A) \leq1 δ ( A ) ≤ 1 . Suppose that σ \sigma σ is a schedule prefix of A A A in which some process p p p :
invokes an operation and broadcasts a message m m m in step σ [ a ] \sigma[a] σ [ a ] , and
receives its own message m m m in step σ [ b ] \sigma[b] σ [ b ] .
Then the operation invoked by p p p in step σ [ a ] \sigma[a] σ [ a ] returns no later than step σ [ b ] \sigma[b] σ [ b ] .
Proof. Let the worst-case message delay of A \mathcal{A} A be k ≤ 1 k \le1 k ≤ 1 . Suppose, for the sake of contradiction, that the operation invoked by p p p in step σ [ a ] \sigma[a] σ [ a ] does not return by step σ [ b ] \sigma[b] σ [ b ] . By assumption, b > a b > a b > a .
Extend σ [ 0.. b ] \sigma[0..b] σ [ 0.. b ] to an (infinite) schedule S S S of A \mathcal{A} A in which p p p takes infinitely many steps. Then p p p is correct in S S S , and since A \mathcal{A} A has finite worst-case message delay, Proposition 2.7 implies that the operation invoked in step S [ a ] S[a] S [ a ] eventually returns. Let S [ c ] S[c] S [ c ] be its return step, where c > b c > b c > b , and call the complete operation O O O .
Assign times T T T to the steps in S S S by setting
T [ i ] ≔ { Affine ( − ∞ , a ] → ( − ∞ , 0 ] ( i ) , i ≤ a , Affine ( a , b ] → ( 1 / 2 , 3 / 4 ] ( i ) , a < i ≤ b , Affine ( b , c ] → ( 3 / 4 , 3 / 2 ] ( i ) , b < i ≤ c , Affine ( c , + ∞ ) → ( 3 / 2 , + ∞ ) ( i ) , i > c . T[i] \coloneqq
\begin{cases}
\operatorname{Affine}_{(-\infty,a]\to(-\infty,0]}(i), & i \le a,\\
\operatorname{Affine}_{(a,b]\to(1/2,3/4]}(i), & a < i \le b,\\
\operatorname{Affine}_{(b,c]\to(3/4,3/2]}(i), & b < i \le c,\\
\operatorname{Affine}_{(c,+\infty)\to(3/2,+\infty)}(i), & i > c.
\end{cases} T [ i ] : = ⎩ ⎨ ⎧ Affine ( − ∞ , a ] → ( − ∞ , 0 ] ( i ) , Affine ( a , b ] → ( 1/2 , 3/4 ] ( i ) , Affine ( b , c ] → ( 3/4 , 3/2 ] ( i ) , Affine ( c , + ∞ ) → ( 3/2 , + ∞ ) ( i ) , i ≤ a , a < i ≤ b , b < i ≤ c , i > c .
This sequence is strictly increasing and unbounded. Let R = ( S , T ) R = (S,T) R = ( S , T ) be the resulting run.
Since O O O is complete, we show that messages are penultimately timely during O O O in R R R by verifying the two conditions of Definition C.6(2). Condition (2)(a) holds vacuously because T [ c ] − 2 < T [ a ] T[c] - 2 < T[a] T [ c ] − 2 < T [ a ] . Since p p p takes infinitely many steps, condition (2)(b) requires us to consider the messages sent to p p p during the relevant time interval [ 0 , 1 / 2 ] [0,1/2] [ 0 , 1/2 ] ; the only step taken in this interval is S [ a ] S[a] S [ a ] . Since A \mathcal{A} A is loquacious, the only message sent to p p p in step S [ a ] S[a] S [ a ] is m m m ; by assumption, p p p receives m m m in step S [ b ] S[b] S [ b ] , with latency T [ b ] − T [ a ] = 3 / 4 ≤ 1 T[b] - T[a] = 3/4 \le1 T [ b ] − T [ a ] = 3/4 ≤ 1 .
Therefore, by Lemma C.7 , δ ( O ) ≤ k ≤ 1 \delta(O) \le k \le1 δ ( O ) ≤ k ≤ 1 , contradicting the fact that δ ( O ) = T [ c ] − T [ a ] = 3 / 2 \delta(O) = T[c] - T[a] = 3/2 δ ( O ) = T [ c ] − T [ a ] = 3/2 .
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 \mathcal{A} 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 \mathcal{A} A is loquacious. By Proposition 3.3 , A \mathcal{A} A satisfies ordering (CT1a). Since n ≥ 2 n \ge2 n ≥ 2 , let p p p and q q q be distinct processes in the system.
Construct a schedule prefix σ p \sigma_p σ p of A \mathcal{A} A consisting of two steps, both taken by process p p p : In the first step, p p p invokes an operation and broadcasts a message m p m_p m p ; in the second step, p p p receives m p m_p m p . By Lemma D.1 , this operation returns by the end of σ p \sigma_p σ p —let its return value be x p x_p x p . Construct σ q \sigma_q σ q symmetrically for process q q q , with return value x q x_q x q .
Note that σ p \sigma_p σ p contains only steps of p p p and σ q \sigma_q σ q contains only steps of q q q , so their concatenation σ p ∘ σ q \sigma_p \circ\sigma_q σ p ∘ σ q is also a schedule prefix of A \mathcal{A} A . Extend σ p ∘ σ q \sigma_p \circ\sigma_q σ p ∘ σ q to a schedule of A \mathcal{A} A ; in this schedule, condition (CT1a) implies x p < x q x_p < x_q x p < x q . Similarly, we can extend σ q ∘ σ p \sigma_q \circ\sigma_p σ q ∘ σ p to a schedule of A \mathcal{A} A , yielding x q < x p x_q < x_p x q < x p , a contradiction.