Mobility Matters
Home›Programmable matter›Self-organising particle systems›Coating

Coating

Particles must cover a fixed object as uniformly as possible: in layers, each filled before the next.

Problem statement and measurescollapse
Start: roots touch the object; arrows point to parentsRoots walk clockwise along the first layerHandover: the parent contracts, its child expandsFinal: the first layer is filled
Coating, following Derakhshandeh et al. 2017: particles that neighbour the object (black) are roots, the others follow a parent closer to the object (forming trees). Roots walk clockwise along the first layer, one expansion and one contraction per node; when an expanded particle contracts, its child expands into the node it leaves (a handover), so the trees are pulled along without breaking. With as many particles as first-layer nodes, the walk ends when every node that neighbours the object is occupied (green); further particles would start the next layer.

A fixed object (a connected set of nodes of the triangular lattice that particles cannot enter) is surrounded by particles. They must arrange themselves into layers around the object, each layer filled before the next. Time in rounds; work is the number of moves (expansions and contractions).

Measures: Time, asynchronous rounds; Moves, total expansions and contractions (work).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine ants covering a crumb, one even layer at a time. The floor is the triangular lattice: the endless graph whose nodes are the corners of a tiling of the plane by equal triangles; each node is joined by an edge to six others, its neighbours. A particle is a tiny machine that occupies one node; it moves in two actions: an expansion into an empty neighbouring node, after which it is expanded and occupies both, then a contraction into one of the two; so one expansion and one contraction move it by one node, and each of them is one move. The object is a connected set of nodes that particles cannot enter; \(n\) particles, connected to each other and to the object, sit around it. They must arrange themselves into layers around the object: the first layer (the nodes that neighbour the object) must be full before any particle sits in the second, and so on, with any extra particles in the last layer. In the standard version particles have constant memory, agree on which way is clockwise (chirality), and may flip coins; we count rounds (intervals of time in which every particle is activated at least once) and work (the total number of moves).

1AlgorithmFollow the leader around the object, layer by layer Universal coating → Derakhshandeh et al. 2017

The particles move in handovers: an expanded particle contracts and at the same moment pulls a neighbour into the node it vacates, so the chain of particles never breaks.

  1. Particles that neighbour the object become roots; every other particle picks a neighbour closer to the object as its parent, so the particles form trees hanging off the object.
  2. Roots walk clockwise around the object along the first layer; followers trail behind their parents by handovers.
  3. A root that bumps into a particle that has already stopped stops too (it retires). A follower that still wants a node in the layer sends a 'complaint' to a root with free space ahead, which then moves on and makes room.
  4. A leader, elected among the particles of the first layer, marks where the layer begins and ends. When the first layer is full, the next layer starts from that mark, and so on.
Why it works and what it costs. In the worst case the total work is \(\Theta(n^2)\), which matches the lower bound below Derakhshandeh et al. 2017. The running time is \(O(n)\) rounds with high probability Daymude et al. 2018; the coins are needed only for the leader election, and \(O(n)\) is the best possible in the worst case. Particles with no memory and no messages can still coat a convex object with one layer, in \(O(n^2)\) rounds Navarra & Piselli 2023.

Why it matters. Spanning trees plus handovers became the standard way to move all the particles without ever disconnecting them.

2Lower boundA long tail of particles Universal coating → Daymude et al. 2018

Put all \(n\) particles in one straight line that meets the object only at its first particle, and let the first layer have more than \(n\) nodes. The particle at distance \(i\) from the object must end as a neighbour of it, so it must travel about \(i\) nodes, which takes about \(2i\) moves. The last particle is at distance \(n\), and an unkind scheduler may let it act only once per round.

Why it holds. The last particle needs about \(n\) moves at one move per round, so every algorithm needs \(\Omega(n)\) rounds in the worst case Daymude et al. 2018. Adding the distances, \(2(1+2+\dots+(n-1)) \approx n^2\), so every algorithm needs \(\Omega(n^2)\) work Derakhshandeh et al. 2017. Both bounds are matched by the algorithm above.

Why it matters. It is the simplest example of the distance argument that underlies most lower bounds for programmable matter.

3Lower boundLocal particles cannot see where the gap is Universal coating → Daymude et al. 2018

Let the object be a long straight bar. The first layer is completely full except for one empty node exactly in the middle below the bar, and one extra particle sits in the second layer exactly in the middle above it. Someone who sees everything solves it in a constant number of rounds: every particle in the first layer shifts by one node around the bar, closing the gap, and the extra particle drops in. Local particles near the two ends of the bar cannot tell, within about \(n/4\) rounds, which way the shift should go: information moves at most one node per round, and the situation looks the same from both ends.

Why it holds. So for about \(n/4\) rounds the flows at the two ends are decided independently and by symmetry are equally likely to go either way; in the cases where they do not fit together, the layer is not yet correct. Hence any local algorithm is, on such inputs, about \(n\) times slower than the best algorithm with global knowledge: a competitive ratio of \(\Omega(n)\) Daymude et al. 2018 (Theorem 1).

Why it matters. It shows that 'worst case over all inputs' is the right measure here, since comparing to the best possible run on each input is hopeless for local algorithms.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Moves
Universal coating standard
Any object admitting a uniform coating is coated with optimal work, and in \(\Theta(n)\) rounds with high probability.
tight \(O(n)\) vs \(\Omega(n)\) locality
tight \(O(n^2)\) vs \(\Omega(n^2)\) distance
SILBOT, chirality, deterministic
Silent oblivious particles with chirality coat a convex object with one layer, deterministically, in \(O(n^2)\) rounds.
tight \(O(n^2)\) vs \(\Omega(n^2)\) oblivious silent particles
unknown — vs —

Open questions 2

SILBOT, chirality, deterministic

  1. Coating in SILBOT without chirality Navarra & Piselli 2023.
  2. Multi-layer coating, which "seems unfeasible" in SILBOT Navarra & Piselli 2023.

What the community started looking at

Coating was posed as a basic task for self-organising matter with work (moves) as the first measure Derakhshandeh et al. 2017; rounds followed, with matching bounds Daymude et al. 2018. Coating was later solved by silent, oblivious particles Navarra & Piselli 2023 and in 3D hybrid programmable matter Kostitsyna et al. 2024.

Perspectives

  • From robots to particles Programmable matter re-asks the questions of robots in the plane on a lattice, with particles that touch, remember a little and stay connected; SILBOT takes memory and messages away again, and the stochastic approach replaces algorithms by a biased local rule.

All settings

The assumption tree (2 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Moves); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Memory › Scheduler › Orientation › Randomness › Initial shape › Connectivity during execution.

tight near-optimal polynomial gap unknown impossible no variant

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.