Mobility Matters
Home›Programmable matter›Self-organising particle systems›Compression›Separation of coloured particles

Separation of coloured particles

Particles of two colours, following a local stochastic rule, must cluster by colour (or mix).

Problem statement and measuresexpand

Each particle has one of two colours. Particles run a local Markov chain with a bias \(\lambda\) towards more neighbours and a bias \(\gamma\) towards neighbours of the same colour. The system should be compressed and separated (few pairs of neighbours of different colours), or integrated (colours mixed), with high probability in the stationary distribution.

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

no assumptions›+ constant memory, + sequential, + randomized

Markov chain, sequential

standard settingverified
Time: unknownMoves: unknown

One local algorithm separates or integrates the colours depending on a single global parameter.

Assumed (added on the last edge are outlined)

+Memoryconstant memory and local communication+Schedulersequential: one particle active at a time+Randomnessrandomized

Not assumed

Orientationno common orientation and no chiralityInitial shapeconnected, holes allowedConnectivity during executionthe system must stay connected
Formal definitions of this setting
Memory: constant memory
Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
Scheduler: sequential
At most one particle is active at any time.
Orientation: no orientation
Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
Randomness: randomized
Particles flip fair coins; guarantees hold with high probability or in expectation.
Initial shape: holes allowed
The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
Connectivity during execution: stays connected
At every time the occupied nodes induce a connected subgraph.

What is known

Time · asynchronous rounds
unknown
Mixing time not bounded.
lower boundnone known
introductory—
current best
\(\text{eventually}\)
Moves · total expansions and contractions (work)
unknown
—
lower boundnone known
introductory—
current best—

Results, in order of publication

Cannon et al. 2019 current best
Time \(\text{eventually}\)

Introductory and current best; proofs use cluster expansions and the high-temperature expansion of the Ising model.

Open questions

  1. Bounds on the convergence (mixing) time.

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