Population Protocols and Predicates

Pierre Ganty
IMDEA
Friday, 27 April, 2018 - 14:00
ULB La Plaine NO, Salle Solvay

In populations protocols, identical, anonymous, finite-state processes interact pairwise through rendez-vous synchronization. Angluin et al. (PODC 2004) introduced population protocols as a distributed computation model. In that context, an interesting subclass of protocols are the ones computing predicates. Intuitively, a population protocol computes a predicate Φ(N) as follows: instantiate the protocol with N processes and let them interact until they reach a stable unanimity on value true or false. I will present results relative to three natural questions:

  • does this protocol computes a predicate?
  • does this protocol computes this predicate?
  • what predicate does this protocol compute?