CS Paper Radar

Byzantine-Tolerant Causal Unicast with Constant Message Space Overhead

Purv Patel, Ajay D. Kshemkalyani

cs.DC cs.DS ·submitted 2026-10-05 20:38 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.80
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

Byzantine Causal Reliable Broadcast with Constant Metadata Overhead

cs.DC cs.DS ·2026-09-29 ·Purv Patel, Ajay D. Kshemkalyani
similarity 0.78
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 Reliable Broadcast with Causal Ordering

cs.DC ·2026-09-15 ·Mariarosaria Barbaraci, Christian Cachin
publishedtheory similarity 0.73
Abstract · 23 pages, 2 figures

Reliable and total-order broadcasts in the Byzantine-fault model are well studied, but adding causal order has received comparatively little attention, largely due to the complexity that stems from actions of Byzantine processes. Existing solutions almost exclusively build causal ordering on top of total-order broadcast. The combination of causal order with reliable broadcast remains rare, and the few solutions that exist adopt the classical definition of causality based on events occurring at individual processes (the happened-before relation). This definition is not sufficient to enforce causal ordering among broadcast messages: Byzantine processes can lie about, omit, and forge dependency information and thereby violate the causal order among self-reported events. Such manipulations remain indistinguishable from correct behavior to any single observer. We demonstrate the issue and its consequences via a front-running attack. To close this gap, we extend the notion of reliable broadcast to externalize local potential knowledge. We use this to formalize the first complete definition of causal message ordering in reliable broadcast under Byzantine faults. Unlike the classical formalization, this notion is grounded in the joint observations of a sufficiently large group of correct processes rather than a process's own view. Building on this definition, we characterize the properties of a Byzantine reliable broadcast channel that guarantees causal ordering. We then present an efficient protocol that satisfies these properties: it is resilient to the optimal number of $f < n/3$ Byzantine faults and for one instance that broadcasts payload message~$m$, it has bit complexity $O(n^2(|m| + λ+ n))$, where $λ$ denotes the maximal size of a unique (cryptographic) label for~$m$. Finally, we prove the protocol achieves Byzantine reliable broadcast with causal ordering.

0.28

On Latency-Optimal Implementations of the Timestamp Object

cs.DC ·2026-10-23 ·Aurojit Panda, Scott Shenker, Sam Toueg, Wen Zhang
similarity 0.68
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.

0.19

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

cs.DC ·2026-08-27 ·Austin T. Li, Daniel H. Lee, Lorenzo Alvisi, Natacha Crooks, Florian Suri-Payer
top venueposition similarity 0.67
Abstract

Byzantine fault-tolerant (BFT) systems are, in principle, an appealing foundation for transactional applications involving mutually distrustful participants. Yet their adoption has been hampered by two persistent stumbling blocks-performance and developer convenience-which are often in tension with one another. Recent systems show promising progress on both fronts by shifting to a client-centric architecture; clients execute transactions locally and concurrently, while the system resolves any data conflicts to maintain database serializability. We argue that, in its current form, this approach introduces a critical vulnerability: it leaves the integrity of the database exposed to Byzantine clients, which may issue malicious or incorrect transactions. We address this threat with Sintr, a framework that prevents Byzantine clients from compromising database integrity by executing rogue transactions. Sintr combines redundant execution to validate transaction outcomes with a flexible, heterogeneous policy framework for expressing an application's data-integrity requirements. We apply Sintr to harden several existing BFT database systems and find that it imposes only modest overheads-3%-16% in throughput and 3%-21% in latency.

0.30

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.65
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

Pangolin: Efficient DAG-based BFT State-Machine Replication with TEE-Accelerated Commitment

cs.DC ·2026-10-19 ·Paul Franke-Bergmann, Maya Kuhlmann, Alexander Heß, Marc Leinweber, Rüdiger Kapitza +3 more
similarity 0.65
Abstract · 28 pages

Currently many Byzantine fault-tolerant (BFT) protocols use directed acyclic graphs (DAGs) to let replicas propose blocks of requests in parallel for improved throughput. Yet, the existing DAG-based designs mainly consider the atomic-broadcast layer: They typically do not describe an efficient client interaction layer, their garbage collection is either unspecified or relies on trusted external storage, and the lowest-latency designs rely on timing assumptions that may be violated in geo-distributed deployments. In this paper, we propose the Pangolin protocol: It introduces a novel low-latency DAG-based atomic broadcast layer and completes it into an efficient state-machine replication (SMR) framework. To preserve system throughput, clients issue requests to a single replica and verify replies efficiently via compact execution proofs. Furthermore, Pangolin introduces a new garbage-collection scheme for DAGs which bounds memory usage even under full asynchrony. Pangolin leverages trusted execution environments to tolerate f Byzantine faults with only n >= 2f + 1 replicas and accelerates vertex commitments significantly: Broadcasting certified vertices requires only a single communication step, and commit rules are refined to commit both frequently and early without revealing the coin-elected anchor. This way, Pangolin overtakes the fastest partially synchronous DAG protocols while being live under asynchrony: In our evaluation, Pangolin achieves an average 1.27x (up to 1.52x) latency speedup over Mysticeti.

0.23

GUARDTs: Decentralized Access Control for Replicated Data Types

cs.PL cs.DC ·2026-11-05 ·Christian Kuessner, Ragnar Mogk, Julian Haas, Annette Bieniusa, Mira Mezini
similarity 0.65
Abstract · 24 pages, 10 figures

Replicated data types providing strong eventual consistency offer a principled foundation for developing decentralized software. Yet existing approaches to programming such data types leave access control unresolved: they either provide none at all, delegate it to a trusted coordinator, reintroducing the centralization they were designed to avoid, or tie it to specific data-type constructions, while typically assuming non-Byzantine replicas and static policies. We present GUARDTs: Guarded Unforgeable Algebraic Replicated Data Types, which embed fine-grained permissions directly into the application data model, operate without a central authority, support dynamic policy evolution, and tolerate Byzantine replicas. We formally prove that GUARDTs guarantee confidentiality, integrity, and availability and show empirically that their access control adds negligible overhead on top of the cost of Byzantine-resilient replication itself.

0.29