https://us02web.zoom.us/j/88018185733?pwd=OEcxb2ZSYUwzV2hWTE9wcE1yTWRUQT09
Passcode: 279596
In-person: Hamilton Institute Seminar room (317), 3rd Floor Eolas Building, North Campus, Maynooth University
Speaker: Professor David Doty, University of California, Davis
Title: "Time-optimal self-stabilizing leader election in population protocols"
Abstract: We consider the population protocol model, where a priori indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. This is a widely-used model that closely approximates the behavior of interacting molecules in a well-mixed solution. The self-stabilizing leader election problem requires the protocol to "elect a leader" among a population of n agents in an extremely fault-tolerant manner: to converge on a single leader agent from any possible initial setting of the memory of the agents. We study the time and memory complexity of this problem. The only previously known protocol runs in expected time Θ(n2) and has the optimal number of n memory states in a population of n agents. The existing protocol has the additional property that it becomes silent, i.e., the agents' states eventually stop changing.
Observing that any silent protocol solving self-stabilizing leader election requires Ω(n) expected time, we introduce a silent protocol that uses optimal O(n) time and states. Without any silence constraints, we show that it is possible to solve self-stabilizing leader election in asymptotically optimal expected time of O(log n), but using at least exponential states (a quasi-polynomial number of bits of memory). All of our protocols work by solving the more difficult ranking problem: assigning agents the ranks 1,…,n.
Bio: David Doty is an associate professor of Computer Science at the University of California, Davis. He is broadly interested in problems at the intersection of physics, chemistry, biology, and computation. This does not mean the traditional "computation in service of natural science" (e.g., bioinformatics, computational chemistry, or molecular dynamics simulation). Rather, certain molecular systems — such as a test tube of reacting chemicals, a genetic regulatory network, or a growing crystal — can be interpreted as doing computation themselves... natural science in service of computation. He seeks to understand the fundamental logical and physical limits to computation by such means.