Faster information dissemination in dynamic networks via network coding
We use network coding to improve the speed of distributed computation in the dynamic network model of Kuhn, Lynch and Oshman [STOC '10]. In this model an adversary adaptively chooses a new network topology in every round, making even basic distributed computations challenging. Kuhn et al. sh...
| Principais autores: | , |
|---|---|
| Outros Autores: | |
| Formato: | Artigo |
| Idioma: | en_US |
| Publicado em: |
Association for Computing Machinery (ACM)
2012
|
| Acesso em linha: | http://hdl.handle.net/1721.1/72462 https://orcid.org/0000-0002-0024-5847 https://orcid.org/0000-0003-3381-0459 |
| Resumo: | We use network coding to improve the speed of distributed computation in the dynamic network model of Kuhn, Lynch and Oshman [STOC '10]. In this model an adversary adaptively chooses a new network topology in every round, making even basic distributed computations challenging.
Kuhn et al. show that n nodes, each starting with a d-bit token, can broadcast them to all nodes in time O(n[superscript 2]) using b-bit messages, where b > d + log n. Their algorithms take the natural approach of token forwarding: in every round each node broadcasts some particular token it knows. They prove matching Ω(n[superscript 2]) lower bounds for a natural class of token forwarding algorithms and an Ω(n log n) lower bound that applies to all token-forwarding algorithms.
We use network coding, transmitting random linear combinations of tokens, to break both lower bounds. Our algorithm's performance is quadratic in the message size b, broadcasting the n tokens in roughly d/b[superscript 2] * n[superscript 2] rounds. For b = d = Θ(log n) our algorithms use O(n[superscript 2]/log n) rounds, breaking the first lower bound, while for larger message sizes we obtain linear-time algorithms. We also consider networks that change only every T rounds, and achieve an additional factor T[superscript 2] speedup. This contrasts with related lower and upper bounds of Kuhn et al. implying that for natural token-forwarding algorithms a speedup of T, but not more, can be obtained. Lastly, we give a general way to derandomize random linear network coding, that also leads to new deterministic information dissemination algorithms. |
|---|