research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleTerminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata
Bibtex cite IDRACTI-RU1-2015-4
Booktitle 34th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)
Year published 2015
Month July
Pages 37-46
Publisher ACM
Location Donostia-San Sebastián, Spain
Keywords distributed network construction,programmable matter,shape formation,well-mixed solution,homogeneous population,distributed protocol,interacting automata,fairness,random schedule,structure formation,self-organization,self-replication
In this work, we consider a \emphsolution of automata similar to \emphPopulation Protocols and \emphNetwork Constructors. The automata (also called \emphnodes) move passively in a well-mixed solution without being capable of controlling their movement. However, the nodes can \emphcooperate by interacting in pairs. Every such interaction may result in an update of the local states of the nodes. Additionally, the nodes may also choose to connect to each other in order to start forming some required structure. We may think of such nodes as the \emphsmallest possible programmable pieces of matter, like tiny nanorobots or programmable molecules. The model that we introduce here is a more applied version of Network Constructors, imposing \emphphysical (or \emphgeometrical) \emphconstraints on the connections that the nodes are allowed to form. Each node can connect to other nodes only via a very limited number of \emphlocal ports, which implies that at any given time it has only a \emphbounded number of neighbors. Connections are always made at \emphunit distance and are \emphperpendicular to connections of neighboring ports. Though such a model cannot form abstract networks like Network Constructors, it is still capable of forming very practical \emph2D or 3D shapes. We provide direct constructors for some basic shape construction problems, like \emphspanning line, \emphspanning square, and \emphself-replication. We then develop \emphnew techniques for determining the computational and constructive capabilities of our model. One of the main novelties of our approach, concerns our attempt to overcome the inability of such systems to detect termination. In particular, we exploit the assumptions that the system is well-mixed and has a unique leader, in order to \emphgive terminating protocols that are correct with high probability. This allows us to develop terminating subroutines that can be \emphsequentially composed to form larger \emphmodular protocols (which has not been the case in the relevant literature). One of our main results is a \emphterminating protocol counting the size $n$ of the system with high probability. We then use this protocol as a subroutine in order to develop our \emphuniversal constructors, establishing that \emphit is possible for the nodes to become self-organized with high probability into arbitrarily complex shapes while still detecting termination of the construction.
Michail, Othon
Mi15-PODC.pdf (main file)
Publication ID1077