TY - GEN
T1 - Agreement in directed dynamic networks
AU - Biely, Martin
AU - Robinson, Peter
AU - Schmid, Ulrich
N1 - Funding Information:
This work has been supported by the Austrian Science Foundation (FWF) project P20529 and S11405. Peter Robinson has also been supported in part by Nanyang Technological University grant M58110000 and Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082.
PY - 2012
Y1 - 2012
N2 - We study the fundamental problem of achieving consensus in a synchronous dynamic network, where an omniscient adversary controls the unidirectional communication links. Its behavior is modeled as a sequence of directed graphs representing the active (i.e. timely) communication links per round. We prove that consensus is impossible under some natural weak connectivity assumptions, and introduce vertex-stable root components as a-practical and not overly strong-means for circumventing this impossibility. Essentially, we assume that there is a short period of time during which an arbitrary part of the network remains strongly connected, while its interconnect topology keeps changing continuously. We present a consensus algorithm that works under this assumption, and prove its correctness. Our algorithm maintains a local estimate of the communication graphs, and applies techniques for detecting stable network properties and univalent system configurations. Our possibility results are complemented by several impossibility results and lower bounds, which reveal that our algorithm is asymptotically optimal.
AB - We study the fundamental problem of achieving consensus in a synchronous dynamic network, where an omniscient adversary controls the unidirectional communication links. Its behavior is modeled as a sequence of directed graphs representing the active (i.e. timely) communication links per round. We prove that consensus is impossible under some natural weak connectivity assumptions, and introduce vertex-stable root components as a-practical and not overly strong-means for circumventing this impossibility. Essentially, we assume that there is a short period of time during which an arbitrary part of the network remains strongly connected, while its interconnect topology keeps changing continuously. We present a consensus algorithm that works under this assumption, and prove its correctness. Our algorithm maintains a local estimate of the communication graphs, and applies techniques for detecting stable network properties and univalent system configurations. Our possibility results are complemented by several impossibility results and lower bounds, which reveal that our algorithm is asymptotically optimal.
UR - http://www.scopus.com/inward/record.url?scp=84864063620&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84864063620&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31104-8_7
DO - 10.1007/978-3-642-31104-8_7
M3 - Conference contribution
AN - SCOPUS:84864063620
SN - 9783642311031
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 73
EP - 84
BT - Structural Information and Communication Complexity - 19th International Colloquium, SIROCCO 2012, Proceedings
T2 - 19th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2012
Y2 - 30 June 2012 through 2 July 2012
ER -