Type of publication: | Inproceedings |
Entered by: | |
Title | Causality, Influence, and Computation in Possibly Disconnected Synchronous Dynamic Networks |
Bibtex cite ID | RACTI-RU1-2012-26 |
Booktitle | 16th International Conference On Principles Of DIstributed Systems (OPODIS) |
Series | Lecture Notes in Computer Science |
Year published | 2012 |
Volume | 7702 |
Pages | 269-283 |
Publisher | Springer-Verlag Berlin Heidelberg |
Location | Rome, Italy |
URL | http://link.springer.com/chapter/10.1007%2F978-3-642-35476-2_19 |
DOI | 10.1007/978-3-642-35476-2_19 |
Keywords | dynamic graph,mobile computing,worst-case dynamicity,adversarial schedule,temporal connectivity,termination,counting,information dissemination,optimal protocol |
Abstract | In this work, we study the propagation of influence and computation in dynamic networks that are possibly disconnected at every instant. We focus on a synchronous message passing communication model with broadcast and bidirectional links. To allow for bounded end-to-end communication we propose a set of minimal temporal connectivity conditions that bound from the above the time it takes for information to make progress in the network. We show that even in dynamic networks that are disconnected at every instant information may spread as fast as in networks that are connected at every instant. Further, we investigate termination criteria when the nodes know some upper bound on each of the temporal connectivity conditions. We exploit our termination criteria to provide efficient protocols (optimal in some cases) that solve the fundamental counting and all-to-all token dissemination (or gossip) problems. Finally, we show that any protocol that is correct in instantaneous connectivity networks can be adapted to work in temporally connected networks. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments |
MCS-OPODIS12.pdf (main file) |
|
Publication ID | 975 |