April 25, 2023, 11:47 a.m.
Leszek Gąsieniec (University of Liverpool): Clocking Mechanisms and Synchronisation in Population Protocols with Applications, 25.04, 16:15, sala 25
The lecture by prof. Leszek Gąsieniec (University of Liverpool) will be held on Tuesday 25.04 at 16:15 in room 25 as part of the visiting professors' program "Initiative of Excellence - Research University" (IDUB).
Title:
Clocking Mechanisms and Synchronisation in Population Protocols with Applications
Abstract
The model of population protocols is used to study computational processes based on chaotic
pairwise interactions between ill-equipped anonymous agents belonging to a large population. After
an interaction, the states of the two agents are amended according to the predefined transition
function (the set of rules) which governs the considered computational process. While in search for
efficient solutions most of the randomised (distributed) algorithms strive for the modest utilisation of
randomness, the emphasis in population protocols is on the minimalistic use of states and the rules
to harness fully chaotic behaviour of the system. We will discuss several clocking mechanisms utilised
in population protocols which enable efficient solutions to leader election, majority computation, and
other challenging problems.