Probabilistic Performance Guarantees for Distributed Self-Assembly

Michael J. Fox, Jeff S. Shamma

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


In distributed self-assembly, a multitude of agents seek to form copies of a particular structure, modeled here as a labeled graph. In the model, agents encounter each other in spontaneous pairwise interactions and decide whether or not to form or sever edges based on their two labels and a fixed set of local interaction rules described by a graph grammar. The objective is to converge on a graph with a maximum number of copies of a given target graph. Our main result is the introduction of a simple algorithm that achieves an asymptotically maximum yield in a probabilistic sense. Notably, agents do not need to update their labels except when forming or severing edges. This contrasts with certain existing approaches that exploit information propagating rules, effectively addressing the decision problem at the level of subgraphs as opposed to individual vertices. We are able to obey more stringent locality requirements while also providing smaller rule sets. The results can be improved upon if certain requirements on the labels are relaxed. We discuss limits of performance in self-assembly in terms of rule set characteristics and achievable maximum yield.
Original languageEnglish (US)
Pages (from-to)3180-3194
Number of pages15
JournalIEEE Transactions on Automatic Control
Issue number12
StatePublished - Apr 1 2015

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01


Dive into the research topics of 'Probabilistic Performance Guarantees for Distributed Self-Assembly'. Together they form a unique fingerprint.

Cite this