BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260410T025804Z
UID:Seminar-networks-638@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20180315T140000
DTEND:20180315T150000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION:Leszek Gasieniec: Fast Space Optimal Leader Election in Population Protocols\n\nThe model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this paper the emphasis is on the space complexity in fast leader election via population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions from the population of n agents. The main result of this paper is a new fast and space optimal leader election protocol. The new protocol operates in parallel time $O(\log^2 n)$ equivalent to $O(n\log^2 n)$ sequential pairwise interactions, in which each agent utilises $O(\log\log n)$ states. This double logarithmic space utilisation matches asymptotically the lower bound $1/2\log\log n$ on the number of states utilised by agents in any leader election algorithm with the running time $o(n/polylog n)$.\n\nOur solution takes an advantage of the concept of phase clocks, a fundamental synchronisation and coordination tool. We propose a new fast and robust population protocol for initialisation of phase clocks to be run simultaneously in multiple modes and intertwined with the leader election process. We also provide the reader with the relevant formal argumentation indicating that our solution is always correct and fast with high probability.\n\n[JOINT WORK WITH Grzegorz Stachowiak (Wroclaw).]\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=638
LOCATION:
END:VEVENT
END:VCALENDAR