Revisiting Asynchronous Fault Tolerant Computation with Optimal Resilience

被引：11

作者：

Abraham, Ittai ^{[1
]}

Dolev, Danny ^{[2
]}

Stern, Gilad ^{[2
]}

机构：

[1] VMware Res, Herzliyya, Israel

[2] Hebrew Univ Jerusalem, Jerusalem, Israel

来源：

PROCEEDINGS OF THE 39TH SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, PODC 2020 | 2020年

关键词：

D O I：

10.1145/3382734.3405722

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 <= 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.

引用

页码：139 / 148

页数：10

共 9 条

[1] An Almost-Surely Terminating Polynomial Protocol for Asynchronous Byzantine Agreement with Optimal Resilience [J].

Abraham, Ittai ;

Dolev, Danny ;

Halpern, Joseph Y. .

PODC'08: PROCEEDINGS OF THE 27TH ANNUAL ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2008, :405-+

[2]

Abraham Ittai, P 25 ANN ACM S PRINC, P53

[3]

Ben-Or M., 1994, Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, P183, DOI 10.1145/197917.198088

[4]

Ben-Or M., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P52, DOI 10.1145/167088.167109

[5]

Ben-Or M., 1983, P 2 ANN ACM S PRINCI, P27, DOI DOI 10.1145/800221.806707

[6] ASYNCHRONOUS BYZANTINE AGREEMENT PROTOCOLS [J].

BRACHA, G .

INFORMATION AND COMPUTATION, 1987, 75 (02) :130-143

[7]

Canetti R., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P42, DOI 10.1145/167088.167105

[8]

Fischer M. J., 1985, PODC '85, P59, DOI [DOI 10.1145/323596.323602, 10.1145/323596.323602.]

[9] IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS [J].

FISCHER, MJ ;

LYNCH, NA ;

PATERSON, MS .

JOURNAL OF THE ACM, 1985, 32 (02) :374-382

← 1 →