Self-stabilizing Population Protocols

Population protocols model distributed systems of mobile anonymous entities having no control over their movements. The entities interact in pairs in an opportunistic way. In an interaction, the two entities exchange and update their internal states, according to the protocol. This model has proven to be useful for modeling networks in various domains, like those of wireless sensors, social networks, and even chemical reaction and gene regulatory networks. Such networks are inherently unreliable and have limited resources.

Focusing on resources of memory and time, we will discuss how efficiently tasks can be solved when facing transient faults modeled by means of self-stabilization. The talk will give an overview of the related work and focus on several fundamental tasks like counting, naming, and leader election.