Programmable matter

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. 2015b; 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. 2020e. 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. 2026b. The canonical amoebot model lists all four levels: assorted, common chirality, common direction, and common direction and chirality Daymude et al. 2023.

The early amoebot papers assumed "the standard asynchronous computation model, i.e., only one particle can be active at a time" Derakhshandeh et al. 2015b; 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. 2020e. 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. In the circuit extension "the amoebot structure is assumed to progress in synchronized rounds" Feldmann et al. 2022; this is the synchronous value.

Feldmann, Padalkin, Scheideler and Dolev introduced reconfigurable circuits, modelled on the nervous system, because leader election and similar problems need time of the order of the diameter when "information only travels particle by particle"; with circuits, stationary particles elect a leader in \(\Theta(\log n)\) rounds with high probability Feldmann et al. 2022. Circuit algorithms are stated for stationary particles in synchronous rounds. Warner and Scheideler let each particle miss a beep with constant probability and keep most of the speed-up Warner & Scheideler 2026b.

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. 2015b; 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 2023b). 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 2023b Navarra & Piselli 2023a Chalopin et al. 2026a.

The first leader-election algorithm for amoebots used random bits to break symmetry Derakhshandeh et al. 2015b, and Di Luna et al. listed randomization as the "more important" of the assumptions behind the early shape-formation results Di Luna et al. 2020e. 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. 2020e, 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.

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. 2015b (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. 2020e and Gastineau et al. assume chirality and no holes Gastineau et al. 2018. 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. 2026a.

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. 2015b. 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 2023b. In centralised transformations the same distinction separates transformations that may break connectivity from those that may not Michail et al. 2019.