TY - GEN
T1 - Iterative approximate byzantine consensus under a generalized fault model
AU - Tseng, Lewis
AU - Vaidya, Nitin
N1 - Funding Information:
This research is supported in part by National Science Foundation award CNS 1059540 and Army Research Office grant W-911-NF-0710287. Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies or the U.S. government.
PY - 2013
Y1 - 2013
N2 - In this work, we consider a generalized fault model [7,9,5] that can be used to represent a wide range of failure scenarios, including correlated failures and non-uniform node reliabilities. Under the generalized fault model, we explore iterative approximate Byzantine consensus (IABC) algorithms [15] in arbitrary directed networks. We prove a tight necessary and sufficient condition on the underlying communication graph for the existence of IABC algorithms. We propose a new IABC algorithm for the generalized fault model, and present a transition matrix-based proof to show the correctness of the proposed algorithm. While transition matrices have been used to prove correctness of non-fault-tolerant consensus [6], this paper is the first to extend the technique to Byzantine fault-tolerant algorithms.
AB - In this work, we consider a generalized fault model [7,9,5] that can be used to represent a wide range of failure scenarios, including correlated failures and non-uniform node reliabilities. Under the generalized fault model, we explore iterative approximate Byzantine consensus (IABC) algorithms [15] in arbitrary directed networks. We prove a tight necessary and sufficient condition on the underlying communication graph for the existence of IABC algorithms. We propose a new IABC algorithm for the generalized fault model, and present a transition matrix-based proof to show the correctness of the proposed algorithm. While transition matrices have been used to prove correctness of non-fault-tolerant consensus [6], this paper is the first to extend the technique to Byzantine fault-tolerant algorithms.
KW - Generalized fault model
KW - Graph property
KW - Iterative consensus
UR - http://www.scopus.com/inward/record.url?scp=84893117771&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893117771&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-35668-1_6
DO - 10.1007/978-3-642-35668-1_6
M3 - Conference contribution
AN - SCOPUS:84893117771
SN - 9783642356674
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 72
EP - 86
BT - Distributed Computing and Networking - 14th International Conference, ICDCN 2013, Proceedings
T2 - 14th International Conference on Distributed Computing and Networking, ICDCN 2013
Y2 - 3 January 2013 through 6 January 2013
ER -