  Perhaps the two most significant theoretical questions about the programming
of self-assembling agents are: (1) necessary and sufficient conditions to
produce a unique terminal assembly, and (2) error correction. We address both
questions, by reducing two well-studied models of tile assembly to models of
distributed shared memory (DSM), in order to obtain results from the memory
consistency systems induced by tile assembly systems when simulated in the DSM
setting. The Abstract Tile Assembly Model (aTAM) can be simulated by a DSM
system that obeys causal consistency, and the locally deterministic tile
assembly systems in the aTAM correspond exactly to the concurrent-write free
programs that simulate tile assembly in such a model. Thus, the detection of
the failure of local determinism (which had formerly been an open problem)
reduces to the detection of data races in simulating programs. Further, the
Kinetic Tile Assembly Model can be simulated by a DSM system that obeys GWO, a
memory consistency condition defined by Steinke and Nutt. (To our knowledge,
this is the first natural example of a DSM system that obeys GWO, but no
stronger consistency condition.) We combine these results with the observation
that self-assembly algorithms are local algorithms, and there exists a fast
conversion of deterministic local algorithms into deterministic
self-stabilizing algorithms. This provides an "immediate" generalization of a
theorem by Soloveichik et al. about the existence of tile assembly systems that
simultaneously perform two forms of self-stabilization: proofreading and
self-healing. Our reductions and proof techniques can be extended to the
programming of self-assembling agents in a variety of media, not just DNA
tiles, and not just two-dimensional surfaces.
