Document Open Access Logo

Time and Space Optimal Counting in Population Protocols

Authors James Aspnes, Joffroy Beauquier, Janna Burman, Devan Sohier

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.13.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

James Aspnes
Joffroy Beauquier
Janna Burman
Devan Sohier

Cite As Get BibTex

James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. Time and Space Optimal Counting in Population Protocols. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.13

Abstract

This work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of (exact) counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized.

This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of counting given the optimal space per agent. In the case of randomly interacting agents (probabilistic fairness), as usual, the convergence time is measured in terms of parallel time (or parallel interactions), which is defined as the number of pairwise interactions until convergence, divided by n (the number of agents). In case of weak fairness, where it is only required that every pair of agents interacts infinitely often, the convergence time is defined in terms of non-null transitions, i.e, the transitions that affect the states of the interacting agents.

First, assuming probabilistic fairness, we present a "non-guessing" time optimal protocol of O(n log n) expected time given an optimal space of only one bit, and we prove the time optimality of this protocol. Then, for weak fairness, we show that a space optimal (semi-uniform) solution cannot converge faster than in big-omega (2^n) time (non-null transitions). This result, together with the time complexity analysis of an already known space optimal protocol, shows that it is also optimal in time (given the optimal space constrains).

Subject Classification

Keywords
  • networks of passively mobile agents/sensors
  • population protocols
  • counting
  • anonymous non-initialized agents
  • time and space complexity
  • lower bounds

Metrics

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

References

  1. D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, and R. L. Rivest. Time-space trade-offs in population protocols. CoRR, abs/1602.08032, 2016. URL: http://arxiv.org/abs/1602.08032.
  2. D. Alistarh and R. Gelashvili. Polylogarithmic-time leader election in population protocols. In ICALP, pages 479-491, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_38.
  3. D. Alistarh, R. Gelashvili, and M. Vojnovic. Fast and exact majority in population protocols. In PODC, pages 47-56, 2015. URL: http://dx.doi.org/10.1145/2767386.2767429.
  4. D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. Dist. Comp., 18(4):235-253, 2006. URL: http://dx.doi.org/10.1007/s00446-005-0138-3.
  5. D. Angluin, J. Aspnes, D. Eisenstat, and E. Ruppert. The computational power of population protocols. Dist. Comp., 20(4):279-304, 2007. URL: http://dx.doi.org/10.1007/s00446-007-0040-2.
  6. A. F. Anta, M. A. Mosteiro, and C. 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.
  7. J. Aspnes, J. Beauquier, J. Burman, and D. Sohier. Time and Space Optimal Counting in Population Protocols, https://hal.inria.fr/hal-01399797. Technical report, Yale, Nov 2016.
  8. C. Baquero, P. S. Almeida, R. Menezes, and P. Jesus. Extrema propagation: Fast distributed estimation of sums and network sizes. IEEE Trans. Parallel Distrib. Syst., 23(4):668-675, 2012. URL: http://dx.doi.org/10.1109/TPDS.2011.209.
  9. J. Beauquier, J. Burman, and S. Clavière. Comptage et nommage simples et efficaces dans les protocoles de populations symétriques. In ALGOTEL 2014, pages 1-4, Jun 2014. URL: https://hal.archives-ouvertes.fr/hal-00986109.
  10. J. Beauquier, J. Burman, S. Clavière, and D. Sohier. Space-optimal counting in population protocols. In DISC, pages 631-646, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_42.
  11. J. Beauquier, J. Clement, S. Messika, L. Rosaz, and B. Rozoy. Self-stabilizing counting in mobile sensor networks with a base station. In DISC, pages 63-76, 2007. Google Scholar
  12. G. Di Luna, R. Baldoni, S. Bonomi, and I. Chatzigiannakis. Conscious and unconscious counting on anonymous dynamic networks. In ICDCN, pages 257-271, 2014. URL: http://dx.doi.org/10.1007/978-3-642-45249-9_17.
  13. G. Di Luna, R. Baldoni, S. Bonomi, and I. Chatzigiannakis. Counting in anonymous dynamic networks under worst-case adversary. In ICDCS, pages 338-347, 2014. URL: http://dx.doi.org/10.1109/ICDCS.2014.42.
  14. G. A. Di Luna and R. Baldoni. Brief announcement: Investigating the cost of anonymity on dynamic networks. In PODC, pages 339-341, 2015. URL: http://dx.doi.org/10.1145/2767386.2767442.
  15. S. Dolev, M. G. Gouda, and M. Schneider. Memory requirements for silent stabilization. Acta Inf., 36(6):447-462, 1999. URL: http://link.springer.de/link/service/journals/00236/bibs/9036006/90360447.htm.
  16. S. Dolev, A. Israeli, and S. Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. Dist. Comp., 7(1):3-16, 1993. URL: http://dx.doi.org/10.1007/BF02278851.
  17. D. Doty and D. Soloveichik. Stable leader election in population protocols requires linear time. In DISC, pages 602-616, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_40.
  18. A. J. Ganesh, A.-M. Kermarrec, E. Le Merrer, and L. Massoulié. Peer counting and sampling in overlay networks based on random walks. Dist. Comp., 20(4):267-278, 2007. URL: http://dx.doi.org/10.1007/s00446-007-0027-z.
  19. C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks: Algorithms and evaluation. Perform. Eval., 63(3):241-263, 2006. URL: http://dx.doi.org/10.1016/j.peva.2005.01.002.
  20. T. Izumi, K. Kinpara, T. Izumi, and K. Wada. Space-efficient self-stabilizing counting population protocols on mobile sensor networks. Theor. Comput. Sci., 552:99-108, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2014.07.028.
  21. H. Jiang. Distributed Systems of Simple Interacting Agents. PhD thesis, Yale University, 2007. Google Scholar
  22. P. Juang, H. Oki, Y. Wang, M. Martonosi, L. Peh, and D. Rubenstein. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet. In ASPLOS, pages 96-107, 2002. URL: http://dx.doi.org/10.1145/605397.605408.
  23. D. Kostoulas, D. Psaltoulis, I. Gupta, K. P. Birman, and A. J. Demers. Active and passive techniques for group size estimation in large-scale and dynamic distributed systems. Journal of Systems and Software, 80(10):1639-1658, 2007. URL: http://dx.doi.org/10.1016/j.jss.2007.01.014.
  24. S. Lahde, M. Doering, W. Pöttner, G. Lammert, and L. C. Wolf. A practical analysis of communication characteristics for mobile and distributed pollution measurements on the road. Wirel. Comm. and Mob. Comput., 7(10):1209-1218, 2007. Google Scholar
  25. O. Michail, I. Chatzigiannakis, and P. G. Spirakis. Naming and counting in anonymous unknown dynamic networks. In SSS, pages 281-295, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03089-0_20.
  26. A. Milani and M. A. Mosteiro. A faster counting protocol for anonymous dynamic networks. In OPODIS, pages 28:1-28:13, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.OPODIS.2015.28.
  27. Y. Mocquard, E. Anceaume, J. Aspnes, Y. Busnel, and B. Sericola. Counting with population protocols. In NCA, pages 35-42, 2015. URL: http://dx.doi.org/10.1109/NCA.2015.35.
  28. Pigeon Air Patrol project, 2016. URL: http://www.pigeonairpatrol.com/.
  29. B. F. Ribeiro and D. F. Towsley. Estimating and sampling graphs with multidimensional random walks. In ACM SIGCOMM, pages 390-403, 2010. URL: http://dx.doi.org/10.1145/1879141.1879192.
  30. G. Tel. Introduction to Distributed Algorithms. Cambridge University Press, 2000. 2nd ed. Google Scholar
  31. D. Varagnolo, G. Pillonetto, and L. Schenato. Distributed statistical estimation of the number of nodes in sensor networks. In CDC, pages 1498-1503, 2010. URL: http://dx.doi.org/10.1109/CDC.2010.5717355.
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