  Majumder, Reif and Sahu have presented a stochastic model of reversible,
error-permitting, two-dimensional tile self-assembly, and showed that
restricted classes of tile assembly systems achieved equilibrium in (expected)
polynomial time. One open question they asked was how much computational power
would be added if the model permitted multiple nucleation, i.e., independent
groups of tiles growing before attaching to the original seed assembly. This
paper provides a partial answer, by proving that if a tile assembly model uses
only local binding rules, then it cannot use multiple nucleation on a surface
to solve certain "simple" problems in constant time (time independent of the
size of the surface). Moreover, this time bound applies to macroscale robotic
systems that assemble in a three-dimensional grid, not just to tile assembly
systems on a two-dimensional surface. The proof technique defines a new model
of distributed computing that simulates tile (and robotic) self-assembly.
Keywords: self-assembly, multiple nucleation, locally checkable labeling.
