# Events

## Talk given by Dr. Jonas Lèfevre (University of Nice, Sophia Antipolis)

Begin: Mon, 16. of Mar 2015 ( 2:15 PM)Location: Fürstenallee, Room F1.110

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.