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.ISAAC.2019.43
URN: urn:nbn:de:0030-drops-115393
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11539/
Papp, Pál András ;
Wattenhofer, Roger
Stabilization Time in Minority Processes
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.
BibTeX - Entry
@InProceedings{papp_et_al:LIPIcs:2019:11539,
author = {P{\'a}l Andr{\'a}s Papp and Roger Wattenhofer},
title = {{Stabilization Time in Minority Processes}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {43:1--43:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11539},
URN = {urn:nbn:de:0030-drops-115393},
doi = {10.4230/LIPIcs.ISAAC.2019.43},
annote = {Keywords: Minority process, Benevolent model}
}
|
Keywords: |
|
Minority process, Benevolent model |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
