License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.54
URN: urn:nbn:de:0030-drops-102938
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10293/
Go to the corresponding LIPIcs Volume Portal

Papp, Pál András ; Wattenhofer, Roger

Stabilization Time in Weighted Minority Processes

pdf-format:
LIPIcs-STACS-2019-54.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{papp_et_al:LIPIcs:2019:10293,
  author =	{P{\'a}l Andr{\'a}s Papp and Roger Wattenhofer},
  title =	{{Stabilization Time in Weighted Minority Processes}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{54:1--54:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10293},
  doi =		{10.4230/LIPIcs.STACS.2019.54},
  annote =	{Keywords: Minority process, Benevolent model}
}

Keywords: Minority process, Benevolent model
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI