Document Open Access Logo

Space-Optimal Naming in Population Protocols

Authors Janna Burman, Joffroy Beauquier, Devan Sohier

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.9.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Janna Burman
  • LRI, Université Paris-Sud, CNRS, Université Paris-Saclay, France
Joffroy Beauquier
  • LRI, Université Paris-Sud, CNRS, Université Paris-Saclay, France
Devan Sohier
  • LI-PaRAD, Université de Versailles, Université Paris-Saclay, France

Cite As Get BibTex

Janna Burman, Joffroy Beauquier, and Devan Sohier. Space-Optimal Naming in Population Protocols. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.DISC.2019.9

Abstract

The distributed naming problem, assigning unique names to the nodes in a distributed system, is a fundamental task. This problem is nontrivial, especially when the amount of memory available for the task is low, and when requirements for fault-tolerance are added.
The considered distributed communication model is population protocols. In this model, a priori anonymous and indistinguishable mobile nodes (called agents), communicate in pairs and in an asynchronous manner (according to a fairness condition). Fault-tolerance is addressed through self-stabilization, in terms of arbitrary initialization of agents.
This work comprises a comprehensive study of the necessary and sufficient state space conditions for naming. The problem is studied under various combinations of model assumptions: weak or global fairness, arbitrary or uniform initialization of agents, existence or absence of a distinguishable agent (arbitrarily initialized or not), possibility of breaking symmetry in pair-wise interactions (symmetric or asymmetric transitions). For each possible combination of these assumptions, either an impossibility is proven or the necessary exact number of states (per mobile agent) is determined and an appropriate space-optimal naming protocol is presented.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • networks of passively mobile agents
  • population protocols
  • deterministic naming
  • self-stabilization
  • exact space complexity
  • tight lower bounds
  • global and weak fairness

Metrics

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

Related Versions

References

  1. D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. URL: https://doi.org/10.1007/s00446-005-0138-3.
  2. D. Angluin, J. Aspnes, D. Eisenstat, and E. Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, 2007. URL: https://doi.org/10.1007/s00446-007-0040-2.
  3. D. Angluin, J. Aspnes, M. J. Fischer, and H. Jiang. Self-stabilizing population protocols. ACM Trans. Auton. Adapt. Syst., 3(4), 2008. URL: https://doi.org/10.1145/1452001.1452003.
  4. J. Beauquier, J. Burman, S. Clavière, and D. Sohier. Space-Optimal Counting in Population Protocols. In DISC, pages 631-646, 2015. URL: https://doi.org/10.1007/978-3-662-48653-5_42.
  5. 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
  6. O. Bournez, J. Chalopin, J. Cohen, X. Koegler, and M. Rabie. Population Protocols that Correspond to Symmetric Games. IJUC, 9(1-2):5-36, 2013. URL: http://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-9-number-1-2-2013/ijuc-9-1-2-p-5-36/.
  7. O. Bournez, J. Cohen, and M. Rabie. Homonym Population Protocols. Theory Comput. Syst., 62(5):1318-1346, 2018. URL: https://doi.org/10.1007/s00224-017-9833-2.
  8. J. Burman, J. Beauquier, and D. Sohier. Space-Optimal Naming in Population Protocols. Research report, LRI, Université Paris Sud, 2019. URL: https://hal.inria.fr/hal-01790517.
  9. S. Cai, T. Izumi, and K. Wada. How to Prove Impossibility Under Global Fairness: On Space Complexity of Self-Stabilizing Leader Election on a Population Protocol Model. Theory Comput. Syst., 50(3):433-445, 2012. URL: https://doi.org/10.1007/s00224-011-9313-z.
  10. I. Chatzigiannakis, O. Michail, S. Nikolaou, A. Pavlogiannis, and P. G. Spirakis. Passively mobile communicating machines that use restricted space. Theor. Comput. Sci., 412(46):6469-6483, 2011. URL: https://doi.org/10.1016/j.tcs.2011.07.001.
  11. C. Cooper, A. Lamani, G.i Viglietta, M. Yamashita, and Y. Yamauchi. Constructing self-stabilizing oscillators in population protocols. Inf. Comput., 255:336-351, 2017. URL: https://doi.org/10.1016/j.ic.2016.12.002.
  12. C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, and E. Ruppert. When Birds Die: Making Population Protocols Fault-Tolerant. In DCOSS, pages 51-66, 2006. URL: https://doi.org/10.1007/11776178_4.
  13. E. W. Dijkstra. Self-stabilizing Systems in Spite of Distributed Control. Commun. of the ACM, 17(11):643-644, November 1974. Google Scholar
  14. S. Dolev, A. Israeli, and S. Moran. Self-Stabilization of Dynamic Systems Assuming Only Read/Write Atomicity. DC, 7(1):3-16, 1993. Google Scholar
  15. R. Guerraoui and E. Ruppert. Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures. In ICALP (2), pages 484-495, 2009. URL: https://doi.org/10.1007/978-3-642-02930-1_40.
  16. 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: https://doi.org/10.1016/j.tcs.2014.07.028.
  17. H. Jiang. Distributed Systems of Simple Interacting Agents. PhD thesis, Yale University, 2007. Google Scholar
  18. Y. Sudo, T. Masuzawa, A. K. Datta, and L. L. Larmore. The Same Speed Timer in Population Protocols. In ICDCS, pages 252-261, 2016. URL: https://doi.org/10.1109/ICDCS.2016.82.
  19. G. Tel. Introduction to Distributed Algorithms (2nd ed.). Cambridge University Press, 2000. Google Scholar
  20. H. Yasumi, F. Ooshita, K. Yamaguchi, and M. Inoue. Constant-Space Population Protocols for Uniform Bipartition. In OPODIS, pages 19:1-19:17, 2017. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2017.19.
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