Revisiting Asynchronous Fault Tolerant Computation with Optimal\n Resilience

Abstract

The celebrated result of Fischer, Lynch and Paterson is the fundamental lower\nbound for asynchronous fault tolerant computation: any 1-crash resilient\nasynchronous agreement protocol must have some (possibly measure zero)\nprobability of not terminating. In 1994, Ben-Or, Kelmer and Rabin published a\nproof-sketch of a lesser known lower bound for asynchronous fault tolerant\ncomputation with optimal resilience against a Byzantine adversary: if $n\\le 4t$\nthen any t-resilient asynchronous verifiable secret sharing protocol must have\nsome non-zero probability of not terminating.\n Our main contribution is to revisit this lower bound and provide a rigorous\nand more general proof. Our second contribution is to show how to avoid this\nlower bound. We provide a protocol with optimal resilience that is almost\nsurely terminating for a strong common coin functionality. Using this new\nprimitive we provide an almost surely terminating protocol with optimal\nresilience for asynchronous Byzantine agreement that has a new fair validity\nproperty. To the best of our knowledge this is the first asynchronous Byzantine\nagreement with fair validity in the information theoretic setting.\n