CS Paper Radar

Consensus with Stochastic Broadcast

Pierre Fraigniaud, Boaz Patt-Shamir, Sergio Rajsbaum

cs.DC ·submitted 2026-08-27 16:38 UTC · v1

Abstract

We study binary consensus in the \emph{stochastic broadcast model}, which assumes $n\geq 2$ processes communicating synchronously by message broadcasts. At each round, every process broadcasts a message to all the other processes. Each broadcast succeeds independently with some probability $p\in[0,1]$. If a broadcast succeeds, all processes receive the message, and if it fails, no process receives the message. The sender does not know whether its broadcast was successful or not. In this model, consensus is not solvable; the objective is to design, for a given number of rounds $r$, consensus algorithms that terminate in $r$ rounds, minimizing the probability of error disagreement. This problem has been studied in depth for 2 processes [DISC 2025]. We extend the study to $n> 2$.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimistic Reliable Broadcast in Three Steps

cs.DC ·2026-10-04 ·Nikita Polyanskii
theory similarity 0.62
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

Contention Resolution Against an Adversarial Scheduler

cs.DS ·2026-11-06 ·Michael A. Bender, Martín Farach-Colton, Andrew Krapivin, Pritom Kundu, John Kuszmaul +3 more
theory similarity 0.59
Abstract · 15 pages

In the classical contention-resolution problem, a set of players share a broadcast channel, and a player succeeds in a given time step if it is the only player to broadcast during that step. Implicit in the classical problem is the assumption that every player is free to act on every step: once a player arrives, it participates until it succeeds. We study what happens when that assumption is removed. In our model, an adversarial \emph{scheduler} decides, on each step, which subset of the players gets scheduled to participate in the step. An unscheduled player simply sleeps through the step. We measure a protocol by its \emph{efficiency}: the number of players divided by the expected number of steps in which at least one player was active. Our first result says that, so long as the players are given access to a global clock and to shared randomness, they can achieve efficiency $Ω(1/\log n)$. The players are able to achieve this bound without requiring any channel feedback, and even if the adversarial scheduler is adaptive. We also give a matching lower bound of $O(1 / \log n)$, which holds even with channel feedback, and even for an oblivious scheduler. Our upper bounds all require the players to have access to a shared global clock and to shared randomness. Our final result says that this type of implicit shared state is necessary. If the players have neither a global clock nor shared randomness, then no protocol can achieve efficiency better than $O(\log n / n)$; and this holds even if the other aspects of the problem are designed to be as favorable for the players as possible (the channel gives ternary feedback and the adversary is oblivious).

0.26

Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics

cs.DC cs.DSmath.PR ·2026-10-29 ·Francesco d'Amore, Joel Rybicki, Nobutaka Shimizu, Takeharu Shiraga, Robin Vacus
theory similarity 0.59
Abstract

How does the number of sampled opinions affect the time required to reach consensus in distributed consensus dynamics? We study the synchronous $h$-Majority, in which every node independently samples $h$ nodes uniformly at random with replacement in each round and adopts a most frequent sampled opinion, breaking ties uniformly at random. We show that $h$-Majority achieves the nearly-optimal trade-off between the sample size and the consensus time, among a broad class of consensus dynamics. In particular, we prove the following results. For every sample size $h \ge 3$ and for every initial configuration, we prove that the process reaches consensus with high probability within $$\widetilde{O}\left(1+\min\left\{\frac{1}{\min\{h^2p_{\max},1\}},\frac{\sqrt{n}}{h}\right\}\right)$$ rounds, where $n$ is the number of nodes and $p_{\max}$ is the largest initial fraction of nodes supporting any single opinion. This is the first bound on the consensus time for $h$-Majority that holds for every $h\ge3$ and every initial configuration. When the initially most popular opinion has a sufficiently large lead over every other opinion, we show that all nodes adopt this opinion with high probability within $O(\log n/\min\{h^2p_{\max},1\})$ rounds. We establish a matching lower bound up to polylogarithmic factors for any fixed update rule that treats all opinions symmetrically and that selects either a sampled opinion or the node's current opinion.

0.49

Multivalued Consensus: General Adversaries Require More Communication

cs.DC cs.CRcs.IT ·2026-08-18 ·Mose Mizrahi, Roger Wattenhofer
theory similarity 0.59
Abstract · 33 pages, 1 figure, full version of a DISC 2026 paper

