Computer Science - Spatial Population Protocols

Supervisor: Prof Leszek Gasieniec

Supervisor bio: 

Prof Leszek Antoni Gasieniec, PhD (1994) in Computer Science, Warsaw University, Poland. Postdocs at Université du Québec à Hull in Canada (94-95), and Max-Planck Institut für Informatik in Saarbruecken, Germany (95-97). He has been with the University of Liverpool since October 1997 becoming full professor in 2003. He was the Head of Computer Science Department in years 2012-2015. The main research strand of Prof Gasieniec’s research explorations is in the design and analysis of efficient algorithms for combinatorial problems, with a special interest in Distributed Algorithms, Networks, and Search Problems.

Email: l.a.gasieniec@liverpool.ac.uk

School: School of Computer Science and Informatics 

Department: Computer Science

Module code: COMP298

Suitable for students of: This project primarily targets Computer Science students with a solid background in Python (or another programming language) and familiarity with random processes. However, students from other disciplines are also warmly welcome, provided they are open-minded and eager to engage with computational challenges.

Desirable experience/requirements: 

Ideally, the student has some prior experience with programming and experimental work. That said, students who wish to contribute expertise from their own discipline (e.g., mathematics, physics, robotics, or biology) to the study of population protocols are also very welcome and strongly encouraged to apply.

Places available: 2

Start date: Session 1 (15th June 2026)

Project length: 8 weeks 

Virtual option: Yes

Hybrid option: Yes

Project description: 

The population protocol model, introduced by Angluin et al. [1], enables stable computation through pairwise interactions among anonymous, finite-state agents. Its key elements include: a population of n agents, a transition function governing state updates during interactions, and a scheduler dictating the sequence of these interactions.

In the probabilistic variant adopted here, a random scheduler selects ordered (initiator, responder) pairs uniformly at random, injecting inherent randomness into the system. Protocols fall into two categories: self-stabilising (capable of recovering from arbitrary initial states) and non-self-stabilising (relying on predefined valid inputs). Successful protocols converge to a stable configuration that encodes the solution to the given problem.

Contemporary analysis prioritises parallel time, defined as the total number of interactions divided by n, with efficient protocols achieving O(polylog n) parallel time with high probability (whp). Essential properties include correctness (always producing valid outputs), silent stabilisation (no further state changes post-convergence), and rapid convergence whp.

Building on this foundation, Gasieniec et al. [2] recently proposed spatial population protocols, a novel extension that augments the transition function with geometric queries. Interacting agents can thus obtain either exact pairwise distances (distance-query model) or complete relative position vectors (vector-query model) in Euclidean space.

The primary contribution in [2] is a family of self-stabilising, silent protocols for the distributed localisation problem. These enable n anonymous agents, starting from inconsistent local coordinate systems, to agree on a unified global coordinate frame that preserves all relative distances. Achieved bounds include o(n) parallel time in the distance-query model and optimal O(log n) in the vector-query model. The work underscores practical potential for lightweight, robust protocols in real-world applications like robotic swarms, while highlighting open challenges: accommodating measurement errors (e.g., via bounding label drifting), handling limited communication ranges, supporting agent mobility, and investigating the model's broader computational power.

This project directly addresses these open problems from [2], aiming to develop enhanced protocols that incorporate error tolerance, restricted topologies, and dynamic movement, thereby advancing fault-resilient spatial computing.

References
[1] D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and N. A. Lynch. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235–253, 2006.
[2] L. A. Gasieniec, ?. Kuszner, E. Latif, R. Parasuraman, P. Spirakis, and G. Stachowiak. Anonymous Self-Stabilising Localisation via Spatial Population Protocols. In Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC), 2025.

Additional requirements: N/A