CS Paper Radar

A Simple Phase-King Protocol with Predictions

Antonia Giannoulea, George Papadoulis, Nikos Leonardos, Aris Pagourtzis

cs.DC ·submitted 2026-11-08 13:28 UTC · v1

Abstract

Inspired by recent work (Ben-David, Dzulfikar, Ellen, and Gilbert, $\textit{Byzantine Agreement with Predictions}$, PODC 2025) we study synchronous binary Byzantine Agreement in the learning-augmented setting, where each process receives predictions about which processes are honest or Byzantine. We present a deterministic Phase King protocol for the anauthenticated setting, combining early stopping with a specifically designed prediction-aware king selection procedure. For at most $t<n/3$ Byzantine processes, the protocol handles arbitrarily many prediction errors, improving upon the $O(n^{3/2})$ bound of Ben-David et al., and terminates within $O(P)$ communication rounds, where $P=1+\min\{\mathbf{B}/n,f\}$, $\mathbf{B}$ is the total number of incorrect prediction bits held by honest processes, and $f$ is the actual number of Byzantine processes. Our protocol uses $O(n^2P)$ messages and $O(n^2P\log n)$ bits, avoiding the initial cubic bit cost of exchanging complete prediction vectors. In comparison to very recent independent work (Dufay, Dzulfikar, and Gilbert, $\textit{Predictions Can Only Help! Communication Efficient Byzantine Agreement with Predictions}$, DISC 2026), which achieves the same error tolerance and round complexity but better communication bounds, our construction provides a much simpler Phase King approach that completely avoids involved preprocessing constructions, rendering it more practical, especially for achieving agreement in time-evolving networks. We believe that the novel prediction-aware king selection technique of our scheme is of independent interest and can find further applications in learning-augmented distributed consensus.

Closest papers

Nearest neighbours by meaning across the whole index.

Fast Quantum Byzantine Agreement with Nearly Linear Quantum Communication

cs.DS ·2026-11-03 ·Jan Olkowski
theory similarity 0.69
Abstract

We consider synchronous binary Byzantine agreement among $n$ processes connected by authenticated point-to-point classical and quantum channels. The adversary is computationally unbounded, sees all classical information, adaptively corrupts up to $t\le(1/3-\varepsilon)n$ processes, and may suppress messages sent by a process in the round in which it is corrupted. We give a quantum algorithm that solves Byzantine agreement in this model with probability $1$. It uses $O(\log^4 n)$ rounds, $O(n\log^8 n)$ qubits, and $O(n^2\log^8 n)$ classical bits in expectation, with constants depending on $\varepsilon$. This reduces the quantum communication of the protocol of Ben-Or and Hassidim (STOC~2005), which achieves $O(1)$ expected rounds but whose Byzantine coin implementation requires $Ω(n^4\log n)$ qubits and classical bits. We also extend the quadratic message lower bound of Abraham et al.\ (PODC~2019) to quantum channels, obtaining an $Ω(t^2)$ lower bound on worst-case expected total communication. For $t=Θ(n)$, the communication and round complexity of our algorithm are therefore optimal up to polylogarithmic factors.

0.24

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.67
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.66
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

Optimal Subcubic Byzantine Agreement with Plain PKI

cs.DC ·2026-11-04 ·Marc Dufay, Roger Wattenhofer
theory similarity 0.66
Abstract

We consider Byzantine Agreement (BA), where $n$ parties run a distributed protocol to agree on a common value, despite $t$ parties being byzantine. In the synchronous setting, a choice must be made between the weaker unauthenticated setting, which only allows $t < n/3$ byzantine parties, and the stronger authenticated setting that allows up to $t < n/2$ byzantine parties. For this latter setting, BA can be solved with optimal resiliency and optimal bit complexity. However, so far, all optimal solutions rely on the use of threshold signatures. This shows a gap compared to regular signatures, where only protocols with cubic complexity are known for optimal resiliency $t < n/2$. We wonder whether this cubic complexity is required without the use of threshold signatures and show that this is not the case. More specifically, given $κ$ an upper bound on the size of a hash or signature, we describe a deterministic protocol solving BA with bit complexity $\mathcal{O}(κ^{(\sqrt{13} - 1)/2} n^{(\sqrt{13} + 1)/2}) \approx \mathcal{O}(κ^{1.303}n^{2.303})$ while having optimal resiliency $t<n/2$ and round complexity $\mathcal{O}(n)$.

