Document Open Access Logo

Deterministic Population Protocols for Exact Majority and Plurality

Authors Leszek Gasieniec, David Hamilton, Russell Martin, Paul G. Spirakis, Grzegorz Stachowiak

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.14.pdf
  • Filesize: 461 kB
  • 14 pages

Document Identifiers

Author Details

Leszek Gasieniec
David Hamilton
Russell Martin
Paul G. Spirakis
Grzegorz Stachowiak

Cite As Get BibTex

Leszek Gasieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak. Deterministic Population Protocols for Exact Majority and Plurality. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.14

Abstract

In this paper we study space-efficient deterministic population protocols for several variants of the majority problem including plurality consensus. We focus on space efficient majority protocols in populations with an arbitrary number of colours C represented by k-bit labels, where k = ceiling (log C). In particular, we present asymptotically space-optimal (with respect to the adopted k-bit representation of colours) protocols for (1) the absolute majority problem, i.e., a protocol which decides whether a single colour dominates all other colours considered together, and (2) the relative majority problem, also known in the literature as plurality consensus, in which colours declare their volume superiority versus other individual colours.

The new population protocols proposed in this paper rely on a dynamic formulation of the majority problem in which the colours originally present in the population can be changed by an external force during the communication process. The considered dynamic formulation is based on the concepts studied by D. Angluin et al. and O. Michail et al. about stabilizing inputs and composition of population protocols. Also, the protocols presented in this paper use a composition of some known protocols for static and dynamic majority.

Subject Classification

Keywords
  • Deterministic population protocols
  • majority
  • plurality consenus

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. Google Scholar
  2. D. Alistarh and R. Gelashvili. Polylogarithmic-time leader election in population protocols. In Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 479-491, 2015. Google Scholar
  3. D. Alistarh, R. Gelashvili, and M. Vojnovic. Fast and exact majority in population protocols. In Proc. 33rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 47-56, 2015. Google Scholar
  4. D. Angluin, J. Aspnes, M. Chan, M.J. Fischer, H. Jiang, and R. Peralta. Stably computable properties of network graphs. In Proc. 1st IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), pages 63-74, 2005. Google Scholar
  5. D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. In Proc. 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 290-299, 2004. Google Scholar
  6. 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. Google Scholar
  7. D. Angluin, J. Aspnes, and D. Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87-102, 2008. Google Scholar
  8. D. Angluin, J. Aspnes, M. J. Fischer, and H. Jiang. Self-stabilizing population protocols. ACM Trans. Auton. Adapt. Syst., 3(4):1-28, 2008. Google Scholar
  9. L. Gąsieniec, D. D. Hamilton, R. Martin, and P. G. Spirakis. The match-maker: Constant-space distributed majority via random walks. In Proc. 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 67-80, 2015. Google Scholar
  10. L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri, and L. Trevisan. Simple dynamics for plurality consensus. In Proc. 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 247-256, 2014. Google Scholar
  11. L. Becchetti, A. E. F. Clementi, E. Natale, F. Pasquale, and R. Silvestri. Plurality consensus in the gossip model. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 371-390, 2015. Google Scholar
  12. P. Berenbrink, T. Friedetzky, G. Giakkoupis, and P. Kling. Efficient plurality consensus, or: The benefits of cleaning up from time to time. In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 1-14, 2016. Google Scholar
  13. J. M. Bower and H. Bolouri. Computational modeling of genetic and biochemical networks. MIT Press, 2004. Google Scholar
  14. H.-L. Chen, R. Cummings, D. Doty, and D. Soloveichik. Speed faults in computation by chemical reaction networks. Distributed Computing, pages 16-30, 2014. Google Scholar
  15. C. Cooper, R. Elsaesser, and T. Radzik. The power of two choices in distributed voting. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 435-446, 2014. Google Scholar
  16. C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, and E. Ruppert. When birds die: Making population protocols fault-tolerant. In IEEE 2nd Intl. Conference on Distributed Computing in Sensor Systems (DCOSS), volume 4026 of Lecture Notes in Computer Science, pages 51-56. Springer-Verlag, 2006. Google Scholar
  17. B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, , and C. Scheideler. Stabilizing consensus with the power of two choices. In Proc. 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 149-158, 2011. Google Scholar
  18. S. Dolev. Self Stabilization. MIT Press, 2000. Google Scholar
  19. D. Doty and D. Soloveichik. Stable leader election in population protocols requires linear time. In Proc. 29th International Symposium on Distributed Computing (DISC), pages 602-616, 2015. Google Scholar
  20. M. Draief and M. Vojnovic. Convergence speed of binary interval consensus. SIAM Journal on Control and Optimization, 50(3):1087-1109, 2012. Google Scholar
  21. P. Fraigniaud and E. Natale. Noisy rumor spreading and plurality consensus. In Proc. 34th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 127-136, 2016. Google Scholar
  22. M. Ghaffari and M. Parter. A polylogarithmic gossip algorithm for plurality consensus. In Proc. 34th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 117-126, 2016. Google Scholar
  23. G. B. Mertzios, S. E. Nikoletseas, C. Raptopoulos, and P. G. Spirakis. Determining majority in networks with local interactions and very small local memory. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP), pages 871-882, 2014. Google Scholar
  24. O. Michail, I. Chatzigiannakis, and P. G. Spirakis. New Models for Population Protocols. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2011. Google Scholar
  25. O. Michail and P. G. Spirakis. Simple and efficient local codes for distributed stable network construction. In Proc. 32nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 76-85, 2014. Google Scholar
  26. Y. Mocquard, E. Anceaume, J. Aspnes, Y. Busnel, and B. Sericola. Counting with population protocols. In Proc. 2015 IEEE 14th International Symposium on Network Computing and Applications (NCA), pages 35-42, 2015. Google Scholar
  27. E. Perron, D. Vasudevan, and M. Vojnovic. Using three states for binary consensus on complete graphs. In Proc. 28th Conference on Computer Communications (INFOCOM), pages 2527-2535, 2009. 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