Network Constructors: A Model for Programmable Matter

Michail, Othon ORCID: 0000-0002-6234-3960 and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2017) Network Constructors: A Model for Programmable Matter. In: 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2017-1-16 - 2017-1-20, Lero-Limerick, Ireland.

Text MS17-sofsem.pdf - Author Accepted Manuscript Download (368kB)

Abstract

We discuss recent theoretical models for programmable matter operating in a dynamic environment. In the basic Network Constructors model, all devices are finite automata, begin from the same initial state, execute the same protocol, and can only interact in pairs. The interactions are scheduled by a fair (or uniform random) scheduler, in the spirit of Population Protocols. When two devices interact, the protocol takes as input their states and the state of the connection between them (on/off) and updates all of them. Initially all connections are off. The goal of such protocols is to eventually construct a desired stable network, induced by the edges that are on. We present protocols and lower bounds for several basic network construction problems and also universality results. We next highlight minimal strengthenings of the model, that can be exploited by appropriate network-transformation protocols in order to achieve termination and the maximum computational power that one can hope for in this family of models. Finally, we discuss a more applied version of these abstract models, enriched with geometric constraints, aiming at capturing some first physical restrictions in potential future programmable matter systems operating in dynamic environments.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	27 Oct 2016 16:11
Last Modified:	19 Jan 2023 07:27
DOI:	10.1007/978-3-319-51963-0_3
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3004036