[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1993806.1993885acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
research-article

Faster information dissemination in dynamic networks via network coding

Published: 06 June 2011 Publication History

Abstract

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(n2) 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 Ω(n2) 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/b2 * n2 rounds. For b = d = Θ(log n) our algorithms use O(n2/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 T2 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.

References

[1]
R. Ahlswede, N. Cai, S. Li, and R. Yeung. Network information flow. Transactions on Information Theory (TransInf), 46(4):1204--1216, 2000.
[2]
M. Borokhovich, C. Avin, and Z. Lotker. Tight bounds for algebraic gossip on graphs. In Proc. of the International Symp. on Information Theory (ISIT), pages 1758--1762, 2010.
[3]
K. C.-H. Chen Avin, Michael Borokhovich and Z. Lotker. Order Optimal Information Spreading Using Algebraic Gossip. In Proc. of the 40th Symp. on Principles of Distributed Computing (PODC), 2011.
[4]
S. Deb, M. Medard, and C. Choute. On random network coding based information dissemination. In Proc. of the International Symp. on Information Theory (ISIT), pages 278--282, 2005.
[5]
S. Deb, M. Medard, and C. Choute. Algebraic gossip: a network coding approach to optimal multiple rumor mongering. Transactions on Information Theory (TransInf), 52(6):2486 -- 2507, 2006.
[6]
B. Haeupler. Analyzing Network Coding Gossip Made Easy. In Proc. of the 43nd Symp. on Theory of Computing (STOC), 2011.
[7]
T. Ho and D. Lun. Network coding: an introduction. Cambridge Univ Pr, 2008.
[8]
T. Ho, M. Medard, R. Koetter, D. Karger, M. Effros, J. Shi, and B. Leong. A random linear network coding approach to multicast. Transactions on Information Theory (TransInf), 52(10):4413--4430, 2006.
[9]
F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. In Proc. of the 42nd Symp. on Theory of Computing (STOC), pages 557--570, 2010.
[10]
S. Li, R. Yeung, and N. Cai. Linear network coding. Transactions on Information Theory (TransInf), 49(2):371--381, 2003.
[11]
M. Luby. A simple parallel algorithm for the maximal independent set problem. In Proc. of the 17th Symp. on Theory of Computing (STOC), pages 1--10, 1985.
[12]
D. Mosk-Aoyama and D. Shah. Information dissemination via network coding. In Proc. of the International Symp. on Information Theory (ISIT), pages 1748--1752, 2006.
[13]
A. Panconesi and A. Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proc. of the 24th Symp. on Theory of Computing (STOC), pages 581--592, 1992.
[14]
R. Yeung. Information Theory and Network Coding. Springer Verlag, 2008.

Cited By

View all
  • (2024)Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic NetworksTheoretical Computer Science10.1016/j.tcs.2024.114904(114904)Online publication date: Oct-2024
  • (2024)Sublinear Algorithms in T-Interval Dynamic NetworksAlgorithmica10.1007/s00453-024-01250-386:9(2959-2996)Online publication date: 12-Jul-2024
  • (2022)Latency and Alphabet Size in the Context of Multicast Network CodingIEEE Transactions on Information Theory10.1109/TIT.2022.316039868:7(4289-4300)Online publication date: Jul-2022
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing
June 2011
406 pages
ISBN:9781450307192
DOI:10.1145/1993806
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. dynamic networks
  2. gossip
  3. multicast
  4. network coding

Qualifiers

  • Research-article

Conference

PODC '11
Sponsor:

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic NetworksTheoretical Computer Science10.1016/j.tcs.2024.114904(114904)Online publication date: Oct-2024
  • (2024)Sublinear Algorithms in T-Interval Dynamic NetworksAlgorithmica10.1007/s00453-024-01250-386:9(2959-2996)Online publication date: 12-Jul-2024
  • (2022)Latency and Alphabet Size in the Context of Multicast Network CodingIEEE Transactions on Information Theory10.1109/TIT.2022.316039868:7(4289-4300)Online publication date: Jul-2022
  • (2019)Local Distributed Algorithms in Highly Dynamic Networks2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00015(33-42)Online publication date: May-2019
  • (2019)The Communication Cost of Information Spreading in Dynamic Networks2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2019.00044(368-378)Online publication date: Jul-2019
  • (2018)The (T, L)-Path Model and Algorithms for Information Dissemination in Dynamic NetworksInformation10.3390/info90902129:9(212)Online publication date: 24-Aug-2018
  • (2018)The Cost of Unknown Diameter in Dynamic NetworksJournal of the ACM10.1145/320966565:5(1-34)Online publication date: 29-Aug-2018
  • (2018)Latency and Alphabet Size in the Context of Multicast Network Coding2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/ALLERTON.2018.8636026(212-218)Online publication date: Oct-2018
  • (2018)Time-communication impossibility results for distributed transactional memoryDistributed Computing10.1007/s00446-017-0318-y31:6(471-487)Online publication date: 1-Nov-2018
  • (2018)Simple multi-party set reconciliationDistributed Computing10.1007/s00446-017-0316-031:6(441-453)Online publication date: 1-Nov-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media