Revisiting asynchronous fault tolerant computation with optimal resilience
| Autor: | Gilad Stern, Danny Dolev, Ittai Abraham |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Theoretical computer science Computer science Computer Networks and Communications TheoryofComputation_GENERAL Upper and lower bounds Theoretical Computer Science Null set Fault tolerant computation Computer Science - Distributed Parallel and Cluster Computing Computational Theory and Mathematics Asynchronous communication Hardware and Architecture Almost surely Verifiable secret sharing Distributed Parallel and Cluster Computing (cs.DC) Resilience (network) Protocol (object-oriented programming) |
| Zdroj: | PODC |
| ISSN: | 1432-0452 0178-2770 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |