CS Paper Radar

On Latency-Optimal Implementations of the Timestamp Object

Aurojit Panda, Scott Shenker, Sam Toueg, Wen Zhang

cs.DC ·submitted 2026-10-23 16:19 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Self-stabilising approximate clock synchronisation requires linear time

cs.DC ·2026-11-03 ·Joel Rybicki
theory similarity 0.69
Abstract

Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $Θ(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $Ω(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.

0.14

Byzantine-Tolerant Causal Unicast with Constant Message Space Overhead

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

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

0.03

Optimistic Reliable Broadcast in Three Steps

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

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

0.19

Byzantine Causal Reliable Broadcast with Constant Metadata Overhead

cs.DC cs.DS ·2026-09-29 ·Purv Patel, Ajay D. Kshemkalyani
similarity 0.63
Abstract

Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. Causal message ordering is important for many applications such as blockchain and social networking. Existing solutions for Byzantine Causal Reliable Broadcast (BCRB) have several drawbacks. Such protocols typically append vector clocks or dependency barriers to application messages, resulting in a metadata overhead that scales linearly with $n$, the number of processes in the system. In this paper, we propose the first optimal message overhead BCRB algorithm that guarantees safety. We do this by re-engineering Bracha's BRB algorithm with relatively small but critical modifications, and prove that our algorithm solves BCRB with optimal message metadata. The algorithm achieves constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ messages, resulting in $\mathcal{O}(n^2)$ communication word complexity. This is as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols. The algorithm tolerates $f < n/3$ Byzantine processes, which is the well-known optimal resilience bound, and uses four phases.

0.34

Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata

cs.DC cs.DS ·2026-09-21 ·Purv Patel, Ajay D. Kshemkalyani
theory similarity 0.62
Abstract

Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. In this paper, we address Byzantine Causal Reliable Broadcast (BCRB), which builds on BRB to enforce causal message ordering. We present a novel BCRB protocol that decouples causal ordering from the BRB layer, achieving constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ communication word complexity as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols; here $n$ is the number of processes. We present two variants of our protocol: a cryptographic version using a threshold encryption scheme and sequence gating, and its non-cryptographic version. In the cryptographic version, senders broadcast ciphertexts immediately, and decryption shares are piggybacked on out-of-band ACKs, preventing early decryption and front-running. In both versions, causal safety is achieved probabilistically. We evaluate the probability of causal safety violations using a random variable path analysis under independent exponential link delay distributions. We show that both variants satisfy liveness and the probability of weak safety violation is bounded by $\mathcal{O}(f^{-3}\cdot\ln^3 f)$, where $f$ is the upper bound on the number of Byzantine processes, and $f < n/3$ and $f=\mathcal{O}(n)$. Further, for the crypto version, we show that the probability of strong safety violation is bounded by $\mathcal{O}(f^{-1} \cdot \ln^2 f)$. We also show how to modify our two protocols to guarantee 100\% weak safety keeping $\mathcal{O}(1)$ message space overhead but with $\mathcal{O}(n^3)$ messages and $\mathcal{O}(n^3)$ communication word complexity.

0.29

Optimal Adaptive Multi-Valued Byzantine Agreement

cs.DC ·2026-08-18 ·Marc Dufay, Anton Paramonov, Roger Wattenhofer
similarity 0.60
Abstract

In Byzantine Agreement (BA), $n$ parties, out of which $t$ can be Byzantine, run a distributed protocol to agree on a common valid input. Traditionally, these protocols have a linear latency and quadratic message complexity, making them impractical at a large scale. In their recent work, Constantinescu, Dufay, Paramonov, and Wattenhofer consider the actual number of byzantine parties $f \leq t$ and work toward decoupling the dependency on $n$ and $t$ in the complexity. They obtain a BA protocol with $\tilde{\mathcal{O}}(n + t\cdot f)$ message complexity and $\tilde{\mathcal{O}}(f)$ round complexity. However, their results are strictly limited to agreement on a binary value. Using the framework given by their work along with novel techniques, we extend these results for BA on an $L$-bit value. With $κ$ being a security parameter, and with optimal resiliency ($t < n/2$ in the synchronous setting or $t < n/3$ otherwise), we obtain: - In synchrony, a deterministic protocol with $\mathcal{O}(n\cdot (L + f \cdot κ))$ bit complexity and $\mathcal{O}(f + \log n)$ round complexity. - In synchrony and partial synchrony, deterministic protocols with $\tilde{\mathcal{O}}(n \cdot κ+ t\cdot (L + f \cdot κ))$ bit complexity and $\mathcal{O}(f)$ round complexity. - In asynchrony, a protocol with $\tilde{\mathcal{O}}(n \cdot κ+ t\cdot(L + t \cdot κ))$ expected bit complexity and expected $\mathcal{O}(1)$ latency.

0.45

Asynchronous Verifiable and Complete Secret Sharing: From Design Patterns to System-Level Trade-offs

cs.CR ·2026-10-27 ·Joachim Bruneau-Queyreix, Martin Zivojinovic, Leo Mendiboure, Tom Claudel, Laurent Réveillère
similarity 0.59
Abstract

Modern secret sharing protocols promise robust secret sharing in fully asynchronous Byzantine systems, but their practical costs remain difficult to compare across papers, assumptions, and workloads. The difficulty is not merely experimental: protocols with similar asymptotic guarantees often place very different work on the critical path through their choices of dissemination, verification, batching, and recovery. This paper turns that fragmented research landscape into a corpus-backed designspace analysis and systems evaluation of asynchronous verifiable and complete secret sharing. We derive a design sieve, select seven representative protocols, and implement them in a common Rust framework. In our experiments on the Grid'5000 platform, we evaluate honest-dealer and faulty-dealer stress executions using latency, throughput, message count, bandwidth, and aggregate CPU-time. The results show that message complexity alone poorly predicts latency, that optimistic paths can be dominated by recovery cost, and that batching or packing helps only when verification stays off the critical path. These findings turn protocol-by-protocol comparisons into design-to-cost guidance for choosing, implementing, and extending asynchronous verifiable and complete sharing protocols.

0.28

Generalizing and accelerating consistency checking for non-transactional distributed storage systems

cs.DC ·2026-08-18 ·Kotikala Raghav, Aman Hassan, Brian Sajeev Kattikat, Patel Jay, RSRS Santhosh +1 more
similarity 0.59
Abstract

Linearizability checkers check if an operation history, observed by concurrent clients, is linearizable. They are used in testing distributed storage systems, and use the classic Wing-Gong (WG) linearizability checking algorithm. In this paper, we generalize the WG algorithm to make linearizability checkers more versatile: we can check other non-transactional consistency guarantees, like ordered sequential consistency provided by Zookeeper. Equipped with this generalization, we can also check for system-specific consistency guarantees that introduce additional ordering constraints over operations in a history, as per the system's specification. Our experiments with 8 distributed storage systems show that checking for system-specific consistency guarantees is easy to realize, reduces false negatives in testing, helps debug consistency violations, can be up to 370x faster, and can scale to more concurrent clients within the same checking time budget. We report 6 new consistency violation bugs, out of which 5 could not be found with existing consistency checkers.

0.38