Distributed complexity of stochastic spatial coordination

• Applicant: Professor Dr. Joel Rybicki
• Subject Area: Theoretical Computer Science
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 539576251

This project investigates what can be efficiently computed in stochastic distributed systems that comprise resource-limited computational entities. Specifically, we investigate the computational complexity of various distributed coordination problems and spatial dynamics that arise in the design of spatially-structured stochastic biological distributed systems, such as engineered microbial circuits. To this end, we consider the so-called spatial population model, where the system is described by an interaction graph in which each node represents an individual and edges denote pairs of individuals that can directly interact with each other. In each time step, a stochastic scheduler randomly picks a pair of adjacent individuals to interact and update their internal states. Previously, the complexity of stochastic coordination problems in this model has been mainly studied in the special case where the interaction graph is a clique. This corresponds to the setting of well-mixed chemical systems that follow the law of mass action kinetics: the spatial locations of individuals are ignored and any two individuals have the same probability to directly interact. While this is a plausible assumption for modelling molecular computation in chemical reaction networks, most biological systems are not well-mixed, as they exhibit strong spatial structure. In this project, we move beyond well-mixed systems and develop a theory of computational complexity in stochastic, spatially-structured populations. We systematically investigate how spatial structure influences computational complexity trade-offs for solving fundamental distributed coordination problems. In particular, we aim to explain which signal amplification and symmetry breaking problems can and cannot be solved fast by simple, resource-efficient algorithms.

• DFG Programme: Research Grants