Stabilization Time in Weighted Minority Processes
OPEN ACCESS
Author / Producer
Date
2019-03
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
A minority process in a weighted graph is a dynamically changing coloring. Each node repeatedly changes its color in order to minimize the sum of weighted conflicts with its neighbors. We study the number of steps until such a process stabilizes. Our main contribution is an exponential lower bound on stabilization time. We first present a construction showing this bound in the adversarial sequential model, and then we show how to extend the construction to establish the same bound in the benevolent sequential model, as well as in any reasonable concurrent model. Furthermore, we show that the stabilization time of our construction remains exponential even for very strict switching conditions, namely, if a node only changes color when almost all (i.e., any specific fraction) of its neighbors have the same color. Our lower bound works in a wide range of settings, both for node-weighted and edge-weighted graphs, or if we restrict minority processes to the class of sparse graphs.
Permanent link
Publication status
published
External links
Book title
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Volume
126
Pages / Article No.
54
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Minority process; Benevolent model
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger