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...
| Main Authors: | , |
|---|---|
| 其他作者: | |
| 格式: | 文件 |
| 语言: | en_US |
| 出版: |
Association for Computing Machinery (ACM)
2012
|
| 在线阅读: | http://hdl.handle.net/1721.1/72462 https://orcid.org/0000-0002-0024-5847 https://orcid.org/0000-0003-3381-0459 |
| _version_ | 1826208750851063808 |
|---|---|
| author | Haeupler, Bernhard Karger, David R. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Haeupler, Bernhard Karger, David R. |
| author_sort | Haeupler, Bernhard |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T14:11:35Z |
| format | Article |
| id | mit-1721.1/72462 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:11:35Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/724622022-10-01T19:42:24Z Faster information dissemination in dynamic networks via network coding Haeupler, Bernhard Karger, David R. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Karger, David R. Haeupler, Bernhard Karger, David R. 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. 2012-08-30T15:00:20Z 2012-08-30T15:00:20Z 2011-06 2011-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0719-2 http://hdl.handle.net/1721.1/72462 Bernhard Haeupler and David Karger. Faster information dissemination in dynamic networks via network coding. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (PODC '11). ACM, New York, NY, USA, 381-390. DOI=10.1145/1993806.1993885 http://doi.acm.org/10.1145/1993806.1993885 https://orcid.org/0000-0002-0024-5847 https://orcid.org/0000-0003-3381-0459 en_US http://dx.doi.org/10.1145/1993806.1993885 Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC '11) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Haeupler, Bernhard Karger, David R. Faster information dissemination in dynamic networks via network coding |
| title | Faster information dissemination in dynamic networks via network coding |
| title_full | Faster information dissemination in dynamic networks via network coding |
| title_fullStr | Faster information dissemination in dynamic networks via network coding |
| title_full_unstemmed | Faster information dissemination in dynamic networks via network coding |
| title_short | Faster information dissemination in dynamic networks via network coding |
| title_sort | faster information dissemination in dynamic networks via network coding |
| url | http://hdl.handle.net/1721.1/72462 https://orcid.org/0000-0002-0024-5847 https://orcid.org/0000-0003-3381-0459 |
| work_keys_str_mv | AT haeuplerbernhard fasterinformationdisseminationindynamicnetworksvianetworkcoding AT kargerdavidr fasterinformationdisseminationindynamicnetworksvianetworkcoding |