[ main page ] [ back ]

59/2012 : Agreement in Directed Dynamic Networks

RR Number
59/2012
Conference
Proceedings 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO'12), p. 73-84, Reykjavik, Iceland
Author(s)
Martin Biely, Peter Robinson, Ulrich Schmid
Abstract
We study distributed computation in synchronous dynamic networks 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 for consensus and other distributed computing problems like leader election, revealing that our algorithm is asymptotically optimal.
Bibtex
@InProceedings{BRS12:sirocco,
  author    = {Martin Biely and
               Peter Robinson and
               Ulrich Schmid},
  title     = {Agreement in Directed Dynamic Networks},
  booktitle = {Proceedings 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO'12)},
  year      = {2012},
  pages     = {73-84},
  ee        = {http://dx.doi.org/10.1007/978-3-642-31104-8_7},
  location = {Reykjavik, Iceland},
}
Download
Get paper.pdf - Adobe PDF-format, (302.8457 KB; posted at July 09 2013)

[ main page ] [ back ]