Speaker: Eric Severson, University of California at Davis
https://www.math.ucdavis.edu/~severson/

Abstract:

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.

Bio:

Eric Severson is a PhD candidate in the UC Davis Graduate Group in
Applied Mathematics, working with Professor David Doty.