2026-07-26T00:38:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15949 2024-03-06T10:56:29Z ddc:004 open_access

Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem Berenbrink, Petra Biermeier, Felix Hahn, Christopher Kaaser, Dominik Population Protocols Phase Clocks Loose Self-stabilization Clock Synchronization Majority Adaptive 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petra Berenbrink and Felix Biermeier and Christopher Hahn and Dominik Kaaser 2022 Is Part Of LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2022.7 urn:nbn:de:0030-drops-159493 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.7 eng https://creativecommons.org/licenses/by/4.0/legalcode