Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2009-02-20
Computer Science
Distributed, Parallel, and Cluster Computing
The extended abstract of this paper won the Best Student Paper Award at DNA 15. The current version has been accepted for publ
Scientific paper
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.
No associations
LandOfFree
Distributed Agreement in Tile Self-Assembly does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distributed Agreement in Tile Self-Assembly, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Agreement in Tile Self-Assembly will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-370155