Document Open Access Logo

Stabilization Time in Minority Processes

Authors Pál András Papp, Roger Wattenhofer

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2019.43.pdf
  • Filesize: 0.53 MB
  • 19 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Theory of computation → Distributed computing models
  • Theory of computation → Self-organization
Keywords
  • Minority process
  • Benevolent model

Metrics

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

Abstract

We analyze the stabilization time of minority processes in graphs. A minority process is a dynamically changing coloring, where each node repeatedly changes its color to the color which is least frequent in its neighborhood. First, we present a simple Omega(n^2) stabilization time lower bound in the sequential adversarial model. Our main contribution is a graph construction which proves a Omega(n^(2-epsilon)) stabilization time lower bound for any epsilon>0. This lower bound holds even if the order of nodes is chosen benevolently, not only in the sequential model, but also in any reasonable concurrent model of the process.

Cite As Get BibTex

Pál András Papp and Roger Wattenhofer. Stabilization Time in Minority Processes. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.43

Author Details

Pál András Papp
  • ETH Zürich, Switzerland
Roger Wattenhofer
  • ETH Zürich, Switzerland

References

  1. Cristina Bazgan, Zsolt Tuza, and Daniel Vanderpooten. Satisfactory graph partition, variants, and generalizations. European Journal of Operational Research, 206(2):271-280, 2010. Google Scholar
  2. Olivier Bodini, Thomas Fernique, and Damien Regnault. Crystallization by stochastic flips. In Journal of Physics: Conference Series, volume 226, page 012022. IOP Publishing, 2010. Google Scholar
  3. Zhigang Cao and Xiaoguang Yang. The fashion game: Network extension of matching pennies. Theoretical Computer Science, 540:169-181, 2014. Google Scholar
  4. Jacques Demongeot, Julio Aracena, Florence Thuderoz, Thierry-Pascal Baum, and Olivier Cohen. Genetic regulation networks: circuits, regulons and attractors. Comptes Rendus Biologies, 326(2):171-188, 2003. Google Scholar
  5. Silvio Frischknecht, Barbara Keller, and Roger Wattenhofer. Convergence in (social) influence networks. In International Symposium on Distributed Computing, pages 433-446. Springer, 2013. Google Scholar
  6. Bernd Gärtner and Ahad N Zehmakan. Color war: Cellular automata with majority-rule. In International Conference on Language and Automata Theory and Applications, pages 393-404. Springer, 2017. Google Scholar
  7. Bernd Gärtner and Ahad N Zehmakan. Majority model on random regular graphs. In Latin American Symposium on Theoretical Informatics, pages 572-583. Springer, 2018. Google Scholar
  8. Eric Goles and Jorge Olivos. Periodic behaviour of generalized threshold functions. Discrete Mathematics, 30(2):187-189, 1980. Google Scholar
  9. Sandra M Hedetniemi, Stephen T Hedetniemi, KE Kennedy, and Alice A Mcrae. Self-stabilizing algorithms for unfriendly partitions into two disjoint dominating sets. Parallel Processing Letters, 23(01):1350001, 2013. Google Scholar
  10. Dominik Kaaser, Frederik Mallmann-Trenn, and Emanuele Natale. Brief Announcement: On the Voting Time of the Deterministic Majority Process. Distributed, page 647, 2015. Google Scholar
  11. Barbara Keller, David Peleg, and Roger Wattenhofer. How Even Tiny Influence Can Have a Big Impact! In International Conference on Fun with Algorithms, pages 252-263. Springer, 2014. Google Scholar
  12. Jeremy Kun, Brian Powers, and Lev Reyzin. Anti-coordination games and stable graph colorings. In International Symposium on Algorithmic Game Theory, pages 122-133. Springer, 2013. Google Scholar
  13. Pál András Papp and Roger Wattenhofer. Stabilization Time in Weighted Minority Processes. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  14. Damien Regnault, Nicolas Schabanel, and Éric Thierry. Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority. In Luděk Kučera and Antonín Kučera, editors, Mathematical Foundations of Computer Science 2007, pages 320-332. Springer Berlin Heidelberg, 2007. Google Scholar
  15. Damien Regnault, Nicolas Schabanel, and Éric Thierry. On the analysis of “simple” 2d stochastic cellular automata. In International Conference on Language and Automata Theory and Applications, pages 452-463. Springer, 2008. Google Scholar
  16. Jean-Baptiste Rouquier, Damien Regnault, and Éric Thierry. Stochastic minority on graphs. Theoretical Computer Science, 412(30):3947-3963, 2011. Google Scholar
  17. Saharon Shelah and Eric C Milner. Graphs with no unfriendly partitions. A tribute to Paul Erdös, pages 373-384, 1990. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact