Population Protocols

Population protocols emerged in 2004 as a new theoretical model for describing mobile systems in which the components have sharply limited computational power. The model makes minimal assumptions about many aspects of the system, with the goal of making the model widely applicable, but also tractable for theoretical analysis. Our work on this model has been done in collaboration with researchers from EPFL, Université Paris 7 and Yale University.

Understanding the Model

The first task, now mostly complete, is to understand what can be computed in the model. There are still many open questions about how efficiently problems can be solved in the model, however.

Extending the Model

It turns out that the basic model is fairly weak: it is only capable of solving a fairly small set of problems. How can the understanding of the basic model be extended to stronger models that are more realistic and more powerful?

Fault-Tolerance

In the mobile systems that population protocols are supposed to model, failures of individual components are inevitable. How can algorithms be designed so that they are robust enough to handle failures?