Population Protocols and Predicates
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?