Models and Algorithms for Systems of Programmable Particles

The project will investigate the algorithmic framework necessary for the development of systems of programmable particles. These are roughly systems of tiny and computationally weak entities equipped with computing and possibly also actuation capabilities. Additionally, some of these systems are typically highly dynamic both in space and time. During the project the student is expected to explore topics from the related areas of Population Protocols and Network Constructors, Dynamic Networks, Discrete Dynamic Systems, and Algorithmic properties of Programmable Matter. This research has the potential to reveal new modes of computing as well as to establish novel computability and complexity insights.

The student apart from working on existing models and problems from the state of the art will have the opportunity to develop a set of novel reasonable models that capture well essential parameters of emerging and future systems. The student will be able to enhance those models through our close collaboration with experts from EEE and Mechanical Engineering. For each of these models, we shall explore adaptations of existing problems as well as identify and formulate naturally occurring new problems, investigate feasibility and efficiency questions, develop a wide range of centralised and distributed algorithms, and consider relationships between the various models (e.g., through simulation relations, characterisations, and complexity classes). Our solutions shall be extensively tested analytically and through simulations and visualization. Another PhD student (based in the EEE Department, member of our team) will be working in parallel on the design and implementation of a real system corresponding to the best model predicted by our theoretical framework, so the two students are expected to form a team.

The project will study models of both actively-mobile and passively-mobile systems of programmable particles. As part of the latter direction, it shall be investigated how recent techniques from the area of dynamic networks can be applied in programmable matter models.

The aforementioned opportunity to interact with academics from Electrical Engineering, and Electronics and Mechanical Engineering will enable the student to form a global perspective and arrive at more realistic models. It is also anticipated that a collaboration with the Virtual Engineering Centre at Daresbury and the NeST initiative of the Computer Science department shall be established during the project.

Candidates should have completed a BSc degree in Computer Science (preferably 1st class, i.e. 70%+, but upper second class, i.e. 60-69%, shall also be considered) or other closely related field, be passionate and highly motivated for pursuing a PhD in Computer Science and to have a strong relevant background (example topics: sequential/distributed algorithms, computability/complexity theory, modelling computing systems, graphs/networks, analysis and formal proofs). Holding an MSc in Computer Science or other closely related field is not necessary for applying to this position (but will be taken into account). Candidates are also expected to have reasonable programming skills, to be willing to get involved in interdisciplinary collaborations which are already in place, and to acquire new knowledge ranging from theoretical aspects to applied issues and experimentation.