Search papers, labs, and topics across Lattice.
This paper extends the study of binary consensus in the stochastic broadcast model to scenarios involving more than two processes, addressing a previously unexplored area of consensus algorithms. The authors focus on designing algorithms that can achieve consensus within a fixed number of rounds while minimizing the probability of error disagreement, which is critical in environments with unreliable communication. Key results indicate that while consensus is unsolvable in this model, effective strategies can be developed to optimize performance as the number of processes increases.
Achieving consensus in a stochastic broadcast model with more than two processes reveals new strategies to minimize error in unreliable communication environments.
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$.
