ABSTRACT


Population protocols are a model of distributed computation in which anonymous finitestate agents perform a computation by converging to a common output value via twoway 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 wellmixed 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. Return to DMTCS home page. 