TY - GEN
T1 - Iterative approximate consensus in the presence of Byzantine link failures
AU - Tseng, Lewis
AU - Vaidya, Nitin
N1 - Funding Information:
This research is supported in part by National Science Foundation award CNS 1329681. 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 - 2014
Y1 - 2014
N2 - This paper explores the problem of reaching approximate consensus in synchronous point-to-point networks, where each directed link of the underlying communication graph represents a communication channel between a pair of nodes. We adopt the transient Byzantine link failure model [15, 16], where an omniscient adversary controls a subset of the directed communication links, but the nodes are assumed to be fault-free. Recent work has addressed the problem of reaching approximate consensus in incomplete graphs with Byzantine nodes using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations [12, 21, 23, 24]. This paper addresses approximate consensus in the presence of Byzantine links. We extend our past work [21, 23] that provided exact characterization of graphs in which the iterative approximate consensus problem in the presence of Byzantine node failures is solvable. In particular, we prove a tight necessary and sufficient condition on the underlying communication graph for the existence of iterative approximate consensus algorithms under transient Byzantine link model [15, 16].
AB - This paper explores the problem of reaching approximate consensus in synchronous point-to-point networks, where each directed link of the underlying communication graph represents a communication channel between a pair of nodes. We adopt the transient Byzantine link failure model [15, 16], where an omniscient adversary controls a subset of the directed communication links, but the nodes are assumed to be fault-free. Recent work has addressed the problem of reaching approximate consensus in incomplete graphs with Byzantine nodes using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations [12, 21, 23, 24]. This paper addresses approximate consensus in the presence of Byzantine links. We extend our past work [21, 23] that provided exact characterization of graphs in which the iterative approximate consensus problem in the presence of Byzantine node failures is solvable. In particular, we prove a tight necessary and sufficient condition on the underlying communication graph for the existence of iterative approximate consensus algorithms under transient Byzantine link model [15, 16].
UR - http://www.scopus.com/inward/record.url?scp=84905906216&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84905906216&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-09581-3_7
DO - 10.1007/978-3-319-09581-3_7
M3 - Conference contribution
AN - SCOPUS:84905906216
SN - 9783319095806
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 84
EP - 98
BT - Networked Systems - Second International Conference, NETYS 2014, Revised Selected Papers
PB - Springer
T2 - 2nd International Conference on Networked Systems, NETYS 2014
Y2 - 15 May 2014 through 17 May 2014
ER -