Return to Colloquia & Seminar listing
An optimal population protocol to solve majority
Student-Run Research Seminar| Speaker: | Eric Severson, UC Davis |
| Related Webpage: | https://www.math.ucdavis.edu/~severson/ |
| Location: | Zoom |
| Start time: | Thu, Feb 4 2021, 11:00AM |
The problem: we have a population of finite-state computational agents that all start in state A or state B. At each step, two randomly selected agents will meet, and change their states based on some fixed transition rule (ie.
). One good motivation for this model (population protocols) is as a simple model of chemical reactions (the states of the agents are types of molecules, and agents meeting and changing state is a chemical reaction).
The goal is to reach a configuration where all agents know which state was in the initial majority (ie. determine which opinion would win the election). Given the agents don't have nearly enough memory to count the number of initial As and Bs, it's not obvious they can even solve this problem. But there are ways to solve it, and I'll start with an introduction to the model and describing various protocols that solve this problem. Then I'll introduce some of the ideas behind our recent result (https://arxiv.org/abs/2012.15800), giving a protocol that converges to the correct answer in the asymptotically optimal amount of time, with an anatomically optimal number of states.
Pets welcome, please allow adequate time for parking.