Document Open Access Logo

Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader

Authors Dariusz R. Kowalski, Miguel A. Mosteiro

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.147.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Dariusz R. Kowalski
  • Department of Computer Science, University of Liverpool, UK
  • SWPS University of Social Sciences and Humanities, Warsaw, Poland
Miguel A. Mosteiro
  • Computer Science Department, Pace University, New York, NY, USA

Funding

This work was supported by the National Science Center Poland (NCN) grant 2017/25/B/ ST6/02553; the UK Royal Society International Exchanges 2017 Round 3 Grant #170293; and Pace University SR Grant and Kenan Fund.

Cite As Get BibTex

Dariusz R. Kowalski and Miguel A. Mosteiro. Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 147:1-147:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.147

Abstract

Counting the number of nodes in {Anonymous Dynamic Networks} is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [Michail et al., 2013], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [Dariusz R. Kowalski and Miguel A. Mosteiro, 2018]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. 
In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Anonymous Dynamic Networks
  • Counting
  • distributed algorithms

Metrics

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

References

  1. Chen Avin, Michal Kouckỳ, and Zvi Lotker. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In Automata, languages and programming, pages 121-132. Springer, 2008. Google Scholar
  2. Roberto Baldoni and Giuseppe A Di Luna. Counting on Anonymous Dynamic Networks: Bounds and Algorithms. manuscript, 2016. Google Scholar
  3. Siddhartha Banerjee, Aditya Gopalan, Abhik Kumar Das, and Sanjay Shakkottai. Epidemic spreading with external agents. IEEE Transactions on Information Theory, 60(7):4125-4138, 2014. Google Scholar
  4. Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-2530, 2006. Google Scholar
  5. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. Google Scholar
  6. Maitri Chakraborty, Alessia Milani, and Miguel A. Mosteiro. Counting in Practical Anonymous Dynamic Networks is Polynomial. In Proceedings of the 4th International Conference on Networked Systems, volume 9944 of Lecture Notes in Computer Science, pages 131-136, 2016. Google Scholar
  7. Maitri Chakraborty, Alessia Milani, and Miguel A. Mosteiro. A Faster Exact-Counting Protocol for Anonymous Dynamic Networks. Algorithmica, 80(11):3023-3049, 2018. URL: http://dx.doi.org/10.1007/s00453-017-0367-4.
  8. Yuxin Chen, Sanjay Shakkottai, and Jeffrey G Andrews. On the role of mobility for multimessage gossip. IEEE Transactions on Information Theory, 59(6):3953-3970, 2013. Google Scholar
  9. Giuseppe Antonio Di Luna and Roberto Baldoni. Investigating the Cost of Anonymity on Dynamic Networks. CoRR, abs/1505.03509, 2015. URL: http://arxiv.org/abs/1505.03509.
  10. Giuseppe Antonio Di Luna and Roberto Baldoni. Non Trivial Computations in Anonymous Dynamic Networks. In Proceedings of the 19th International Conference on Principles of Distributed Systems, Leibniz International Proceedings in Informatics, 2015. To appear. Google Scholar
  11. Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. Conscious and Unconscious Counting on Anonymous Dynamic Networks. In Proceedings of the 15th International Conference on Distributed Computing and Networking, volume 8314 of Lecture Notes in Computer Science, pages 257-271. Springer Berlin Heidelberg, 2014. Google Scholar
  12. Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. Counting in Anonymous Dynamic Networks under Worst-Case Adversary. In Proceedings of the 34th International Conference on Distributed Computing Systems, pages 338-347. IEEE, 2014. Google Scholar
  13. Giuseppe Antonio Di Luna, Silvia Bonomi, Ioannis Chatzigiannakis, and Roberto Baldoni. Counting in Anonymous Dynamic Networks: An Experimental Perspective. In Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, volume 8243 of Lecture Notes in Computer Science, pages 139-154. Springer Berlin Heidelberg, 2014. Google Scholar
  14. M. Farach-Colton, A. Fernández Anta, A. Milani, M. A. Mosteiro, and S. Zaks. Opportunistic Information Dissemination in Mobile Ad-hoc Networks: adaptiveness vs. obliviousness and randomization vs. determinism. In Proc. of the 10th Latin American Theoretical Informatics Symposium, volume 7256 of Lecture Notes in Computer Science, pages 303-314. Springer-Verlag, Berlin, 2012. Google Scholar
  15. Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, and Shmuel Zaks. Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony. Distributed Computing, 25(4):279-296, 2012. URL: http://dx.doi.org/10.1007/s00446-012-0165-9.
  16. Dariusz R. Kowalski and Miguel A. Mosteiro. Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 156:1-156:14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.156.
  17. Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed Computation in Dynamic Networks. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 513-522. ACM, 2010. Google Scholar
  18. Othon Michail, Ioannis Chatzigiannakis, and Paul G Spirakis. Naming and counting in anonymous unknown dynamic networks. In Stabilization, Safety, and Security of Distributed Systems, pages 281-295. Springer, 2013. Google Scholar
  19. Alessia Milani and Miguel A. Mosteiro. A Faster Counting Protocol for Anonymous Dynamic Networks. In Proceedings of the 19th International Conference on Principles of Distributed Systems, volume 46 of Leibniz International Proceedings in Informatics, pages 1-13, 2015. Google Scholar
  20. Damon Mosk-Aoyama and Devavrat Shah. Fast distributed algorithms for computing separable functions. IEEE Transactions on Information Theory, 54(7):2997-3007, 2008. Google Scholar
  21. Angelia Nedic, Alex Olshevsky, Asuman Ozdaglar, and John N Tsitsiklis. On distributed averaging algorithms and quantization effects. IEEE Transactions on Automatic Control, 54(11):2506-2517, 2009. Google Scholar
  22. Sujay Sanghavi, Bruce Hajek, and Laurent Massoulié. Gossiping with multiple messages. IEEE Transactions on Information Theory, 53(12):4640-4654, 2007. Google Scholar
  23. Atish Das Sarma, Anisur Rahaman Molla, and Gopal Pandurangan. Distributed computation in dynamic networks via random walks. Theoretical Computer Science, 581:45-66, 2015. 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