betaFeedback

WorksComputer Science

On Latency-Optimal Implementations of the Timestamp Object

Abstract

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

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≥2n \ge2 is the number of processes in the system and 1≤f<n1 \le 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>4n > 4 and f=1f = 1. There, we narrow the optimal latency down to either two or three message delays.

Failure typeTS implementable iff# of failuresLower boundUpper boundTight?
Crashn>2fn > 2f (only if: Prop. 4.1)f≥2f \ge23 (Thm. 4.23)3 (Alg. 2)✓
f=1f = 12 (Prop. 4.22)2 (Alg. 1)✓
Byzantine with signaturesn>3fn > 3f (only if: Prop. 6.1)f≥2f \ge23 (Obs. 6.42)3 (Obs. 6.2)✓
f=1f = 12 (Obs. 6.41)2 (Alg. 3)✓
Byzantinen>3fn > 3f (only if: Obs. 7.1)f≥2f \ge23 (Obs. 7.14)✓
n=4, f=1n = 4,\ f = 13 (Thm. 7.15)3 (Alg. 4)✓
n>4, f=1n > 4,\ f = 12 (Obs. 7.13)

Table 1. Summary of results on implementing the timestamp object (TS), where n≥2n \ge2 is the number of processes in the system and 1≤f<n1 \le 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≥2n \ge2 processes connected pairwise by reliable asynchronous channels. At most ff processes may crash, where 1≤f<n1 \le 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} assigns to each process pp a deterministic automaton Ap\mathcal{A}_p. Each transition of Ap\mathcal{A}_p maps process pp’s current state, an optional operation invocation, and the received messages to a new state, outgoing messages, and any response to pp’s pending operation.

A schedule SS of A\mathcal{A} is an infinite sequence of steps, each taken according to A\mathcal{A}, in which at least n−fn-f processes take infinitely many steps. The processes that take infinitely many steps are correct in SS; 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} is a finite prefix of a schedule of A\mathcal{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) of A\mathcal{A} consists of a schedule SS of A\mathcal{A} and a non-decreasing, unbounded sequence TT of real numbers, where T[j]T[j] is the time of step S[j]S[j], such that:

  1. if a message sent in step S[j]S[j] is received in step S[k]S[k], then T[j]<T[k]T[j] < T[k]; and

  1. if steps S[j]S[j] and S[k]S[k] with j<kj < k are taken by the same process, then T[j]<T[k]T[j] < T[k].

A process is correct in RR if it is correct in SS, 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 RR.

Definition 2.2 (Message latency). In a run R=(S,T)R=(S,T), if a message mm is sent in step S[j]S[j] and received in step S[k]S[k], then its latency in RR is δR(m)≜T[k]−T[j]\delta_R(m) \triangleq 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), let OO be an operation invoked in step S[a]S[a].

  • The time interval of OO is

IR(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}
  • The latency of OO, denoted δR(O)\delta_{R}(O), is the length of IR(O)\mathcal{I}_{R}(O). In particular, δR(O)=∞\delta_{R}(O)=\infty if OO is incomplete.

  • A message is sent during OO if its send time lies in IR(O)\mathcal{I}_{R}(O).

Definition 2.5. In a run R=(S,T)R=(S,T), let LL be the set of processes that take infinitely many steps in SS, and let OO be an operation. We say that messages are timely during OO if every message sent during OO to a process in LL is timely.

All these notions are relative to a run, which we specify explicitly when needed. When the run RR is clear from context, we omit it from the notation, writing I(O)\mathcal{I}(O), δ(m)\delta(m), and δ(O)\delta(O).

Definition 2.6 (Worst-case message delay). The worst-case message delay of an algorithm A\mathcal{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\}.

If δ(A)\delta(\mathcal{A}) is finite, two simple but useful consequences follow:

Proposition 2.7. If δ(A)<∞\delta(\mathcal{A})<\infty, then A\mathcal{A} satisfies liveness: In every schedule of A\mathcal{A}, every operation invoked by a correct process eventually returns.

Proposition 2.8. If δ(A)<∞\delta(\mathcal{A})<\infty, then δ(A)=k\delta(\mathcal{A})=k for some nonnegative integer kk.

Accordingly, whenever we refer to a worst-case message delay of kk, we take kk 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: last∈Z≥0\mathit{last} \in\mathbb{Z}_{\ge0}, initially 0.

next():

choose any Δ∈Z≥1\Delta\in\mathbb{Z}_{\ge1}

last←last+Δ\mathit{last} \leftarrow\mathit{last}+\Delta

return last\mathit{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 HH 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' that (1) satisfies the sequential specification of TS and (2) preserves the precedence of operations in HH.

Definition 3.2 (TS implementation). Let AA be an algorithm whose next⁡()\operatorname{next}() operation returns positive integers. We say that AA implements TS in a system with crash failures if every schedule SS of AA, with corresponding history HH, satisfies the following conditions:

(CT1) Safety: HH is linearizable with respect to TS.

(CT2) Liveness: Every operation invoked by a correct process in SS eventually returns.

We call such an algorithm AA 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 AA be an algorithm whose next⁡()\operatorname{next}() operation returns positive integers. Then AA implements TS in a system with crash failures if and only if every schedule SS of AA, with corresponding history HH, satisfies the following conditions:

(CT1a) Ordering: If a complete operation O1O_1 precedes a complete operation O2O_2 in HH, then O1O_1 returns a smaller value than O2O_2.

(CT1b) Uniqueness: No two distinct complete operations in HH return the same value.

(CT2) Liveness: Every operation invoked by a correct process in SS 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 AA, (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 HH, (CT1) ⟹\Longrightarrow (CT1a) ∧\land (CT1b).

Proof. Suppose that HH satisfies (CT1). Since HH is linearizable with respect to TS, we can discard some incomplete operations from HH, append responses to the remaining incomplete operations, and arrange the resulting operations into a sequential history H′H' that (1) satisfies the sequential specification of TS and (2) preserves the precedence of operations in HH. Every complete operation in HH therefore appears in H′H' with the same return value. By the sequential specification of TS, each next⁡()\operatorname{next}() operation increases last⁡\operatorname{last} by some Δ≥1\Delta\ge1 and returns the new value of last⁡\operatorname{last}. Hence, the values returned by successive operations in H′H' are strictly increasing.

For (CT1a), suppose that a complete operation O1O_1 precedes a complete operation O2O_2 in HH. Since H′H' preserves the precedence of operations in HH, O1O_1 appears before O2O_2 in H′H' and therefore returns a smaller value. For (CT1b), let O1O_1 and O2O_2 be distinct complete operations in HH. Both appear in H′H' with the same return values as in HH. Since H′H' is sequential, one appears before the other; because return values strictly increase in H′H', they return distinct values.

Claim 3.5. For every history HH whose complete operations return positive integers, (CT1a) ∧\land (CT1b) ⟹\Longrightarrow (CT1).

Proof. Suppose that HH satisfies (CT1a) and (CT1b). Discard all incomplete operations from HH, and arrange the complete operations into a sequential history H′H' in increasing order of their return values.5 To show that HH is linearizable with respect to TS, it remains to show that H′H' satisfies the sequential specification of TS and preserves the precedence of operations in HH.

The return values in H′H' are positive integers and, by construction and (CT1b), strictly increasing. Thus, H′H' satisfies the sequential specification of TS.

Next, suppose that a complete operation O1O_1 precedes a complete operation O2O_2 in HH. By (CT1a), O1O_1 returns a smaller value than O2O_2. Since H′H' orders operations by increasing return value, O1O_1 appears before O2O_2 in H′H'. Hence, H′H' preserves the precedence of operations in HH.

Therefore, HH is linearizable with respect to TS.

Since the next() operation of A\mathcal{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≥2n \ge2 processes in the system, of which at most f≥1f \ge1 may crash.

Maximum Resilience

Proposition 4.1. In a system with crash failures, there exists an implementation of TS only if n>2fn > 2f.

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=1f = 1 and then for general ff.

Two-Delay Algorithm for f=1f=1

When f=1f = 1, TS can be implemented in two message delays.

Theorem 4.2. In a system with crash failures, if n>2fn > 2f and f=1f = 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 pip_i, its local clock xix_i is non-decreasing.

Proof. After initialization, only lines 13 and 20 assign to xix_i, and neither decreases it.

Claim 4.4. If an invocation of next() computes base timestamp tt on line 19, then at the time of return, at least two distinct processes pjp_j satisfy xj≥tx_j \ge t.

References

  1. [1]James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. “Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity”. In: J. ACM 62.1 (2015), 3:1–3:22. DOI: 10.1145/2732263. URL: https://doi.org/10.1145/2732263.
  2. [2]Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. “Sharing Memory Robustly in Message-Passing Systems”. In: J. ACM 42.1 (1995), pp. 124–142. DOI: 10.1145/200836.200869. URL: https://doi.org/10.1145/200836.200869.
  3. [3]Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. 2nd ed. Wiley series on parallel and distributed computing. Wiley, 2004. ISBN: 978-0-471-45324-6. DOI: 10.1002/0471478210. URL: https://doi.org/10.1002/0471478210.
  4. [4]Baruch Awerbuch. “Complexity of Network Synchronization”. In: J. ACM 32.4 (1985), pp. 804–823. DOI: 10.1145/4221.4227. URL: https://doi.org/10.1145/4221.4227.
  5. [5]João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud. “Asynchronous Latency and Fast Atomic Snapshot”. In: 39th International Symposium on Distributed Computing, DISC 2025, Berlin, Germany, October 27–31, 2025. Ed. by Dariusz R. Kowalski. Vol. 356. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 15:1–15:22. DOI: 10.4230/LIPIcs.DISC.2025.15. URL: https://doi.org/10.4230/LIPIcs.DISC.2025.15.
  6. [6]Shir Cohen and Idit Keidar. “Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer”. In: 35th International Symposium on Distributed Computing, DISC 2021, Freiburg, Germany (Virtual Conference), October 4–8, 2021. Ed. by Seth Gilbert. Vol. 209. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 18:1–18:18. DOI: 10.4230/LIPIcs.DISC.2021.18. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.18.
  7. [7]Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. “Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch&Increment, Stacks and Queues with Multiplicity”. In: Distributed Comput. 36.2 (2023), pp. 89–106. DOI: 10.1007/s00446-022-00440-y. URL: https://doi.org/10.1007/s00446-022-00440-y.
  8. [8]Partha Dutta, Rachid Guerraoui, Ron R. Levy, and Arindam Chakraborty. “How fast can a distributed atomic read be?” In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25–28, 2004. ACM, 2004, pp. 236–245. DOI: 10.1145/1011767.1011802. URL: https://doi.org/10.1145/1011767.1011802.
  9. [9]Faith Ellen, Panagiota Fatourou, and Eric Ruppert. “The Space Complexity of Unbounded Timestamps”. In: Distributed Computing, 21st International Symposium, DISC 2007, Lemesos, Cyprus, September 24–26, 2007, Proceedings. Ed. by Andrzej Pelc. Vol. 4731. Lecture Notes in Computer Science. Springer, 2007, pp. 223–237. DOI: 10.1007/978-3-540-75142-7_19. URL: https://doi.org/10.1007/978-3-540-75142-7_19.
  10. [10]Rachid Guerraoui and Eric Ruppert. “What Can Be Implemented Anonymously?” In: Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26–29, 2005, Proceedings. Ed. by Pierre Fraigniaud. Vol. 3724. Lecture Notes in Computer Science. Springer, 2005, pp. 244–259. DOI: 10.1007/11561927_19. URL: https://doi.org/10.1007/11561927_19.
  11. [11]Maryam Helmi, Lisa Higham, Eduardo Pacheco, and Philipp Woelfel. “The space complexity of long-lived and one-shot timestamp implementations”. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6–8, 2011. Ed. by Cyril Gavoille and Pierre Fraigniaud. ACM, 2011, pp. 139–148. DOI: 10.1145/1993806.1993826. URL: https://doi.org/10.1145/1993806.1993826.
  12. [13]Maurice P. Herlihy and Jeannette M. Wing. “Linearizability: A Correctness Condition for Concurrent Objects”. In: ACM Trans. Program. Lang. Syst. 12.3 (1990), pp. 463–492. DOI: 10.1145/78969.78972. URL: https://doi.org/10.1145/78969.78972.
  13. [14]H. T. Kung and John T. Robinson. “On Optimistic Methods for Concurrency Control”. In: ACM Trans. Database Syst. 6.2 (1981), pp. 213–226. DOI: 10.1145/319566.319567. URL: https://doi.org/10.1145/319566.319567.
  14. [15]Leslie Lamport. “Time, Clocks, and the Ordering of Events in a Distributed System”. In: Commun. ACM 21.7 (1978), pp. 558–565. DOI: 10.1145/359545.359563. URL: https://doi.org/10.1145/359545.359563.
  15. [16]N. A. Lynch and A. A. Shvartsman. “Robust Emulation of Shared Memory Using Dynamic Quorum-Acknowledged Broadcasts”. In: Digest of Papers: FTCS-27, The Twenty-Seventh Annual International Symposium on Fault-Tolerant Computing, Seattle, Washington, USA, June 24–27, 1997. IEEE Computer Society, 1997, pp. 272–281. DOI: 10.1109/FTCS.1997.614100. URL: https://doi.org/10.1109/FTCS.1997.614100.

Paper details

vlnc:W_22wr5x2t
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents