Distributed agreement in tile self-assembly

DOI10.1007/978-3-642-10604-0_16zbMATH Open1213.68127arXiv0902.3631OpenAlexW2900396373MaRDI QIDQ537848FDOQ537848

Aaron Sterling

Publication date: 23 May 2011

Published in: Lecture Notes in Computer Science, Natural Computing (Search for Journal in Brave)

Abstract: Laboratory investigations have shown that a formal theory of fault-tolerance will be essential to harness nanoscale self-assembly as a medium of computation. Several researchers have voiced an intuition that self-assembly phenomena are related to the field of distributed computing. This paper formalizes some of that intuition. We construct tile assembly systems that are able to simulate the solution of the wait-free consensus problem in some distributed systems. (For potential future work, this may allow binding errors in tile assembly to be analyzed, and managed, with positive results in distributed computing, as a "blockage" in our tile assembly model is analogous to a crash failure in a distributed computing model.) We also define a strengthening of the "traditional" consensus problem, to make explicit an expectation about consensus algorithms that is often implicit in distributed computing literature. We show that solution of this strengthened consensus problem can be simulated by a two-dimensional tile assembly model only for two processes, whereas a three-dimensional tile assembly model can simulate its solution in a distributed system with any number of processes.

Full work available at URL: https://arxiv.org/abs/0902.3631

zbMATH Keywords

consensus problemtile self-assemblyconsensus hierarchy

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Cites Work

• The program-size complexity of self-assembled squares (extended abstract)
• Complexity of Self‐Assembled Shapes
• Error suppression mechanisms for DNA tile self-assembly and their simulation
• Impossibility of distributed consensus with one faulty process
• Title not available (Why is that?)
• Reliable cellular automata with self-organization
• Randomized wait-free concurrent objects (extended abstract)
• DNA Computing
• Computability and Complexity in Self-assembly
• A Limit to the Power of Multiple Nucleation in Self-assembly
• Self-assembly of Decidable Sets
• Title not available (Why is that?)
• Strict Self-assembly of Discrete Sierpinski Triangles

Cited In (4)

• Distributed disassembly of mosaics
• An optimal maximal independent set algorithm for bounded-independence graphs
• Distributed agreement in tile self-assembly
• Crystallization and tile separation in the multi-agent systems

   Recommendations

• Distributed agreement in tile self-assembly 👍 👎
• Intrinsic universality in tile self-assembly requires cooperation 👍 👎
• Self-Replication via Tile Self-Assembly (Extended Abstract). 👍 👎
• Asynchronous Signal Passing for Tile Self-assembly: Fuel Efficient Computation and Efficient Assembly of Shapes 👍 👎
• Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes 👍 👎
• Crystallization and tile separation in the multi-agent systems 👍 👎
• Verification in staged tile self-assembly 👍 👎
• Probabilistic Performance Guarantees for Distributed Self-Assembly 👍 👎
• An Introduction to Tile-Based Self-assembly 👍 👎
• Directed non-cooperative tile assembly is decidable 👍 👎

This page was built for publication: Distributed agreement in tile self-assembly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q537848)