More Web Proxy on the site http://driver.im/

research-article

The Cost of Unknown Diameter in Dynamic Networks

Authors:

Irvan JahjaAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 5

Article No.: 31, Pages 1 - 34

https://doi.org/10.1145/3209665

Published: 29 August 2018 Publication History

Abstract

For dynamic networks with unknown diameter, we prove novel lower bounds on the time complexity of a range of basic distributed computing problems. Together with trivial upper bounds under dynamic networks with known diameter for these problems, our lower bounds show that the complexities of all these problems are sensitive to whether the diameter is known to the protocol beforehand: Not knowing the diameter increases the time complexities by a large poly(N) factor as compared to when the diameter is known, resulting in an exponential gap. Our lower bounds are obtained via communication complexity arguments and by reducing from the two-party DisjointnessCP problem. We further prove that sometimes this large poly(N) cost can be completely avoided if the protocol is given a good estimate on N. In other words, having such an estimate makes some problems no longer sensitive to unknown diameter.

References

[1]

Y. Afek and D. Hendler. 1995. On the complexity of global computation in the presence of link failures: The general case. Distrib. Comput. 8, 3 (1995), 115--120.

Digital Library

[2]

Chen Avin, Michal Koucky, and Zvi Lotker. 2008. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In ICALP.

Digital Library

[3]

Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, and Calvin Newport. 2011. Structuring unreliable radio networks. In PODC.

Digital Library

[4]

Binbin Chen, Haifeng Yu, Yuda Zhao, and Phillip B. Gibbons. 2014. The cost of fault tolerance in multi-party communication complexity. J. ACM 61, 3 (May 2014), Article 19, 64 pages.

Digital Library

[5]

Alejandro Cornejo, Seth Gilbert, and Calvin Newport. 2012. Aggregation in dynamic networks. In PODC.

Digital Library

[6]

A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. 2011. Distributed verification and hardness of distributed approximation. In STOC.

Digital Library

[7]

Andrew Drucker, Fabian Kuhn, and Rotem Oshman. 2012. The communication complexity of distributed task allocation. In PODC.

Digital Library

[8]

C. Dutta, G. Pandurangan, R. Rajaraman, Z. Sun, and E. Viola. 2013. On the complexity of information spreading in dynamic networks. In SODA.

Digital Library

[9]

Emanuele Fusco and Andrzej Pelc. 2012. Knowledge, level of symmetry, and time of leader election. In ESA.

Digital Library

[10]

Mohsen Ghaffari, Nancy Lynch, and Calvin Newport. 2013. The cost of radio network broadcast for different models of unreliable links. In PODC.

Digital Library

[11]

Oded Goldreich and Liuba Shrira. 1991. On the complexity of computation in the presence of link failures: The case of a ring. Distrib. Comput. 5, 3 (1991), 121--131.

Digital Library

[12]

Bernhard Haeupler and David Karger. 2011. Faster information dissemination in dynamic networks via network coding. In PODC.

Digital Library

[13]

B. Haeupler and F. Kuhn. 2012. Lower bounds on information dissemination in dynamic networks. In DISC.

Digital Library

[14]

I. Jahja, H. Yu, and Y. Zhao. 2017. Some lower bounds in dynamic networks with oblivious adversaries. In DISC.

[15]

Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea Richa. 2010. Broadcasting in unreliable radio networks. In PODC.

Digital Library

[16]

Fabian Kuhn, Nancy Lynch, and Rotem Oshman. 2010. Distributed computation in dynamic networks. In STOC.

Digital Library

[17]

Fabian Kuhn, Yoram Moses, and Rotem Oshman. 2011. Coordinated consensus in dynamic networks. In PODC.

Digital Library

[18]

Fabian Kuhn and Rotem Oshman. 2011. The complexity of data aggregation in directed networks. In DISC.

Digital Library

[19]

Fabian Kuhn and Rotem Oshman. 2011. Dynamic networks: Models and algorithms. SIGACT News 42, 1 (Mar. 2011), 82--96.

Digital Library

[20]

D. Mosk-Aoyama and D. Shah. 2008. Fast distributed algorithms for computing separable functions. IEEE Trans. Inf. Theory 54, 7 (2008), 2997--3007.

Digital Library

[21]

D. Peleg. 1987. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics.

Digital Library

[22]

H. Yu, Y. Zhao, and I. Jahja. 2016. The cost of unknown diameter in dynamic networks. In SPAA.

Digital Library

[23]

Y. Zhao, H. Yu, and B. Chen. 2016. Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions. Distrib. Comput. 29, 1 (Feb. 2016), 17--38.

Digital Library

Cited By

Jahja IYu H(2024)Sublinear Algorithms in T-Interval Dynamic NetworksAlgorithmica10.1007/s00453-024-01250-386:9(2959-2996)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01250-3
Hou RJahja ISun YWu JYu HAgrawal KLee I(2022)Achieving Sublinear Complexity under Constant T in T-interval Dynamic NetworksProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538571(131-141)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538571
Jahja IYu HHou R(2022)On the power of randomization in distributed algorithms in dynamic networks with adaptive adversariesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2021.09.004159(35-50)Online publication date: Jan-2022
https://doi.org/10.1016/j.jpdc.2021.09.004
Show More Cited By

Index Terms

The Cost of Unknown Diameter in Dynamic Networks
1. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

The Cost of Unknown Diameter in Dynamic Networks
SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures

For dynamic networks with unknown diameter, we prove novel lower bounds on the time complexity of a range of basic distributed computing problems. Together with trivial upper bounds under dynamic networks with known diameter for these problems, our ...
Some lower bounds in dynamic networks with oblivious adversaries
Abstract
This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel $Ω (d + poly (m))$ lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic ...
Property Testing Lower Bounds via Communication Complexity
Selected papers from the 26th Annual IEEE Conference on Computational Complexity (CCC 2011)

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 65, Issue 5

October 2018

299 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3274534

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2018 ACM.

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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 August 2018

Accepted: 01 April 2018

Revised: 01 October 2017

Received: 01 August 2016

Published in JACM Volume 65, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Singapore Ministry of Education Academic Research Fund Tier-2

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
241
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jahja IYu H(2024)Sublinear Algorithms in T-Interval Dynamic NetworksAlgorithmica10.1007/s00453-024-01250-386:9(2959-2996)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01250-3
Hou RJahja ISun YWu JYu HAgrawal KLee I(2022)Achieving Sublinear Complexity under Constant T in T-interval Dynamic NetworksProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538571(131-141)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538571
Jahja IYu HHou R(2022)On the power of randomization in distributed algorithms in dynamic networks with adaptive adversariesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2021.09.004159(35-50)Online publication date: Jan-2022
https://doi.org/10.1016/j.jpdc.2021.09.004
Jahja IYu HScheideler CSpear M(2020)Sublinear Algorithms in T-interval Dynamic NetworksProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400228(317-327)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400228
Jahja IYu HHou R(2020)On the Power of Randomization in Distributed Algorithms in Dynamic Networks with Adaptive AdversariesEuro-Par 2020: Parallel Processing10.1007/978-3-030-57675-2_24(376-391)Online publication date: 24-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-57675-2_24

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents