Document Open Access Logo

Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations

Authors Dariusz R. Kowalski, Miguel A. Mosteiro

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.156.pdf
  • Filesize: 0.48 MB
  • 14 pages

Document Identifiers

Author Details

Dariusz R. Kowalski
  • Computer Science Department, University of Liverpool, Liverpool, UK
Miguel A. Mosteiro
  • Computer Science Department, Pace University, New York, NY, USA

Funding

  • Kowalski, Dariusz R.: Supported by Polish National Science Center grant UMO-2015/17/B/ST6/01897.
  • Mosteiro, Miguel A.: Research work partially supported by Pace University Scholarly Research Award P1258 and the UK Royal Society Grant IES\textbackslash{}R3\textbackslash{}170293.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 156:1-156:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.156

Abstract

Starting with Michail, Chatzigiannakis, and Spirakis work [Michail et al., 2013], the problem of Counting the number of nodes in {Anonymous Dynamic Networks} has attracted a lot of attention. The problem is challenging because nodes are indistinguishable (they lack identifiers and execute the same program) and the topology may change arbitrarily from round to round of communication, as long as the network is connected in each round. The problem is central in distributed computing as the number of participants is frequently needed to make important decisions, such as termination, agreement, synchronization, and many others. A variety of algorithms built on top of mass-distribution techniques have been presented, analyzed, and also experimentally evaluated; some of them assumed additional knowledge of network characteristics, such as bounded degree or given upper bound on the network size. However, the question of whether Counting can be solved deterministically in sub-exponential time remained open. In this work, we answer this question positively by presenting Methodical Counting, which runs in polynomial time and requires no knowledge of network characteristics. Moreover, we also show how to extend Methodical Counting to compute the sum of input values and more complex functions without extra cost. Our analysis leverages previous work on random walks in evolving graphs, combined with carefully chosen alarms in the algorithm that control the process and its parameters. To the best of our knowledge, our Counting algorithm and its extensions to other algebraic and Boolean functions are the first that can be implemented in practice with worst-case guarantees.

Subject Classification

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

Metrics

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

Related Versions

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. 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
  8. 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,
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. Martin Farach-Colton and Miguel A. Mosteiro. Initializing sensor networks of non-uniform density in the weak sensor model. Algorithmica, 73(1):87-114, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9905-5.
  15. A. Fernández Anta and M. A. Mosteiro. Contention resolution in multiple-access channels: k-selection in radio networks. Discrete Mathematics, Algorithms and Applications, 02(04):445-456, 2010. URL: http://dx.doi.org/10.1142/S1793830910000796.
  16. 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.
  17. D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In Proc. of the 44th IEEE Ann. Symp. on Foundations of Computer Science, pages 482-491, 2003. Google Scholar
  18. E. Kranakis, D. Krizanc, and J. Vandenberg. Computing boolean functions on anonymous networks. Information and Computation, 114(2):214-236, 1994. URL: http://dx.doi.org/10.1006/inco.1994.1086.
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. Sujay Sanghavi, Bruce Hajek, and Laurent Massoulié. Gossiping with multiple messages. IEEE Transactions on Information Theory, 53(12):4640-4654, 2007. 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 Imprint Privacy Contact