Probabilistic Indistinguishability and the Quality of Validity in Byzantine Agreement
Guy Goren, Yoram Moses, Alexander Spiegelman · 2022
This paper provides a formal framework for reasoning about randomized distributed algorithms. We generalize the notion of indistinguishability, the most useful tool in deterministic lower bounds, to apply to a probabilistic setting. We use the new notion to prove a lower bound on the probability at which it can be guaranteed that honest parties will not decide on a possibly bogus value. Moreover, we show that the bound is tight by providing a protocol that matches the bound. This completely characterizes the quality of decisions that protocols for a randomized multi-valued Consensus problem can guarantee in an asynchronous environment with Byzantine faults.