Document Open Access Logo

The Benefits of Entropy in Population Protocols

Authors Joffroy Beauquier, Peva Blanchard, Janna Burman, Rachid Guerraoui

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.21.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Joffroy Beauquier
Peva Blanchard
Janna Burman
Rachid Guerraoui

Cite As Get BibTex

Joffroy Beauquier, Peva Blanchard, Janna Burman, and Rachid Guerraoui. The Benefits of Entropy in Population Protocols. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.21

Abstract

A distributed computing system can be viewed as the result of the interplay between a distributed algorithm specifying the effects of a local event (e.g. reception of a message), and an adversary choosing the interleaving (schedule) of these events in the execution. In the context of large networks of mobile pairwise interacting agents (population protocols), the adversary models the mobility of the agents by choosing the successive pairs of interacting agents. For some problems, assuming that the adversary selects the schedule according to some probability distribution greatly helps to devise (almost) correct solutions. But how much randomness is really necessary? To what extent does a problem admit implementations that are robust against a "not so random" schedule? This paper takes a first step in addressing this question by borrowing the concept of T-randomness, 0 <= T <= 1, from algorithmic information theory. Roughly speaking, the value T fixes the entropy rate of the considered schedules. For instance, the case T = 1 corresponds, in a specific sense, to schedules in which the pairs of interacting agents are chosen independently and uniformly (perfect randomness). The holy grail question can then be precisely stated as determining the optimal entropy rate to solve a given problem. We first show that perfect randomness is never required. Precisely, if a finite-state algorithm solves a problem with 1-randomness, then this algorithm still solves the same problem with T-randomness for some T < 1. Second, we illustrate how to compute bounds on the optimal entropy rate of a specific problem, namely the leader election problem.

Subject Classification

Keywords
  • algorithmic randomness
  • entropy
  • leader election
  • distributed computing
  • scheduler
  • population protocols

Metrics

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

References

  1. Yehuda Afek and Yossi Matias. Elections in anonymous networks. Information and Computation, 113(2):312-330, 1994. URL: http://dx.doi.org/10.1006/inco.1994.1075.
  2. Dan Alistarh, Keren Censor-Hillel, and Nir Shavit. Are lock-free concurrent algorithms practically wait-free? In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 714-723, 2014. URL: http://dx.doi.org/10.1145/2591796.2591836.
  3. Dana Angluin. Local and global properties in networks of processors (extended abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 82-93, 1980. URL: http://dx.doi.org/10.1145/800141.804655.
  4. Dana Angluin, James Aspnes, Melody Chan, Hong Jiang, Michael J. Fischer, and René Peralta. Stably computable properties of network graphs. In Distributed Computing in Sensor Systems, pages 63-74. LNCS 3560, 2005. Google Scholar
  5. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, 2006. URL: http://dx.doi.org/10.1007/s00446-005-0138-3.
  6. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In PODC'06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 292-299, New York, NY, USA, 2006. ACM Press. URL: http://dx.doi.org/10.1145/1146381.1146425.
  7. James Aspnes. Fast deterministic consensus in a noisy environment. In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, PODC'00, pages 299-308, New York, NY, USA, 2000. ACM. URL: http://dx.doi.org/10.1145/343477.343631.
  8. Joffroy Beauquier, Peva Blanchard, and Janna Burman. Self-stabilizing leader election in population protocols over arbitrary communication graphs. In Principles of Distributed Systems - 17th International Conference, OPODIS 2013, Nice, France, December 16-18, 2013. Proceedings, pages 38-52, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03850-6_4.
  9. Cristian S. Calude and Marius Zimand. Algorithmically independent sequences. In Developments in Language Theory, 12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008. Proceedings, pages 183-195, 2008. URL: http://dx.doi.org/10.1007/978-3-540-85780-8_14.
  10. Gregory J. Chaitin. A theory of program size formally identical to information theory. Journal of the ACM, 22(3):329-340, July 1975. URL: http://dx.doi.org/10.1145/321892.321894.
  11. Jérémie Chalopin. Local computations on closed unlabelled edges: The election problem and the naming problem. In SOFSEM 2005: Theory and Practice of Computer Science, 31st Conference on Current Trends in Theory and Practice of Computer Science, Liptovský Ján, Slovakia, January 22-28, 2005, Proceedings, pages 82-91, 2005. Google Scholar
  12. Jérémie Chalopin, Yves Métivier, and Thomas Morsellino. Enumeration and leader election in partially anonymous and multi-hop broadcast networks. Fundamenta Informaticae, 120(1):1-27, 2012. URL: http://dx.doi.org/10.3233/FI-2012-747.
  13. Yuval Emek, Christoph Pfister, Jochen Seidel, and Roger Wattenhofer. Anonymous networks: randomization = 2-hop coloring. In ACM Symposium on Principles of Distributed Computing, PODC'14, Paris, France, July 15-18, 2014, pages 96-105, 2014. URL: http://dx.doi.org/10.1145/2611462.2611478.
  14. Leonidas J. Guibas and Andrew M. Odlyzko. String overlaps, pattern matching, and nontransitive games. Journal of Combinatorial Theory, Series A, 30(2):183-208, 1981. URL: http://dx.doi.org/10.1016/0097-3165(81)90005-4.
  15. Alon Itai and Michael Rodeh. Symmetry breaking in distributive networks. In 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981, pages 150-158, 1981. URL: http://dx.doi.org/10.1109/SFCS.1981.41.
  16. Andreï Nikolaïevitch Kolmogorov. Three approaches to the quantitative definition of information. Problemy Peredachi Informatsii, 1(1):3-31, 1965. Google Scholar
  17. Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications, Third Edition. Texts in Computer Science. Springer, 2008. URL: http://dx.doi.org/10.1007/978-0-387-49820-1.
  18. Per Martin-Löf. The definition of random sequences. Information and Control, 9(6):602-619, 1966. Google Scholar
  19. Antoni Mazurkiewicz. Distributed enumeration. Information Processing Letters, 61(5):233-239, March 1997. URL: http://dx.doi.org/10.1016/S0020-0190(97)00022-7.
  20. Ray J. Solomonoff. A formal theory of inductive inference part i. Information and Control, 7(1):1-22, March 1964. Google Scholar
  21. Ray J. Solomonoff. A formal theory of inductive inference part ii. Information and Control, 7(2):224-254, June 1964. Google Scholar
  22. Ludwig Staiger. The kolmogorov complexity of infinite words. Theoretical Computer Science, 383(2-3):187-199, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.04.013.
  23. Kohtaro Tadaki. A generalization of Chaitin’s halting probability Ω and halting self-similar sets. Hokkaido Mathematical Journal, 31(1):219-253, 02 2002. URL: http://dx.doi.org/10.14492/hokmj/1350911778.
  24. Kohtaro Tadaki. Partial randomness and dimension of recursively enumerable reals. In Mathematical Foundations of Computer Science, pages 687-699, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03816-7_58.
  25. Alexander K. Zvonkin and Leonid A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys, page 11, 1970. 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 About DROPS Imprint Privacy Contact