Document Open Access Logo

Non Trivial Computations in Anonymous Dynamic Networks

Authors Giuseppe Di Luna, Roberto Baldoni

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.33.pdf
  • Filesize: 1.14 MB
  • 16 pages

Document Identifiers

Author Details

Giuseppe Di Luna
Roberto Baldoni

Cite As Get BibTex

Giuseppe Di Luna and Roberto Baldoni. Non Trivial Computations in Anonymous Dynamic Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.33

Abstract

In this paper we consider a static set of anonymous processes, i.e., they do not have distinguished IDs, that communicate with neighbors using a local broadcast primitive. The communication graph changes at each computational round with the restriction of being always connected, i.e., the network topology guarantees 1-interval connectivity. In such setting non trivial computations, i.e., answering to a predicate like "there exists at least one process with initial input a?", are impossible. In a recent work, it has been conjectured that the impossibility holds even if a distinguished leader process is available within the computation. In this paper we prove that the conjecture is false. We show this result by implementing a deterministic leader-based terminating counting algorithm. In order to build our counting algorithm we first develop a counting technique that is time optimal on a family of dynamic graphs where each process has a fixed distance h from the leader and such distance does not change along rounds. Using this technique we build an algorithm that counts in anonymous 1-interval connected networks.

Subject Classification

Keywords
  • Distributed System
  • Anonymous Networks
  • Dynamic Networks

Metrics

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

References

  1. D. Angluin. Local and global properties in networks of processors (extended abstract). In STOC'80, pages 82-93. ACM, 1980. URL: http://dx.doi.org/10.1145/800141.804655.
  2. R. Baldoni, S. Bonomi, A. Kermarrec, and M. Raynal. Implementing a register in a dynamic distributed system. In IEEE International Conference on Distributed Computing Systems (ICDCS'09), pages 639-647, 2009. URL: http://dx.doi.org/10.1109/ICDCS.2009.46.
  3. M. Bawa, A. Gionis, H. Garcia-Molina, and R. Motwani. The price of validity in dynamic networks. J. Comput. Syst. Sci., 73(3):245-264, May 2007. URL: 10.1016/j.jcss.2006.10.007, URL: http://dx.doi.org/10.1016/j.jcss.2006.10.007.
  4. Joffroy Beauquier, Janna Burman, Simon Clavière, and Devan Sohier. Space-optimal counting in population protocols. In (to appear) DISC'15, 2015. URL: https://hal.inria.fr/hal-01169634.
  5. P. Boldi and S. Vigna. Computing anonymously with arbitrary knowledge. In PODC'99, pages 181-188. ACM, 1999. Google Scholar
  6. P. Boldi and S. Vigna. Fibrations of graphs. Discrete Mathematics, 243(1-3):21-66, 2002. URL: http://dx.doi.org/10.1016/S0012-365X(00)00455-6.
  7. A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. CoRR, abs/1012.0009, 2010. URL: http://arxiv.org/abs/1012.0009.
  8. P. Fraigniaud, A. Pelc, D. Peleg, and S. Pérennes. Assigning labels in an unknown anonymous network with a leader. Distributed Computing, 14(3):163-183, 2001. URL: http://dx.doi.org/10.1007/PL00008935.
  9. M. Jelasity, A. Montresor, and Ö. Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst., 23(3):219-252, 2005. Google Scholar
  10. D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In FOCS'03, pages 482-491. IEEE, 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238221.
  11. J. Kong, X. Hong, and M. Gerla. An identity-free and on-demand routing scheme against anonymity threats in mobile ad hoc networks. IEEE Transactions on Mobile Computing, 6(8):888-902, 2007. Google Scholar
  12. F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. In STOC'10, pages 513-522. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806760.
  13. F. Kuhn and R. Oshman. Dynamic networks: Models and algorithms. SIGACT News, 42(1):82-96, March 2011. URL: http://dx.doi.org/10.1145/1959045.1959064.
  14. G. Di Luna and R. Baldoni. Brief announcement: Investigating the cost of anonymity on dynamic networks. In PODC'15, pages 339-341. ACM, 2015. URL: http://dx.doi.org/10.1145/2767386.2767442.
  15. G. Di Luna, R. Baldoni, S. Bonomi, and I. Chatzigiannakis. Conscious and unconscious counting on anonymous dynamic networks. In ICDCN'14, pages 257-271. Springer, 2014. Google Scholar
  16. G. Di Luna, R. Baldoni, S. Bonomi, and I. Chatzigiannakis. Counting in anonymous dynamic networks under worst case adversary. In ICDCS'14, pages 338-347. IEEE, 2014. Google Scholar
  17. L. Massoulié, E. Le Merrer, A.-M. Kermarrec, and A. Ganesh. Peer counting and sampling in overlay networks: Random walk methods. In PODC'06, pages 123-132. ACM, 2006. URL: http://dx.doi.org/10.1145/1146381.1146402.
  18. O. Michail, I. Chatzigiannakis, and P. Spirakis. Brief announcement: Naming and counting in anonymous unknown dynamic networks. In DISC'12, pages 437-438. Springer, 2012. Google Scholar
  19. O. Michail, I. Chatzigiannakis, and P. Spirakis. Naming and counting in anonymous unknown dynamic networks. In SSS'13, pages 281-295. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03089-0_20.
  20. O. Michail, I. Chatzigiannakis, and P. G. Spirakis. Causality, influence, and computation in possibly disconnected synchronous dynamic networks. In OPODIS'12, pages 269-283, 2012. URL: http://dx.doi.org/10.1007/978-3-642-35476-2_19.
  21. D. Mosk-Aoyama and D. Shah. Computing separable functions via gossip. In PODC' 06, pages 113-122. ACM, 2006. URL: http://dx.doi.org/10.1145/1146381.1146401.
  22. R. O'Dell and R. Wattenhofer. Information dissemination in highly dynamic graphs. In DIALM-POMC' 05, pages 104-110, 2005. URL: http://dx.doi.org/10.1145/1080810.1080828.
  23. B. Ribeiro and D. Towsley. Estimating and sampling graphs with multidimensional random walks. In IMC'10, pages 390-403, New York, NY, USA, 2010. ACM. URL: http://dx.doi.org/10.1145/1879141.1879192.
  24. N. Sakamoto. Comparison of initial conditions for distributed algorithms on anonymous networks. In Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, PODC'99, pages 173-179. ACM, 1999. URL: http://dx.doi.org/10.1145/301308.301352.
  25. M. Yamashita and T. Kameda. Computing on an anonymous network. In PODC'88, pages 117-130. ACM, 1988. URL: http://dx.doi.org/10.1145/62546.62568.
  26. M. Yamashita and T. Kameda. Computing on anonymous networks: Part 1-characterizing the solvable cases. IEEE Trans. on Parallel and Distributed Systems, 7(1):69-89, 1996. URL: http://dx.doi.org/10.1109/71.481599.
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