Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2012-04-03
Computer Science
Distributed, Parallel, and Cluster Computing
A preliminary version of this paper appears in SIROCCO 2012
Scientific paper
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 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.
Biely Martin
Robinson Peter
Schmid Ulrich
No associations
LandOfFree
Agreement in Directed Dynamic Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Agreement in Directed Dynamic Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Agreement in Directed Dynamic Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-354840