Document Open Access Logo

Some Lower Bounds in Dynamic Networks with Oblivious Adversaries

Authors Irvan Jahja, Haifeng Yu, Yuda Zhao

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.29.pdf
  • Filesize: 0.68 MB
  • 16 pages

Document Identifiers

Author Details

Irvan Jahja
Haifeng Yu
Yuda Zhao

Cite As Get BibTex

Irvan Jahja, Haifeng Yu, and Yuda Zhao. Some Lower Bounds in Dynamic Networks with Oblivious Adversaries. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.29

Abstract

This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel Omega(d + poly(m)) lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic network and m is the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial Omega(d) lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a poly(m) term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider the communication complexity with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain "non-critical" information about the problem instance that they are solving.

Subject Classification

Keywords
  • dynamic networks
  • oblivious adversary
  • adaptive adversary
  • lower bounds
  • communication complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Augustine, C. Avin, M. Liaee, G. Pandurangan, and R. Rajaraman. Information spreading in dynamic networks under oblivious adversaries. In DISC, 2016. Google Scholar
  2. J. Augustine, T. Kulkarni, P. Nakhe, and P. Robinson. Robust leader election in a fast-changing world. In Workshop on Foundations of Mobile Computing, 2013. Google Scholar
  3. J. Augustine, G. Pandurangan, and P. Robinson. Fast byzantine leader election in dynamic networks. In DISC, October 2015. Google Scholar
  4. John Augustine, Gopal Pandurangan, and Peter Robinson. Fast byzantine agreement in dynamic networks. In PODC, July 2013. Google Scholar
  5. Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702-732, June 2004. Google Scholar
  6. Q. Bramas, T. Masuzawa, and S. Tixeuil. Distributed online data aggregation in dynamic graphs. In ICDCS, 2016. Google Scholar
  7. M. Braverman. Interactive information complexity. SIAM Journal on Computing, 44(6):1698-1739, 2015. Google Scholar
  8. K. Censor-Hillel, E. Haramaty, and Z. Karnin. Optimal dynamic distributed MIS. In PODC, 2016. Google Scholar
  9. Binbin Chen, Haifeng Yu, Yuda Zhao, and Phillip B. Gibbons. The cost of fault tolerance in multi-party communication complexity. Journal of the ACM, 61(3), May 2014. Google Scholar
  10. Alejandro Cornejo, Seth Gilbert, and Calvin Newport. Aggregation in dynamic networks. In PODC, July 2012. Google Scholar
  11. E. Coulouma, E. Godard, and J. Peters. A characterization of oblivious message adversaries for which consensus is solvable. Theoretical Computer Science, 584:80-90, June 2015. Google Scholar
  12. A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed verification and hardness of distributed approximation. In STOC, 2011. Google Scholar
  13. C. Dutta, G. Pandurangan, R. Rajaraman, Z. Sun, and E. Viola. On the complexity of information spreading in dynamic networks. In SODA, January 2013. Google Scholar
  14. Mohsen Ghaffari, Nancy Lynch, and Calvin Newport. The cost of radio network broadcast for different models of unreliable links. In PODC, July 2013. Google Scholar
  15. R. Ingram, P. Shields, and J. Walter. An asynchronous leader election algorithm for dynamic networks. In IPDPS, 2009. Google Scholar
  16. I. Jahja, H. Yu, and Y. Zhao. Some lower bounds in dynamic networks with oblivious adversaries. Technical Report TRA7/17, School of Computing, National University of Singapore, July 2017. Also available at URL: http://www.comp.nus.edu.sg/~yuhf/oblivious-disc17-technicalreport.pdf.
  17. M. Konig and R. Wattenhofer. On local fixing. In OPODIS, 2013. Google Scholar
  18. Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea Richa. Broadcasting in unreliable radio networks. In PODC, July 2010. Google Scholar
  19. Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In STOC, June 2010. Google Scholar
  20. Fabian Kuhn, Yoram Moses, and Rotem Oshman. Coordinated consensus in dynamic networks. In PODC, June 2011. Google Scholar
  21. Fabian Kuhn and Rotem Oshman. The complexity of data aggregation in directed networks. In DISC, September 2011. Google Scholar
  22. Fabian Kuhn and Rotem Oshman. Dynamic networks: Models and algorithms. SIGACT News, 42(1):82-96, March 2011. Google Scholar
  23. U. Schmid, B. Weiss, and I. Keidar. Impossibility results and lower bounds for consensus under link failures. SIAM Journal on Computing, 38(5):1912-1951, 2009. Google Scholar
  24. O. Weinstein. Information complexity and the quest for interactive compression. SIGACT News, 46(2):41-64, June 2015. Google Scholar
  25. H. Yu, Y. Zhao, and I. Jahja. The cost of unknown diameter in dynamic networks. In SPAA, July 2016. (Journal version under submission). Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact