Programmable matter
Many tiny particles with constant memory occupy nodes of the triangular lattice, move by expanding and contracting, and must self-organise into a shape or elect a leader.
The first question was what constant-memory, anonymous particles can do at all (leader election, shapes, coating); then rounds, with matching lower bounds where possible, and how weak a scheduler and how little orientation the algorithms can tolerate.
In the amoebot model Derakhshandeh et al. 2014 each particle occupies one node of the infinite triangular lattice (contracted) or two adjacent nodes (expanded). A particle moves by expanding into an empty neighbouring node and contracting into one of its two nodes. Particles are anonymous, have constant memory, and communicate only with neighbours; in the founding announcement each particle is a finite-state machine that reads and writes one flag per incident edge, and a pair of neighbours may combine an expansion and a contraction into a handover Derakhshandeh et al. 2014. An adversarial scheduler activates particles; time is measured in asynchronous rounds: intervals of time in which every particle is activated at least once (the epochs of the other models; they need not be the shortest such intervals, and a bound holds for every division of the execution into consecutive rounds). The canonical amoebot model separates the core model from families of assumption variants, including concurrency Daymude et al. 2023.
How the axes work. As in the other models, level 0 assumes nothing and higher levels are stronger assumptions.
How the assumptions fit together
Matter that computes
Toffoli and Margolus coined programmable matter for matter that changes its physical properties under program control Toffoli & Margolus 1991 (as reported by Di Luna et al. 2020, Emek et al. 2019 and Derakhshandeh et al. 2014). Derakhshandeh et al. proposed the amoebot model in a brief announcement at SPAA 2014: particles on the triangular lattice that "have constant memory (in particular, they have no identifiers)", "act asynchronously and make their decision based on local information", and move by expanding and contracting, "which resembles the behavior of amoeba" Derakhshandeh et al. 2014. The founding papers fixed many details at once: common chirality, one particle active at a time, random bits, constant memory and a structure that stays connected Derakhshandeh et al. 2014 Derakhshandeh et al. 2015; the announcement already named compass, initialisation and fault tolerance as dimensions along which the model could vary Derakhshandeh et al. 2014. Most axes of this model are the history of removing those defaults one by one.
Removing the defaults
Di Luna et al. listed the defaults behind the early shape-formation results (chirality, a sequential schedule and, "more important, randomization") and asked: "What can be done deterministically? Is chirality necessary? ... What happens if the scheduler is not sequential?" Di Luna et al. 2020. Their answers, and the leader-election papers that followed Emek et al. 2019 Dufoulon et al. 2021 Chalopin et al. 2026, gave the axes orientation, scheduler, randomness and initial shape. Chalopin, Das and Kokkou observe that every deterministic two-dimensional leader-election algorithm uses at least two extra assumptions from a short menu: randomness, simply connected shape, chirality, movement, a sequential scheduler Chalopin et al. 2026. Daymude, Richa and Scheideler then wrote the hierarchy down as the canonical amoebot model, with variants for orientation, memory, concurrency and fairness, because without it "precise systematic comparison of results under the amoebot model is difficult" Daymude et al. 2023.
Weaker particles, looser structures
Two axes push below the original model. SILBOT particles keep no memory beyond being contracted or expanded, send no messages and act asynchronously with non-atomic actions, so a step depends only on what a particle sees within two hops D'Angelo et al. 2020; this is the oblivious memory level and the weak scheduler. The connectivity axis records that the requirement that the structure stays connected at every moment is a convention of the literature rather than of the model: Dufoulon, Kutten and Moses Jr. disconnected and reconnected the structure on purpose to elect a leader faster Dufoulon et al. 2021.
Other mechanisms
Not every problem in this model is about amoebots. Problem-specific axes cover modules on the square grid that rotate or slide under central control Michail et al. 2019, the hybrid model in which one finite-state agent moves passive tiles in two or three dimensions Gmyr et al. 2020 Hinnenthal et al. 2024, and, for leader election, whether particles may move at all Chalopin et al. 2026. These axes apply to a single problem each. They are kept on the problem so that the model's own axes stay shared across problems.
Notation
Symbols of this model; the notation page has every model and the general conventions.
| Symbol | Meaning | Papers write | Used in |
|---|---|---|---|
| \(n\) | number of particles (modules, tiles) | whole model | |
| \(D\) | diameter of the configuration (largest lattice distance between two particles) | whole model | |
| \(L_{out},\ L_{max}\) | length of the outer boundary and of the longest boundary of the configuration | Leader election in programmable matter | |
| \(\lambda\) | bias towards having more neighbours (stochastic approach) | whole model | |
| \(\gamma\) | bias towards neighbours of the same colour (separation) | Separation of coloured particles | |
| \(\alpha\) | compression factor: perimeter at most \(\alpha\) times the minimum | Compression | |
| \(q\) | number of orientations (alignment) | Alignment | |
| \(s\) | number of energy sources | Energy distribution | |
| \(k\) | symmetricity of a configuration (a \(k\)-symmetric configuration admits up to \(k\) leaders) | Leader election in programmable matter |
Assumption axes
Each axis below says where the assumption comes from and why the community studies it. Every axis is a scale. Level 0 assumes nothing; each higher level is a stronger assumption, which makes a problem easier. Values on the same level are alternatives that do not imply each other. An algorithm designed for weaker assumptions works under stronger ones; a lower bound proved under stronger assumptions holds under weaker ones.
Orientation
In the geometric amoebot model of Derakhshandeh et al., each particle labels its six ports clockwise from an arbitrary edge, so all particles share chirality but not a direction Derakhshandeh et al. 2015; the 2014 announcement numbers the edges counter-clockwise and calls this the "no-compass model where particles only share their sense of orientation", as opposed to a full-compass model Derakhshandeh et al. 2014. Di Luna et al. asked whether chirality is necessary and showed that it is "computationally irrelevant for shape formation" from simply connected configurations Di Luna et al. 2020. Emek et al. elected a leader with no orientation at all, using a procedure by which the particles reach common chirality Emek et al. 2019. Chalopin, Das and Kokkou replaced chirality by agreement on one lattice direction and found that the difficulties are different: a unique stationary leader can then be elected, but explicit termination is impossible Chalopin et al. 2026. The canonical amoebot model lists all four levels: assorted, common chirality, common direction, and common direction and chirality Daymude et al. 2023.
Formal definitions
- 0no orientation
- Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
- 1chirality
- All particles agree on clockwise order, not on a common direction.
- 1common direction
- All particles agree on one lattice direction, not on handedness. Chalopin, Das and Kokkou call this a common direction Chalopin et al. 2026, but the same words mean agreement on all six directions in other papers Chalopin et al. 2026 Navarra & Piselli 2023.
- 2common compass
- All particles agree on all six directions.
Scheduler
The early amoebot papers assumed "the standard asynchronous computation model, i.e., only one particle can be active at a time" Derakhshandeh et al. 2015; in the 2014 announcement, from the set of enabled actions "a single action is arbitrarily chosen and executed" Derakhshandeh et al. 2014. Di Luna et al. dropped this for a strong scheduler that activates many particles but executes each activation atomically Di Luna et al. 2020. Dufoulon, Kutten and Moses Jr. use strong for atomic activations and weaker for non-atomic ones, under which, they report, deterministic election of a unique leader becomes impossible in some cases (attributed by them to Bazzi and Briones and to Di Luna et al.) Dufoulon et al. 2021 Bazzi & Briones 2019. Daymude, Richa and Scheideler observed that "much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting", whereas "real programmable matter systems are concurrent"; their canonical model orders the concurrency variants from asynchronous through synchronous and k-isolated to sequential Daymude et al. 2023. The fully asynchronous SILBOT model sits at the weak end: all operations are "non-atomic", with possible delays between sensing, computing and acting, so an action may be based on an obsolete observation D'Angelo et al. 2020.
Formal definitions
- 0weak scheduler
- An activation's look, compute and move need not be atomic; concurrent activations may interfere. The scheduler of Bazzi and Briones is described as weak sequential, as non-atomic, and as fair asynchronous by different later papers Briones et al. 2023 Dufoulon et al. 2021 Chalopin et al. 2026.
- 1strong scheduler
- Each activation is executed atomically; the adversary chooses the order, fairly.
- 2sequential
- At most one particle is active at any time.
Memory
Constant memory is part of the amoebot model from its start: each particle runs a fixed finite program and reads and writes memory shared with its neighbours Derakhshandeh et al. 2015; in the 2014 announcement the state set and the flag alphabet on each edge are finite Derakhshandeh et al. 2014. D'Angelo et al. introduced SILBOT at AAMAS 2020, in which particles are "asynchronous, without any direct means of communication (silent) and without memory of past events (oblivious)", to find "the minimal settings for PM under which it is possible to accomplish basic global tasks" D'Angelo et al. 2020 (as described by Navarra & Piselli 2023). Each SILBOT particle is "an automaton with two states, CONTRACTED or EXPANDED (they do not have any other form of persistent memory)" D'Angelo et al. 2020. In exchange, particles see two hops instead of one, because "without communication, 1-hop visibility is not enough for a particle to decide whether it is a LEADER or not" D'Angelo et al. 2020. The canonical amoebot model lists oblivious, constant, finite and unbounded memory as its memory variants Daymude et al. 2023. Oblivious particles have since solved leader election, line formation, coating and self-stabilising election with holes D'Angelo et al. 2020 Navarra & Piselli 2023 Navarra & Piselli 2023 Chalopin et al. 2026.
Formal definitions
- 0oblivious
- No persistent state and no messages; a particle decides from its view only.
- 1constant memory
- Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.
Randomness
The first leader-election algorithm for amoebots used random bits to break symmetry Derakhshandeh et al. 2015, and Di Luna et al. listed randomization as the "more important" of the assumptions behind the early shape-formation results Di Luna et al. 2020. Deterministic algorithms then became a goal of their own: for a simply connected start up to \(k\) leaders are elected in a \(k\)-symmetric configuration Di Luna et al. 2020, and Emek et al. gave the first deterministic election of a unique leader using movement Emek et al. 2019. A second use of randomness is the stochastic approach of Cannon, Daymude, Randall and Richa, who design a Markov chain whose stationary distribution favours the desired configurations and turn it into a local asynchronous algorithm Cannon et al. 2016. The design is motivated by statistical physics, and the approach has been applied to separation, alignment and bridging Cannon et al. 2019 Kedia et al. 2022 Arroyo et al. 2018.
Formal definitions
- 0deterministic
- No random choices.
- 1randomized
- Particles flip fair coins; guarantees hold with high probability or in expectation.
Initial shape
The first leader-election algorithm for amoebots worked on every boundary of the structure, outer and inner, and its running time depends on the longest boundary Derakhshandeh et al. 2015 (as summarised by Dufoulon et al. 2021). Several early deterministic algorithms assumed the initial configuration has no holes: Di Luna et al. start from any simply connected configuration Di Luna et al. 2020 and Gastineau et al. assume chirality and no holes Gastineau et al. 2019. Dufoulon, Kutten and Moses Jr. summarise that early deterministic algorithms that did not use movement relied on "assumptions on the initial shape ... (intuitively, that it had no 'holes')" Dufoulon et al. 2021. Emek et al. removed the assumption by letting particles move Emek et al. 2019, and Chalopin, Das and Kokkou extended self-stabilising election from simply connected systems to systems with holes Chalopin et al. 2026.
Formal definitions
- 0holes allowed
- The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
- 1no holes
- The initial configuration is connected and encloses no empty node. Also called contractible Briones et al. 2023 or hole-free Gastineau et al. 2019.
Connectivity during execution
The founding papers required the particles to stay connected at all times, "to prevent the particles from drifting apart in an uncontrolled manner like in fluids and because in our case particles communicate only via bonds" Derakhshandeh et al. 2015. Emek et al. still followed "the common practice" that the shape is connected at all times Emek et al. 2019. Dufoulon, Kutten and Moses Jr. observed that the model itself does not require this, and gave a leader-election algorithm that disconnects and later reconnects, gaining a large speed-up in time Dufoulon et al. 2021. In SILBOT, line formation also passes through disconnected configurations and proves that connectivity is recovered Navarra & Piselli 2023. In centralised transformations the same distinction separates transformations that may break connectivity from those that may not Michail et al. 2019.
Formal definitions
- 0stays connected
- At every time the occupied nodes induce a connected subgraph.
- 1may disconnect
- Connectivity is required only initially and at the end.
Problems in this model
Problem familySelf-organising particle systems
Leader election, shape formation, coating, scattering, stochastic tasks (compression, separation, alignment, bridging), energy distribution, hybrid and centralised reconfiguration.