We study $n$-party fault-tolerant consensus against general (non-threshold) adversaries. We describe an infinite family $Z_\mathsf{proj}^{n,d}$ of $Q^d$-satisfying $n$-party adversary structures based on finite projective geometry which cause error-free $R$-round protocols for interactive consistency on $L$-bit inputs to require $Ω(Ln^{2+1/d})$ bits of expected communication. Likewise, $Z_\mathsf{proj}^{n,d}$ causes error-free byzantine agreement and broadcast to cost $Ω(Ln^{1+1/d})$ bits. In every case, the lower bound is $Ω(L_{\mathsf{out}} \cdot n^{1+1/d})$ bits, where $L_{\mathsf{out}}$ is the output length. The family $Z_\mathsf{proj}^{n,d}$ also causes reliable broadcast and byzantine agreement to cost $Ω(Ln^{1+1/d})$ bits of expected communication in asynchronous networks. Moreover, there exists a related family $Z_\mathsf{2\textsf-proj}^{n,d}$ of $Q^d$-satisfying adversary structures that make core set agreement cost $Ω(Ln^{2+1/d})$ bits. These asynchronous lower bounds hold against send-omission adversaries, even if the protocol uses cryptography. Their basis is that if a quorum of non-faulty parties agree on an output and terminate, then the messages they sent before terminating must suffice for the parties outside the quorum to also terminate with the same output. Surprisingly, if we do not require the parties to terminate (stop sending messages) after they output, then these bounds no longer hold. We show this by designing a non-terminating omission-tolerant reliable broadcast protocol that can for any parameter $δ> 1$ be tuned to cost $(1 + \frac{1}{δ- 1})Ln + O(δn^2\log(δn))$ bits, which is of independent interest. Lastly, we show how to get termination with $O(Ln^{1+1/d} + n^2\log n)$ bits (assuming the $Q^d$ condition), and thus prove our asynchronous lower bounds tight.

0.35

A Simple Phase-King Protocol with Predictions

cs.DC ·2026-11-08 ·Antonia Giannoulea, George Papadoulis, Nikos Leonardos, Aris Pagourtzis
similarity 0.58
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.

0.29

Beyond Leaderless: Randomized Consensus Against Mobile Crashes

cs.DC ·2026-10-31 ·Ittai Abraham, Kaya Alpturer, Pranav Garimidi, Joachim Neu, Tim Roughgarden +1 more
similarity 0.58
Abstract · 32 pages, 6 figures

Many consensus protocols fail to terminate under attack from an adversary that has the power to move between replicas and repeatedly crash one of them, even in synchrony. We present Multi-Leader Fixed-View Simplex (ML-FVS) to defend against such an adversary while keeping the simple structure and good-case latency of Simplex consensus. Our protocol extends fixed-view Simplex with multiple leaders, each of which may broadcast a proposal. At the voting deadline, each replica votes on the set of proposals it has seen so far. A hidden threshold beacon revealed after the votes gives a priority order on the multiple leaders, resolving each vote to its highest-priority proposal. Our model combines permanent adaptive Byzantine faults with mobile crashes. For a constant crash budget and $Δ$-delayed Byzantine corruption, we obtain $O(Δ)$ expected latency over repeated views whose leaders start honest. With immediate Byzantine corruptions, the protocol still achieves liveness. We also evaluate the protocol under random network delays and stochastic faults, finding that multiple leaders reduce view failures even when rational leaders delay their proposals to increase rewards.

0.19

Minimizing Commit Rules for DAG-based Atomic Broadcast

cs.DC ·2026-08-18 ·Petr Kuznetsov, Maxence Perion, Sara Tucci-Piergiovanni
hot direction similarity 0.57
Abstract · We have received external feedback that invalidates the results presented in the paper: a counterexample was found that breaks the safety of…

A popular class of Byzantine fault-tolerant atomic broadcast protocols rely on directed acyclic graphs (DAGs) that represent causal relations between broadcast messages. Each process applies a protocol-specific \emph{commit rule} on its local DAG to determine which vertices can be delivered in a total order. Intuitively, commit rules that impose fewer conditions on the DAG to order its vertices imply more efficient protocols, as the broadcast messages are delivered with lower latency. In this paper, we define commit rules on an uncertified round-based DAG construction, and introduce a sub-rule relation between them: a commit rule $cr_1$ is a sub-rule of a commit rule $cr_2$ if, for any DAG, the set of vertices committed by $cr_1$ contains all vertices committed by $cr_2$. We use the sub-rule relation to determine a minimal commit rule in an eventually synchronous model and a minimal commit rule in an asynchronous model, namely, two commit rules that require the least conditions on the DAG to safely commit any set of vertices in their respective models. To the best of our knowledge, no existing DAG-based atomic broadcast protocol relies on such minimal commit rules: we introduce \emph{Minnow}, a new protocol for DAG-based atomic broadcast, which can be instantiated in both eventually synchronous (S-Minnow) and asynchronous networks (A-Minnow).

0.24

An Optimal Gap-Majority Lemma for Bounded-Round Communication

cs.CC ·2026-10-15 ·Pachara Sawettamalya
similarity 0.56
Abstract

Recent work of Sawettamalya and Yu (FOCS 2026) initiated the study of \emph{gap-majority} composition in randomized communication. They showed that if computing a $\{\pm 1\}$-valued function $f$ in $r$ rounds requires $I$ bits of information, then distinguishing whether $\sum_{i=1}^n f(X_i,Y_i)$ is at least $0.01\sqrt{n}$ or at most $-0.01\sqrt{n}$ in $r$ rounds requires $n \cdot (I-O(\log n))$ bits of information. They also conjectured that the $O(\log n)$-additive ``loss'' can be further reduced to $O(1)$. In this note, we show that a minor adaptation of their approach, together with a more refined analysis, achieves the conjectured $O(1)$ loss, establishing a gap-majority lemma for bounded-round communication that is optimal up to constant factors.

0.25