Complexity of Multi-Value Byzantine Agreement
作者： Guanfeng Liang , Nitin Vaidya
DOI: 10.21236/ADA555114
关键词:
摘要: Abstract : In this paper, we consider the problem of maximizing throughput Byzantine agreement, given that sum capacity all links in between nodes system is finite. agreement (BA) a classical distributed computing, with initial solutions presented seminal work Pease, Shostak and Lamport. Many variations on have been introduced past, some also called consensus. We will use following definition (Byzantine general problem): Consider network one node designated as sender or source (S), other peers. The goal for fault-free to agree value being sent by sender, despite possibility may be faulty. Our design algorithms can achieve optimal agreement.
harvard.edu
arxiv.org
sci-hub.st 参考文章(29)
Guanfeng Liang, Nitin Vaidya, Capacity of Byzantine Agreement: Tight Bound for the Four Node Network Defense Technical Information Center. ,(2010) , 10.21236/ADA555086
Michael Waidner, Birgit Pfitzmann, Information-Theoretic Pseudosignatures and Byzantine Agreement for t ≥ n/3 ,(2007)
Raymond W. Yeung, Ning Cai, NETWORK ERROR CORRECTION, PART II: LOWER BOUNDS ,(2006)
Tal Mizrahi, Yoram Moses, Continuous Consensus with Failures and Recoveries international symposium on distributed computing. pp. 408- 422 ,(2008) , 10.1007/978-3-540-87779-0_28
R. Friedman, A. Mostéfaoui, S. Rajsbaum, M. Raynal, Distributed Agreement and Its Relation with Error-Correcting Codes international symposium on distributed computing. pp. 63- 87 ,(2002) , 10.1007/3-540-36108-1_5
Tal Mizrahi, Yoram Moses, Continuous consensus via common knowledge theoretical aspects of rationality and knowledge. ,vol. 20, pp. 236- 252 ,(2005) , 10.1007/S00446-007-0049-6
M.N. Krohn, M.J. Freedman, D. Mazieres, On-the-fly verification of rateless erasure codes for efficient content distribution ieee symposium on security and privacy. pp. 226- 240 ,(2004) , 10.1109/SECPRI.2004.1301326
R. Koetter, M. Medard, An algebraic approach to network coding international symposium on information theory. pp. 104- ,(2001) , 10.1109/ISIT.2001.935967
Piotr Berman, Juan A. Garay, Kenneth J. Perry, Bit Optimal Distributed Consensus Computer Science. pp. 313- 321 ,(1992) , 10.1007/978-1-4615-3422-8_27
Brian A. Coan, Jennifer L. Welch, Modular construction of a Byzantine agreement protocol with optimal message bit complexity Information & Computation. ,vol. 97, pp. 61- 85 ,(1992) , 10.1016/0890-5401(92)90004-Y