Lower bounds and impossibility results in distributed computing are both intellectually challenging and practically important. Hundreds if not thousands of proofs appear in the literature, but surprisingly, the vast majority of them apply to deterministic algorithms only. Probabilistic protocols have been around for at least four decades and are receiving a lot of attention with the emergence of blockchain systems. Nonetheless, we are aware of only a handful of randomized lower bounds. In this paper we provide 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 apply this framework to prove a result of independent interest. Namely, we completely characterize the quality of decisions that protocols for a randomized multi-valued Consensus problem can guarantee in an asynchronous environment with Byzantine faults. 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. Finally, we show that the bound is tight by providing a protocol that matches it.
翻译:在分布式计算中,下限和不可能的结果在智力上具有挑战性,而且实际上也很重要。在文献中出现了数百个甚至数千个证据,但令人惊讶的是,绝大多数证据只适用于确定性算法。概率协议已经存在了至少40年,并且随着块链系统的出现,正在受到大量关注。然而,我们只意识到少数随机的下限。在本文中,我们为随机分布式计算法的推理提供了一个正式框架。我们普遍采用了不可分性的概念,这是确定性下限中最有用的工具,可以适用于概率性环境。我们应用这个框架来证明一种独立利益的结果。也就是说,我们完全确定随机化多价共识问题协议在与拜占廷断层的不连贯环境中可以保证的协议的质量。我们使用这个新概念来证明一种较低的约束,即可以保证诚实的各方不会就可能的虚假价值作出决定。最后,我们证明,我们通过提供一项能够与之匹配的协议,这个约束是紧凑紧的。