0.20

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

Vantage: Availability-Graded Broadcast for Signature-Free BFT

cs.DC cs.CR ·2026-08-17 ·Nikita Polyanskii
hot direction similarity 0.62
Abstract · 65 pages

Digital signatures make blocks and votes transferable evidence: one party can prove to another what a third party said. Authenticated channels convince only the direct receiver, so a proposer that references another party's block cannot prove to the voters who published it. High-throughput signature-free protocols therefore complete an availability vote or a reliable broadcast for every published data block before a proposer may reference it. We present Vantage, a partially synchronous Byzantine fault-tolerant protocol for $n \ge 3f+1$ parties, at most $f$ Byzantine, that uses only authenticated channels and collision-resistant hashing. Parties publish blocks on hash-linked author lanes; each view's proposer pairs a core manifest of lane prefixes that a quorum has acknowledged to it with an optimistic tip manifest of blocks it has just received. A new primitive, Availability-Graded Broadcast (AGB), makes the core irrevocable on a quorum of directly received acknowledgments while grading, rather than blocking on, the tip. A view that AGB leaves open or silent is decided by an on-demand instance of information-theoretic agreement. A block may thus be referenced in a proposal one message delay after publication, as in signed optimistic designs. Let $δ$ be the message delay after global stabilization (GST). With all parties correct, a proposal commits within $2δ$ of its send if all $n$ parties support it, and within $3δ$ on the quorum path, so a block published in time for the next proposal is sequenced $3δ$ to $4δ$ after publication. Safety holds under asynchrony; liveness holds after GST. On an emulated ten-region WAN with 100 parties, Vantage has the lowest p50 latency among compared signed and signature-free protocols at every offered load up to its peak, and sequences 250k 512-byte transactions per second at median end-to-end latency below 500 ms.

0.48

Faster Convergence of Multidimensional Approximate Agreement via Smallest Enclosing Balls

cs.DC ·2026-09-01 ·Darya Melnyk
theory similarity 0.60
Abstract

This work considers the multidimensional approximate agreement problem. In this problem, $n$ parties in a distributed system, up to $t$ of which may be corrupted by a Byzantine adversary, need to output vectors that are close to each other and that lie inside the convex hull of all non-corrupted input vectors. We assume that nodes communicate in a fully-connected authenticated network and analyze synchronous and asynchronous communication models. The focus of this work is on the contraction factor of approximate agreement protocols. The first multidimensional approximate agreement protocols had a contraction rate of $1-1/n$(VG, PODC'13) and $\sqrt[d]{1/2}$(MH, STOC'13). While a rate below $1$ is sufficient for convergence, it is not sufficient for practical applications. To date, the best known convergence rate of approximate agreement algorithms is $\sqrt{7/8}\approx0.935$ (FN, DISC'18), which is achieved through the MidExtremes protocol. This stands in contrast to the lower bound on the convergence rate in the $1$-dimensional setting, which is $1/2$. In this work, we propose BallMidpoint - a novel approximate agreement protocol with a contraction rate of $1/\sqrt{2}\approx 0.707$ in the synchronous and the asynchronous communication models. This algorithm satisfies the optimal resilience under convex validity. The presented contraction rate is achieved by choosing the midpoint of the smallest enclosing ball of the so-called local safe areas, and it is tight for the presented algorithms. Similar to (FN, DISC'18), our algorithm is coordinate-free, and the point inside the safe area can be computed efficiently. This work presents the first multidimensional approximate agreement protocol where the convergence rate is closer to the best known lower bound rather than the upper bound of $1$.

0.39