  Imagine coating buildings and bridges with smart particles (also coined smart
paint) that monitor structural integrity and sense and report on traffic and
wind loads, leading to technology that could do such inspection jobs faster and
cheaper and increase safety at the same time. In this paper, we study the
problem of uniformly coating objects of arbitrary shape in the context of
self-organizing programmable matter, i.e., programmable matter which consists
of simple computational elements called particles that can establish and
release bonds and can actively move in a self-organized way. Particles are
anonymous, have constant-size memory, and utilize only local interactions in
order to coat an object. We continue the study of our Universal Coating
algorithm by focusing on its runtime analysis, showing that our algorithm
terminates within a linear number of rounds with high probability. We also
present a matching linear lower bound that holds with high probability. We use
this lower bound to show a linear lower bound on the competitive gap between
fully local coating algorithms and coating algorithms that rely on global
information, which implies that our algorithm is also optimal in a competitive
sense. Simulation results show that the competitive ratio of our algorithm may
be better than linear in practice.
