
In systems of programmable matter, we are given a collection of simple
computation elements (or particles) with limited (constantsize) memory. We are
interested in when they can selforganize to solve systemwide problems of
movement, configuration and coordination. Here, we initiate a stochastic
approach to developing robust distributed algorithms for programmable matter
systems using Markov chains. We are able to leverage the wealth of prior work
in Markov chains and related areas to design and rigorously analyze our
distributed algorithms and show that they have several desirable properties.
We study the compression problem, in which a particle system must gather as
tightly together as possible, as in a sphere or its equivalent in the presence
of some underlying geometry. More specifically, we seek fully distributed,
local, and asynchronous algorithms that lead the system to converge to a
configuration with small boundary. We present a Markov chainbased algorithm
that solves the compression problem under the geometric amoebot model, for
particle systems that begin in a connected configuration. The algorithm takes
as input a bias parameter $\lambda$, where $\lambda > 1$ corresponds to
particles favoring having more neighbors. We show that for all $\lambda >
2+\sqrt{2}$, there is a constant $\alpha > 1$ such that eventually with all but
exponentially small probability the particles are $\alpha$compressed, meaning
the perimeter of the system configuration is at most $\alpha \cdot p_{min}$,
where $p_{min}$ is the minimum possible perimeter of the particle system.
Surprisingly, the same algorithm can also be used for expansion when $0 <
\lambda < 2.17$, and we prove similar results about expansion for values of
$\lambda$ in this range. This is counterintuitive as it shows that particles
preferring to be next to each other ($\lambda > 1$) is not sufficient to
guarantee compression.

In a selforganizing particle system, an abstraction of programmable matter,
simple computational elements called particles with limited memory and
communication selforganize to solve systemwide problems of movement,
coordination, and configuration. In this paper, we consider a stochastic,
distributed, local, asynchronous algorithm for "shortcut bridging", in which
particles selfassemble bridges over gaps that simultaneously balance
minimizing the length and cost of the bridge. Army ants of the genus Eciton
have been observed exhibiting a similar behavior in their foraging trails,
dynamically adjusting their bridges to satisfy an efficiency tradeoff using
local interactions. Using techniques from Markov chain analysis, we rigorously
analyze our algorithm, show it achieves a nearoptimal balance between the
competing factors of path length and bridge cost, and prove that it exhibits a
dependence on the angle of the gap being "shortcut" similar to that of the ant
bridges. We also present simulation results that qualitatively compare our
algorithm with the army ant bridging behavior. Our work gives a plausible
explanation of how convergence to globally optimal configurations can be
achieved via local interactions by simple organisms (e.g., ants) with some
limited computational power and access to random bits. The proposed algorithm
also demonstrates the robustness of the stochastic approach to algorithms for
programmable matter, as it is a surprisingly simple extension of our previous
stochastic algorithm for compression.

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
selforganizing 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 selforganized way. Particles are
anonymous, have constantsize 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.

We consider programmable matter that consists of computationally limited
devices (called particles) that are able to selforganize in order to achieve
some collective goal without the need for central control or external
intervention. We use the geometric amoebot model to describe such
selforganizing particle systems, which defines how particles can actively move
and communicate with one another. In this paper, we present an efficient
localcontrol algorithm which solves the leader election problem in O(n)
asynchronous rounds with high probability, where n is the number of particles
in the system. Our algorithm relies only on local information  particles do
not have unique identifiers, any knowledge of n, or any sort of global
coordinate system  and requires only constant memory per particle.

We consider programmable matter consisting of simple computational elements,
called particles, that can establish and release bonds and can actively move in
a selforganized way, and we investigate the feasibility of solving fundamental
problems relevant for programmable matter. As a suitable model for such
selforganizing particle systems, we will use a generalization of the geometric
amoebot model first proposed in SPAA 2014. Based on the geometric model, we
present efficient localcontrol algorithms for leader election and line
formation requiring only particles with constant size memory, and we also
discuss the limitations of solving these problems within the general amoebot
model.