A Faster Counting Protocol for Anonymous Dynamic Networks

Authors Alessia Milani, Miguel A. Mosteiro



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.28.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Alessia Milani
Miguel A. Mosteiro

Cite AsGet BibTex

Alessia Milani and Miguel A. Mosteiro. A Faster Counting Protocol for Anonymous Dynamic Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.OPODIS.2015.28

Abstract

We study the problem of counting the number of nodes in a slotted-time communication network, under the challenging assumption that nodes do not have identifiers and the network topology changes frequently. That is, for each time slot links among nodes can change arbitrarily provided that the network is always connected. This network model has been motivated by the ongoing development of new communication technologies that enable the deployment of a massive number of devices with highly dynamic connectivity patterns. Tolerating dynamic topologies is clearly crucial in face of mobility and unreliable communication. Current communication networks do have node identifiers though. Nevertheless, in future massive networks, it might be suitable to avoid nodes IDs to facilitate mass production. Consequently, knowing what is the cost of anonymity is of paramount importance to understand what is feasible or not for future generations of Dynamic Networks. Counting is a fundamental task in distributed computing since knowing the size of the system often facilitates the desing of solutions for more complex problems. Also, the size of the system is usually used to decide termination in distributed algorithms. Currently, the best upper bound proved on the running time to compute the exact network size is double-exponential. However, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not. In this paper we make a significant step towards answering this question by presenting a distributed Counting protocol for Anonymous Dynamic Networks which has exponential time complexity. This algorithm, which we call Incremental Counting, ensures that eventually every node knows the exact size of the system and stops executing the protocol. Previous Counting protocols have either double-exponential time complexity, or they are exponential but do not terminate, or terminate but do not provide running-time guarantees, or guarantee only an exponential upper bound on the network size. Other protocols are heuristic and do not guarantee the correct count.
Keywords
  • Anonymous Dynamic Networks
  • Counting
  • Time-varying Graphs

Metrics

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

References

  1. Paulo Sérgio Almeida, Carlos Baquero, Martín Farach-Colton, Paulo Jesus, and Miguel A. Mosteiro. Fault-tolerant aggregation: Flow-updating meets mass-distribution. In Antonio Fernández Anta, Giuseppe Lipari, and Matthieu Roy, editors, Principles of Distributed Systems - 15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011. Proceedings, volume 7109 of Lecture Notes in Computer Science, pages 513-527. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25873-2_35.
  2. 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.
  3. 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
  4. Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. Conscious and unconscious counting on anonymous dynamic networks. In Mainak Chatterjee, Jian-nong Cao, Kishore Kothapalli, and Sergio Rajsbaum, editors, Distributed Computing and Networking, volume 8314 of Lecture Notes in Computer Science, pages 257-271. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-642-45249-9_17.
  5. Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. Counting in anonymous dynamic networks under worst-case adversary. In Distributed Computing Systems (ICDCS), 2014 IEEE 34th International Conference on, pages 338-347. IEEE, 2014. Google Scholar
  6. Giuseppe Antonio Di Luna, Silvia Bonomi, Ioannis Chatzigiannakis, and Roberto Baldoni. Counting in anonymous dynamic networks: An experimental perspective. In Paola Flocchini, Jie Gao, Evangelos Kranakis, and Friedhelm Meyer auf der Heide, editors, Algorithms for Sensor Systems, volume 8243 of Lecture Notes in Computer Science, pages 139-154. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-642-45346-5_11.
  7. K. Fall. A delay-tolerant network architecture for challenged internets. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM), pages 27-34, 2003. Google Scholar
  8. Antonio Fernández Anta, Miguel A. Mosteiro, and Christopher Thraves. An early-stopping protocol for computing aggregate functions in sensor networks. J. Parallel Distrib. Comput., 73(2):111-121, 2013. URL: http://dx.doi.org/10.1016/j.jpdc.2012.09.013.
  9. 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
  10. Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC'10, pages 513-522, New York, NY, USA, 2010. ACM. URL: http://dx.doi.org/10.1145/1806689.1806760.
  11. 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.
  12. 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
  13. Othon Michail, Ioannis Chatzigiannakis, and Paul G Spirakis. Causality, influence, and computation in possibly disconnected synchronous dynamic networks. Journal of Parallel and Distributed Computing, 74(1):2016-2026, 2014. Google Scholar
  14. Regina O'Dell and Rogert Wattenhofer. Information dissemination in highly dynamic graphs. In Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC'05, pages 104-110, New York, NY, USA, 2005. ACM. URL: http://dx.doi.org/10.1145/1080810.1080828.
  15. L. Pelusi, A. Passarella, and M. Conti. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks. Communications Magazine, IEEE, 44(11):134-141, 2006. 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