Source-linked AI summary
Consensus with Stochastic Broadcast
Pierre Fraigniaud, Boaz Patt-Shamir, Sergio Rajsbaum
TL;DR
The paper asks how to minimize disagreement probability for fixed-round binary consensus in the stochastic broadcast model beyond two processes. It develops probabilistic topological and graph-cut methods, identifies optimal or asymptotically optimal algorithms in several regimes, and gives sweep as a communication-optimal multi-round construction. Exact optimal error probabilities for all combinations of n, r, and p remain open.
Problem
The paper extends fixed-round binary consensus analysis to n ≥3, where exact consensus is unsolvable and fractional outputs from approximate agreement are invalid.
Method
The paper extends combinatorial-topology techniques using protocol complexes and a reduced Kripke graph whose weighted cuts represent consensus error.
Results
The paper proves one-round optimality in several p ranges and shows that repeating the two-round sweep algorithm r times uses rn broadcasts with error probability q^rn.
Takeaways & Limitations
Consensus algorithms must be selected by parameter regime: courteous is optimal for some low-p ranges, pref1 for high-p ranges, and one-round repetition is not generally multi-round optimal for n ≥3.
Takeaways & Limitations
Optimal error probabilities are proved only for some choices of n, r, and p; determining them for every parameter combination remains open.
Abstract
from arXiv · showhide
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$.
1 Introduction
The paper extends stochastic-broadcast consensus from two to more processes, using deterministic fixed-round algorithms that minimize worst-case disagreement probability. It identifies range-dependent one-round optima, proves lower bounds through probabilistic combinatorial topology, and develops a communication-optimal multi-round algorithm.
- 1 Introduction: Consensus is impossible to solve exactly in this model, so deterministic algorithms terminate after a fixed number of rounds while minimizing worst-case disagreement probability.Broadcasts succeed independently with probability p, fail with probability q = 1 −p, and senders do not learn whether their broadcasts succeeded.
- 1.1 Our Results: The one-round algorithms pref1 and courteous use different decision rules, with courteous favored for small p and pref1 for larger p.pref1 decides 1 unless no input 1 is known; courteous chooses the most frequent value in a process’s view and negates its own input on ties.
- 1.1 Our Results: For three processes, courteous is optimal for p ∈[0, 2/3], while pref1 is optimal for p ∈[2/3, 1].Their error probabilities are 2p^2q + q^3 and q, respectively, and coincide at p = 2/3.
- 1.1 Our Results: For n > 3, courteous is optimal for sufficiently small p, while pref1 is asymptotically optimal as p approaches 1.The paper establishes thresholds psmall and plarge; for n = 3, both equal 2/3.
- 1.1 Our Results: Repeating an optimal one-round algorithm is not optimal for n ≥3, but repeating the two-round sweep algorithm r times uses rn broadcasts and has error probability q^rn.This contrasts with two processes, where repeating an optimal one-round algorithm remains optimal.
- 1.2 Our Techniques: The analysis represents executions with protocol complexes and a reduced Kripke graph, converting error minimization into weighted cut problems.The reduced graph’s hypercube structure supports geometric analysis, while protocol-complex cuts represent disagreement executions.
2 Model and Preliminaries
The paper studies deterministic fixed-round binary consensus under stochastic broadcasts, optimizing worst-case disagreement probability despite unsolvable consensus. Broadcasts independently succeed with probability p, and failures are globally invisible to the sender.
- Stochastic broadcast model: Each synchronous round gives every process an independent broadcast that either reaches all other processes or reaches none.The success probability is p and the failure probability is q = 1 −p.
- Stochastic broadcast model: Senders do not immediately know whether their broadcasts were received, although later messages may reveal delivery information.A received broadcast certifies delivery to all processes, while a missing broadcast indicates that none received it.
- Consensus objective: The paper considers deterministic one-shot algorithms that execute a prescribed number of rounds before processes decide binary outputs.Randomness comes from message delivery rather than algorithmic randomization.
- Consensus objective: Consensus validity is enforced, while the objective is minimizing agreement errors on the worst-case input vector.Error probability is computed over stochastic executions for each fixed input assignment.
- Execution probabilities: For one round, an execution with k delivered messages has probability p^kq^(n−k), including all-message loss with probability q^n.These execution probabilities permit exhaustive calculation of each algorithm’s error probability.
3 Algorithms for Consensus: courteous and pref
The section introduces two one-round algorithms: pref1 favors deciding 1, while courteous follows the observed majority and reverses its own input on ties. Their relative performance depends on the broadcast success probability.
- Pref algorithms: Pref1 decides 1 unless a process knows of no input 1, and its worst-case error probability is q.For pref0, failure on an input with d zeros occurs when all d zero broadcasts fail, maximized at d = 1.
- Courteous: Courteous chooses the more frequent value in its view and negates its own input when the known counts tie.Its behavior extends to any number n of processes.
- Courteous: A strict majority among successfully delivered messages makes courteous reach agreement on that majority value.Agreement is therefore guaranteed whenever the delivered 0- and 1-messages are unequal.
- Courteous: If the number of delivered messages is odd, courteous reaches agreement.Its failures arise when successfully transmitted 0- and 1-values are equally numerous.
- General n: For general n, the one-round error probability of courteous is analyzed as a degree-n polynomial in p, with distinct behavior for odd and even n.Figure 6 presents the corresponding curves for small n.
4 Lower Bound for 1-Round Consensus in 3-Process Systems
The paper reduces one-round consensus design to weighted edge colorings of a reduced Kripke graph, enabling lower bounds. For three processes, this proves that courteous and pref1 are optimal in complementary probability ranges.
- Graph characterization: A structural theorem establishes a one-to-one correspondence between one-round consensus algorithms and 2-edge-colorings of the reduced Kripke graph.This correspondence supports the lower-bound analysis while preserving relevant algorithm-design information.
- Reduced Kripke graph: The reduced Kripke graph represents one-round configurations using vertices in {−1, 0, 1}^n and weights determined by broadcast delivery probabilities.A point with ||v|| successful transmissions has weight p^||v||q^(n−||v||).
- Graph characterization: The optimal one-round error probability equals the minimum, over valid edge-colorings, of the maximum weighted cut probability over input assignments.The graph formulation turns algorithm optimization into a combinatorial minimax problem.
- Lower bounds: Every nontrivial input includes the center vertex in the relevant cut, so no consensus algorithm can achieve error probability below q^n.This lower bound holds for every p ∈[0, 1].
- Three-process lower bound: For three processes and p ≤1/3, every one-round algorithm has error at least 2p^2q + q^3, matching courteous.The bound applies to every nontrivial input, not only the worst-case input.
5 Upper and Lower Bounds for n ≥3 Processes
For n ≥3, the paper establishes single-round optimality regimes for courteous and pref1, and develops sweep for multi-round consensus with optimal transmission efficiency. It also proves lower bounds using probabilistic topology and bivalence arguments.
- Multi-round algorithms: Repeating an optimal 1-round algorithm is not optimal for n ≥3, unlike the two-process case.
- Multi-round algorithms: For every n and r, repeating sweep r times uses at most rn broadcasts and has error probability q^rn, where q = 1 − p.
- Multi-round algorithms: The sweep error probability q^rn is optimal among algorithms using rn transmissions, and is at least as good as any algorithm using half as many rounds.
- Single-round algorithms: 1-round optimality requires different algorithms across broadcast-success probabilities: courteous performs better for small p, whereas pref1 performs better for larger p.
6 Conclusion and Open Problems
The paper characterizes consensus error probabilities for selected parameter settings and reduces the optimization problem to weighted cuts in combinatorial structures. It leaves optimal error probabilities unresolved for general rounds, process counts, and broadcast-success probabilities, while identifying extensions to other agreement problems and communication models.
- Open problems: Optimality is proved only for some combinations of rounds, process counts, and broadcast-success probabilities.The general determination of optimal error probability remains open.
- Structural characterization: Consensus error minimization reduces to a minimum-weight edge cut in simplicial complexes or a minimum-weight vertex cut in related hypercubic structures.
- Open problems: Set agreement is identified as an important extension because its error probability is not characterized by minimum-weight cuts of simplicial complexes.
- Communication models: Stochastic unicast and undirected-channel variants have been studied, but not for consensus.
- Significance: The paper suggests that its pleasing structural results may inform related problems and randomized distributed computation more broadly.
A The Protocol Complex of the Stochastic Broadcast Model
The protocol-complex framework connects topological and epistemic analyses of stochastic broadcast. For three processes with binary inputs, the input complex is represented geometrically as a pseudo-sphere.
- Framework: The appendix connects protocol-complex topology with knowledge structures represented by the Kripke graph.
- Protocol complex: A protocol-complex vertex is a process name paired with its one-round local state, and compatible process views form a simplex.
- Communication model: Full-information algorithms can be assumed without loss of generality; in one round, each process sends its name and input.
- Input complex: For binary inputs, the zero-round input complex consists of all input vectors in {0,1}^n and is the pseudo-sphere Ψ([n], {0,1}).For n = 3, Figure 14 gives a geometric representation.
A.1 The Protocol Complex after One Round
After one round, each process records which broadcasts it received, producing local states encoded over {0,1,⋆}. The protocol complex enumerates globally compatible states and their stochastic delivery probabilities.
- Local states: A one-round local state is encoded as a vector in {0,1,⋆}^n, where ⋆ denotes a message not received from a process.
- Compatibility: Compatibility requires processes to agree on whether each sender’s broadcast was received, and received values must match the sender’s input.
- Protocol complex: For a fixed input configuration with n processes, the subcomplex has 2^n facets corresponding one-to-one with broadcast delivery patterns.
- Protocol complex: The full protocol complex has 2^n · 2^n facets, indexed by binary input configurations and delivery patterns.
- Stochastic weighting: A delivery pattern with d successful broadcasts has facet probability p^d q^(n−d), where q = 1 − p.
A.2 Algorithms as Simplicial Maps
Consensus algorithms are represented as simplicial maps from protocol-complex states to the binary output complex. Correctness requires both legal simplicial images and agreement with the task specification.
- Algorithm representation: An r-round algorithm maps protocol-complex vertices to output-complex vertices according to processes’ decisions from their views.
- Correctness conditions: For consensus, the output complex has two uniform facets, and correctness requires the map to be simplicial and task-specification compliant.
A.3 Minimizing the Error Probability
The paper formulates one-round consensus as minimizing an algorithm’s error probability over inputs while enforcing validity. Extending this formulation to multiple rounds is already difficult, even for one round.
- Error minimization: The objective is to minimize the error probability of an algorithm f over all input facets.The stochastic delivery pattern makes one-round outputs random even when each process applies a deterministic function to its local state.
- Validity: Validity restricts admissible decision functions to those mapping every all-b-or-unknown local state to b.The paper denotes this set of validity-preserving functions by Fval.
- Optimization scope: The same optimization can be formulated for r-round algorithms, but it is already difficult to handle for r = 1.The topological approach is used to obtain observations that help solve the one-round minimization problem by another route.
A.4 The Connected Components of the Protocol Complexes
The protocol complex is decomposed by delivery patterns into connected components whose structure depends on the number of successful broadcasts. These components intersect in tightly constrained ways across distinct patterns.
- Delivery-pattern subcomplexes: For a fixed delivery pattern ϕ, P(ϕ) contains exactly the protocol facets sharing that pattern.It is the subcomplex induced by facets of the form (x, ϕ).
- Connectivity extremes: When all broadcasts succeed, distinct input facets in P(⊤n) have no vertices in common, whereas P(⊥n) is path-connected.In P(⊥n), every two facets intersect except complementary input vectors, and the complex still has one path-connected component.
- Component structure: If ϕ contains d successful-broadcast entries, P(ϕ) has 2^d path-connected components, each containing 2^(n−d) facets.Each component’s common intersection is a simplex of cardinality d.
- Inter-pattern intersections: Components from distinct delivery patterns intersect in at most one vertex, and every protocol-complex vertex belongs to exactly two such component intersections.These intersection constraints are stated as the two properties of Lemma 19.
- Intersection proof: A delivery-pattern pair differing in more than one process cannot yield intersecting components, while a one-entry difference can share a vertex when that process cannot distinguish the patterns.The proof attributes the distinction to other processes’ received messages and the sender’s uncertainty about its own delivery.
A.5 The Intersection Graph of the Protocol Complex
Lemma 19 motivates replacing the protocol complex with an intersection graph whose vertices are delivery-pattern components. The optimization then becomes an edge-coloring problem subject to graph-structural constraints.
- Graph construction: The intersection graph GP has one vertex for each path-connected component of P(ϕ).Two distinct component-vertices are adjacent exactly when the corresponding components intersect.
- Optimization reformulation: The remaining analysis must characterize GP and translate the original error minimization into edge-coloring properties.These are identified as the two central structural and optimization tasks.
- Graph simplification: Lemma 19 also permits merging protocol-complex vertices with the same delivery pattern when a process cannot distinguish the represented configurations.This yields a simplified variant of the Kripke graph.