Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

How to Stably Elect a Leader from a Corrupted Population

Student-Run Research Seminar

Speaker: Eric Severson, UC Davis
Location: 3106 MSB
Start time: Tue, Oct 8 2019, 12:30PM

The population protocols model describes a population of simple anonymous computational agents that undergo asynchronous random pairwise interactions. To solve the leader election problem, the population must converge to a configuration where a single agent has permanently adopted a "leader" role. We study this problem in the self-stabilizing regime, where the protocol must work from any possible initial configuration (ie. the starting memory of all the agents can be chosen adversarially). A simple protocol was already known for a population of $n$ agents, using $n$ memory states and taking an expected $\Theta(n^3)$ number of interactions to converge. Our work explores the tradeoff in time / space complexity for this problem, by describing three different protocols that are progressively more efficient in terms of convergence time but less efficient in terms of memory.

This is joint work with Janna Burman, David Doty, Thomas Nowak, and Chuan Xu. The preprint "Efficient self-stabilizing leader election in population protocols" is at https://arxiv.org/abs/1907.06068.



Please note the special time and location.