  We consider the problem of completely covering an unknown discrete
environment with a swarm of asynchronous, frequently-crashing autonomous mobile
robots. We represent the environment by a discrete graph, and task the robots
with occupying every vertex and with constructing an implicit distributed
spanning tree of the graph. The robotic agents activate independently at random
exponential waiting times of mean $1$ and enter the graph environment over time
from a source location. They grow the environment's coverage by 'settling' at
empty locations and aiding other robots' navigation from these locations. The
robots are identical and make decisions driven by the same simple and local
rule of behaviour. The local rule is based only on the presence of neighbouring
robots, and on whether a settled robot points to the current location. Whenever
a robot moves, it may crash and disappear from the environment. Each vertex in
the environment has limited physical space, so robots frequently obstruct each
other.
  Our goal is to show that even under conditions of asynchronicity, frequent
crashing, and limited physical space, the simple mobile robots complete their
mission in linear time asymptotically almost surely, and time to completion
degrades gracefully with the frequency of the crashes. Our model and analysis
are based on the well-studied "totally asymmetric simple exclusion process" in
statistical mechanics.
