A Simple and Efficient Randomized Byzantine Agreement Algorithm
关键词:
摘要: A new randomized Byzantine agreement algorithm is presented. This operates in a synchronous system of n processors, at most t which can fail. The reaches 0(t/log n) expected rounds and O(n2tf/log message bits independent the distribution processor failures. performance further improved to constant number O(n2) if failures assumed be uniform. In either event, improves on known lower bound for deterministic algorithms. Some other advantages are that it requires no cryptographic techniques, amount local computation small, random used per only one. It argued many practical applications agreement, this paper achieves superior performance.
sci-hub.se 参考文章(11)
Nancy A. Lynch, Michael J. Fischer, Robert Fowler, Simple and efficient Byzantine generals algorithm IEEE,New York, NY. ,(1982) , 10.21236/ADA113241
Michael O. Rabin, Randomized byzantine generals 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). pp. 403- 409 ,(1983) , 10.1109/SFCS.1983.48
Michael J. Fischer, Nancy A. Lynch, A lower bound for the time to assure interactive consistency Information Processing Letters. ,vol. 14, pp. 183- 186 ,(1981) , 10.1016/0020-0190(82)90033-3
Danny Dolev, H. Raymond Strong, Polynomial algorithms for multiple processor agreement Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. pp. 401- 407 ,(1982) , 10.1145/800070.802215
Gabriel Bracha, Sam Toueg, Resilient consensus protocols principles of distributed computing. pp. 12- 26 ,(1983) , 10.1145/800221.806706
Russell Turpin, Brian A. Coan, Extending binary Byzantine agreement to multivalued Byzantine agreement Information Processing Letters. ,vol. 18, pp. 73- 76 ,(1984) , 10.1016/0020-0190(84)90027-9
Danny Dolev, Ruediger Reischuk, H. Raymond Strong, 'Eventual' is earlier than 'immediate' 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). pp. 196- 203 ,(1982) , 10.1109/SFCS.1982.51
Adi Shamir, How to share a secret Communications of the ACM. ,vol. 22, pp. 612- 613 ,(1979) , 10.1145/359168.359176
Manuel Blum, Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits SIAM Journal on Computing. ,vol. 13, pp. 850- 864 ,(1984) , 10.1137/0213053
Joan B Plumstead, None, Inferring a sequence generated by a linear congruence 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). pp. 153- 159 ,(1982) , 10.1109/SFCS.1982.73