TY - GEN
T1 - Reaching approximate byzantine consensus with multi-hop communication
AU - Su, Lili
AU - Vaidya, Nitin
N1 - This research is supported in part by NSF awards 1329681 and 1421918 . 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 - 2015
Y1 - 2015
N2 - We address the problem of reaching approximate consensus in the presence of Byzantine faults in a synchronous system. We analyze iterative algorithms that maintain minimal state, and impose the constraint that in each iteration the nodes may only communicate with other nodes that are up to l hops away. For a given l, we prove a necessary and sufficient condition on the network structure for the existence of correct iterative algorithms that achieve approximate Byzantine consensus. We prove sufficiency of the condition by designing a correct algorithm, which uses a trim function based on a minimal messages cover property introduced in this paper. Our necessary and sufficient condition generalizes the tight condition identified in prior work for l = 1. For l ≥ l∗, where l∗ is the length of a longest cycle-free path in the given network, our condition is equivalent to the necessary and sufficient conditions for exact consensus in undirected and directed networks both.
AB - We address the problem of reaching approximate consensus in the presence of Byzantine faults in a synchronous system. We analyze iterative algorithms that maintain minimal state, and impose the constraint that in each iteration the nodes may only communicate with other nodes that are up to l hops away. For a given l, we prove a necessary and sufficient condition on the network structure for the existence of correct iterative algorithms that achieve approximate Byzantine consensus. We prove sufficiency of the condition by designing a correct algorithm, which uses a trim function based on a minimal messages cover property introduced in this paper. Our necessary and sufficient condition generalizes the tight condition identified in prior work for l = 1. For l ≥ l∗, where l∗ is the length of a longest cycle-free path in the given network, our condition is equivalent to the necessary and sufficient conditions for exact consensus in undirected and directed networks both.
KW - Approximate byzantine consensus
KW - Bounded length communication paths
KW - Incomplete network
KW - Iterative algorithm
KW - Synchronous system
UR - https://www.scopus.com/pages/publications/84943616965
UR - https://www.scopus.com/pages/publications/84943616965#tab=citedBy
U2 - 10.1007/978-3-319-21741-3_2
DO - 10.1007/978-3-319-21741-3_2
M3 - Conference contribution
AN - SCOPUS:84943616965
SN - 9783319217406
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 21
EP - 35
BT - Stabilization, Safety and Security of Distributed Systems - 17th International Symposium, SSS 2015, Proceedings
A2 - Pelc, Andrzej
A2 - Schwarzmann, Alexander A.
PB - Springer
T2 - 17th International Symposium on Stabilization, Safety and Security of Distributed Systems, SSS 2015
Y2 - 18 August 2015 through 21 August 2015
ER -