Abstract:
We will discuss one of the models in distributed computing called "population protocols". From the logical viewpoint, population protocols are interesting due to their connection to Presburger Arithmetic. More specifically, in the works of Angluin et al. it was proved that the set of predicates that are definable in the Presburger arithmetic coincides with the set of predicates computable by population protocols.
During the talk, we will define the model, then we will state and discuss the result of Angluin et al., and finally, we will survey some modern research directions in this area.