BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260824T040756Z
UID:Seminar-networks-645@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20181204T140000
DTEND:20181204T150000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION:Michail Theofilatos: Simple and Fast Approximate Counting and Leader Election in Populations\n\nWe study the problems of leader election and population size counting for population protocols: networks of finite-state anonymous agents that interact randomly under a uniform random scheduler. We provide simple protocols for approximate counting of the size of the population and for leader election. We show a protocol for leader election that terminates in O(log^2(n)/log(m)) parallel time, where 1 <= m <= n is a parameter, using O(max(m, log n)) states. By adjusting the parameter m between a constant and n, we obtain a single leader election protocol whose time and space can be smoothly traded off between O(log^2(n)) to O(log(n)) time and O(log(n)) to O(n) states. We also give a protocol which provides an upper bound n' of the size n of the population, where n' is at most n^a for some constant a>1. This protocol assumes the existence of a unique leader in the population and stabilizes in ?(log(n)) parallel time, using constant number of states in every node, except from the unique leader which is required to use ?(log^2(n)) states.\n\n[Joint work with Othon Michail and Paul G. Spirakis]\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=645
LOCATION:NeST Software Lab
END:VEVENT
END:VCALENDAR