论文标题
拜占庭一致性中的概率不可区分性和有效性的质量
Probabilistic Indistinguishability and the Quality of Validity in Byzantine Agreement
论文作者
论文摘要
分布式计算中的下限和不可能的结果在智力上具有挑战性且实际上很重要。文献中出现了数百种证据，但令人惊讶的是，其中绝大多数仅适用于确定性算法。概率方案至少已经存在了四十年，并且随着区块链系统的出现，人们引起了很多关注。但是，我们只知道少数几个随机下限。 在本文中，我们为推理随机分布式算法提供了正式的框架。我们概括了不可区分性的概念，这是确定性下限中最有用的工具，用于应用于概率设置。我们应用此框架来证明独立利益的结果。也就是说，我们完全表征了为随机多价共识问题协议的决策质量，可以在异步环境中保证具有拜占庭断层的异步环境。我们使用新的概念来证明较低的限制，即可以确保诚实当事方不会决定可能的虚假价值的概率。最后，我们通过提供与之匹配的协议来证明界限紧密。
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.
