Show simple item record

dc.contributor.author
Papp, Pál A.
dc.contributor.author
Wattenhofer, Roger
dc.contributor.editor
Niedermeier, Rolf
dc.contributor.editor
Paul, Christophe
dc.date.accessioned
2019-08-14T10:56:45Z
dc.date.available
2019-04-01T12:17:29Z
dc.date.available
2019-04-01T13:08:02Z
dc.date.available
2019-08-14T10:56:45Z
dc.date.issued
2019-03
dc.identifier.isbn
978-3-95977-100-9
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.STACS.2019.54
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/335198
dc.identifier.doi
10.3929/ethz-b-000335198
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Minority process
en_US
dc.subject
Benevolent model
en_US
dc.title
Stabilization Time in Weighted Minority Processes
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
126
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
54
en_US
ethz.size
15 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
en_US
ethz.event.location
Berlin, Germany
en_US
ethz.event.date
March 13-16, 2019
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
en_US
ethz.date.deposited
2019-04-01T12:17:40Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2019-04-01T13:08:16Z
ethz.rosetta.lastUpdated
2024-02-02T08:41:33Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Stabilization%20Time%20in%20Weighted%20Minority%20Processes&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2019-03&rft.volume=126&rft.spage=54&rft.issn=1868-8969&rft.au=Papp,%20P%C3%A1l%20A.&Wattenhofer,%20Roger&rft.isbn=978-3-95977-100-9&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPIcs.STACS.2019.54&rft.btitle=36th%20International%20Symposium%20on%20Theoretical%20Aspects%20of%20Computer%20Science%20(STACS%202019)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record