On March 16, 2015, Dr, Jonas Lèfevre will give a talk about "About Population Protocols. Selfstabilizing Algorithms" in the context of the SFB 901.
Abstract:
Population protocols are a computational model for distributed systems where the
agents are equivalent to finite automata, passively mobile and anonymous. The
agents communicate pairwise. The model was introduced in 2004 by Angluin et al.,
and several variants have been studied since then. We determined what sort of formula,
or problem, could be solved by those systems under different sets of constraints such
as: only some pairs of agents can interact, each agent can do some local computation,
some agents trust each other, etc.
At the same time, we consider the distributed matching problem : how to make a group of
people to organize themselves into pairs ? We studied some algorithms proposed by
Manne et al. Based on their work, we built a probabilistic algorithm that constructs a
maximal matching in O(n^3) moves with high probability under the adversarial daemon.
We also studied a 2/3-approximation matching algorithm and proved that its complexity is not polynomial.