Kolloquium SoSe 2021
Die Veranstaltung wird verschoben./
The event is postponed.
Speaker
Prof. Dr. Petra Berenbrink
Universität Hamburg
Algorithmen, Randomisierung, Theorie (ART)
When: Mo, 21.06.2021, at 17:15
Online-Zoom-Meeting
You will receive the registration data via an email invitation. Please register for this at https://mailhost.informatik.uni-hamburg.de/mailman/listinfo/kolloquium.
Topic
Simple information spreading processes
Language: english
Abstract
In this talk I will give an overview about my research in the area of information spreading processes in populations. We have an anonymous population of unknown size. The agents are modelled as finite state machines (in many cases as ''small state machines''). In synchronous time steps two randomly chosen agents communicate with each other, exchange their states and update their own state accordingly. These models have many applications, for example they can be used to study the behaviour of a flogs of birds, the spread of SIR processes, chemical reaction networks ...
One example we will consider are so-called consensus processes. Initially each node supports one of a set of possible opinions. Agents randomly and in parallel sample the opinions of constant many agents. Based on these samples, they use a simple update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion.
A related problem is the majority problem where the agents initially support one opinion and now the goal is to calculate the opinion with the largest support.
Other examples are leader election where the goal is to elect a unique leader or a junta of size $n^{\epsilon}$, or counting/approximating the size of the population.