BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260910T030130Z
UID:Seminar-networks-1139@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20210722T120000
DTEND:20210722T130000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION:Petra Berenbrink: Self-Stabilizing Phase Clocks and the Adaptive Majority Problem\n\nWe 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.\nIt 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.\nOnce the clock is synchronized, it stays in a synchronous configuration for at least $\poly n$ parallel time w.h.p.\n\nWe 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.\n\nJoint work with Felix Biermeier, Christopher Hahn and Dominik Kaaaser\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1139
LOCATION:
END:VEVENT
END:VCALENDAR