Colloquium


Population protocols, clocking mechanisms, and applications

The model of population protocols is used to study computational processes based on chaotic pairwise interactions between ill-equipped anonymous agents belonging to a large population. After an interaction, the states of the two agents are amended according to the predefined transition function (the set of rules) which governs the considered computational process. While in search for efficient solutions most of the randomized (distributed) algorithms strive for the modest utilization of randomness, the emphasis in population protocols is on the minimalistic use of states and the rules to harness fully chaotic behavior of the system. We will discuss several clocking mechanisms utilized in population protocols which enable efficient solutions to leader election, majority computation, and other challenging problems.