论文标题
具有最佳弹性的重新访问异步容忍度计算
Revisiting Asynchronous Fault Tolerant Computation with Optimal Resilience
论文作者
论文摘要
Fischer，Lynch和Paterson的著名结果是异步容忍计算的基本下限：任何1施加弹性的弹性异步协议协议协议都必须具有一定（可能是零）未终止的概率。 1994年，Ben-Or，Kelmer和Rabin出版了鲜为人知的较低限制的较低的下降，以对拜占庭对手的最佳韧性计算，以抗异步的耐受性计算：如果$ n \ le 4t $，则任何T-溶解的异步秘密分享协议一定具有某些不可用的概率。 我们的主要贡献是重新审视此下限，并提供严格，更一般的证据。我们的第二个贡献是展示如何避免这种下限。我们提供具有最佳弹性的协议，几乎可以肯定地终止了强大的共同硬币功能。使用这种新的原始性，我们几乎可以肯定地终止协议，具有具有新的公平有效性属性的异步拜占庭协议的最佳弹性。据我们所知，这是在信息理论环境中具有公平有效性的第一个异步拜占庭协议。
The celebrated result of Fischer, Lynch and Paterson is the fundamental lower bound for asynchronous fault tolerant computation: any 1-crash resilient asynchronous agreement protocol must have some (possibly measure zero) probability of not terminating. In 1994, Ben-Or, Kelmer and Rabin published a proof-sketch of a lesser known lower bound for asynchronous fault tolerant computation with optimal resilience against a Byzantine adversary: if $n\le 4t$ then any t-resilient asynchronous verifiable secret sharing protocol must have some non-zero probability of not terminating. Our main contribution is to revisit this lower bound and provide a rigorous and more general proof. Our second contribution is to show how to avoid this lower bound. We provide a protocol with optimal resilience that is almost surely terminating for a strong common coin functionality. Using this new primitive we provide an almost surely terminating protocol with optimal resilience for asynchronous Byzantine agreement that has a new fair validity property. To the best of our knowledge this is the first asynchronous Byzantine agreement with fair validity in the information theoretic setting.
