Population protocols

Abstract

opulation protocols are a model of distributed computation in which anonymous finite-state agents perform a computation by converging to a common output value via two-way interactions. Though the model is simple, population protocols have a rich mathematical structure. I will give an overview of the model; discuss the computational power of population protocols subject to various assumptions about which agents can interact; and describe recent results on fast computation by randomized population protocols, a version of the model corresponding to well-mixed chemical solutions.

This talk describes joint work with Dana Angluin, Melody Chan, Zoë Diamadi, David Eisenstat, Michael J. Fischer, Hong Jiang, René Peralta, and Eric Ruppert.