Analysis of Distributed Algorithms and Processes in the Population Model

• Applicant: Professorin Dr. Petra Berenbrink
• Subject Area: Theoretical Computer Science
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 491453517

This project focuses on efficient population protocols for fundamental problems in distributed computing. Population protocols have been introduced by Angluin et al. Such a system consists of n anonymous agents. A scheduler selects, in discrete time steps, randomly a pair of agents and these agents are allowed to interact. The interacting agents can execute a state transition, as specified by the ''algorithm'' of the population protocol. In this project we are interested in population protocols solving certain fundamental problems. As an example, consider consensus. At the beginning, each agent possesses one opinion out of k many opinions. The goal is to reach a state where all agents agree on one of the initial opinions. Another example is leader election where the goal is to choose a unique leader. Population protocols are used as a model for chemical reaction networks; there are further interesting relations between population protocols, Petri Nets and vector addition systems. Population protocols can be implemented at the level of DNA molecules, and there are strong similarities between some biochemical regulatory processes in living cells and population protocols. Last but not least, the well-known SIR and SIS models can also be expressed as population protocols.

• DFG Programme: Research Grants
• International Connection: Austria
• Partner Organisation: Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
• Cooperation Partner: Professor Dr. Robert Elsässer