LIPIcs.DISC.2020.42.pdf
- Filesize: 359 kB
- 3 pages
Document
Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model
Authors
Emilio Cruciani 
,
Hlafo Alfie Mimun ,
Matteo Quattropani ,
Sara Rizzo
-
Part of:
Volume:
34th International Symposium on Distributed Computing (DISC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-10-07
File
Document Identifiers
Author Details
Cite AsGet BibTex
Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.42
https://doi.org/10.4230/LIPIcs.DISC.2020.42
Abstract
We analyze the binary-state (either ℛ or ℬ) k-majority dynamics in a biased communication model where nodes have some fixed probability p, independent of the dynamics, of being seen in state ℬ by their neighbors. In this setting we study how p, as well as the initial unbalance between the two states, impact on the speed of convergence of the process, identifying sharp phase transitions.
Subject Classification
ACM Subject Classification
- Theory of computation → Random walks and Markov chains
- Theory of computation → Distributed algorithms
- Mathematics of computing → Probabilistic algorithms
- Mathematics of computing → Markov processes
Keywords
- Biased Communication
- Consensus
- Majority Dynamics
- Markov Chains
- Metastability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Luca Becchetti, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. Step-by-step community detection in volume-regular graphs. In ISAAC 2019, pages 20:1-20:23, 2019.
-
Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. SIAM J. Discrete Math., 27(4):1748-1758, 2013.
-
Emilio Cruciani, Emanuele Natale, André Nusser, and Giacomo Scornavacca. Phase transition of the 2-choices dynamics on core-periphery networks. In AAMAS 2018, pages 777-785, 2018.
-
Emilio Cruciani, Emanuele Natale, and Giacomo Scornavacca. Distributed community detection via metastability of the 2-choices dynamics. In AAAI 2019, pages 6046-6053, 2019.
-
Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In PODC 2018, pages 305-313, 2018.
-
Nobutaka Shimizu and Takeharu Shiraga. Phase transitions of best-of-two and best-of-three on stochastic block models. In DISC 2019, pages 32:1-32:17, 2019.