Self-Stabilizing Phase Clocks and the Adaptive Majority Problem

22^nd July 2021, 12:00
Petra Berenbrink
Hamburg University

Abstract

We present a loosely stabilising 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(log n) parallel time 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 self-stabilizing protocol that solves the comparison problem introduced by Alistarh et al., 2021. In this problem, a subset of agents has at any time either A or B as input. The goal is to keep track which of the two opinions is (momentarily) the majority. We show that if the initial majority has a support of at least Omega(log n) agents and a sufficiently large bias is present, then the protocol converges to a correct output within $O(\log n)$ time and stays in a correct configuration for poly(n) time, w.h.p.

Joint work with Felix Biermeier, Christopher Hahn and Dominik Kaaaser