Consensus with Stochastic Broadcast

The paper investigates binary consensus in the **stochastic broadcast model**, a synchronous communication setting with $n\ge 2$ processes. In each round, every process broadcasts a message to all other processes. Each broadcast independently succeeds with probability $p\in [0,1]$. If a broadcast succeeds, all processes receive the message; if it fails, no process receives it. Crucially, the sender does not learn whether its broadcast succeeded or failed.

Under these assumptions, deterministic consensus is **not solvable**: the uncertainty introduced by silent broadcast failures prevents processes from guaranteeing agreement. The authors therefore reframe the problem as an optimization task: for a fixed number of rounds $r$, design consensus algorithms that terminate in exactly $r$ rounds while minimizing the probability of error disagreement. Prior work [DISC 2025] studied this problem in depth for the special case of $n=2$ processes. This paper extends the study to the general case $n>2$.

The paper's main results are expected to include:

- **Optimal error probability characterization**: For any $n>2$, $p\in [0,1]$, and round budget $r$, the authors provide the minimum achievable disagreement probability, possibly as a closed-form expression or a computable recurrence.
- **Algorithm constructions**: Explicit $r$-round consensus algorithms that attain the optimal error probability, generalizing the two-process solutions from DISC 2025.
- **Lower bounds**: Proofs that no $r$-round algorithm can achieve a smaller error probability, establishing optimality.
- **Dependence on $n$ and $p$**: Analysis of how the optimal error scales with the number of processes and the broadcast success probability, including edge cases $p=0$, $p=1$, and

While the abstract does not list specific numerical results, the contribution is a rigorous extension of the consensus theory under stochastic broadcast to arbitrary process counts.