License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2022.7
URN: urn:nbn:de:0030-drops-159493
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15949/
Berenbrink, Petra ;
Biermeier, Felix ;
Hahn, Christopher ;
Kaaser, Dominik
Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem
Abstract
We present a loosely-stabilizing phase clock for population protocols. In the population model we are given a system of n identical agents which interact in a sequence of randomly chosen pairs. Our phase clock is leaderless and it requires O(log n) states. It runs forever and is, at any point of time, in a synchronous state w.h.p. When started in an arbitrary configuration, it recovers rapidly and enters a synchronous configuration within O(n log n) interactions w.h.p. Once the clock is synchronized, it stays in a synchronous configuration for at least poly(n) parallel time w.h.p.
We use our clock to design a loosely-stabilizing protocol that solves the adaptive variant of the majority problem. We assume that the agents have either opinion A or B or they are undecided and agents can change their opinion at a rate of 1/n. The goal is to keep track which of the two opinions is (momentarily) the majority. We show that if the majority has a support of at least Ω(log n) agents and a sufficiently large bias is present, then the protocol converges to a correct output within O(n log n) interactions and stays in a correct configuration for poly(n) interactions, w.h.p.
BibTeX - Entry
@InProceedings{berenbrink_et_al:LIPIcs.SAND.2022.7,
author = {Berenbrink, Petra and Biermeier, Felix and Hahn, Christopher and Kaaser, Dominik},
title = {{Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem}},
booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
pages = {7:1--7:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-224-2},
ISSN = {1868-8969},
year = {2022},
volume = {221},
editor = {Aspnes, James and Michail, Othon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15949},
URN = {urn:nbn:de:0030-drops-159493},
doi = {10.4230/LIPIcs.SAND.2022.7},
annote = {Keywords: Population Protocols, Phase Clocks, Loose Self-stabilization, Clock Synchronization, Majority, Adaptive}
}
|
Keywords: |
|
Population Protocols, Phase Clocks, Loose Self-stabilization, Clock Synchronization, Majority, Adaptive |
|
Collection: |
|
1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
29.04.2022 |
