The canonical amoebot model: algorithms and concurrency control

Abstract

The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction at SPAA 2014, a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design. We first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. As a case study, we demonstrate both approaches using a simple algorithm for hexagon formation. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.

Appendices

Appendix A: Amoebot operation pseudocode

In this appendix, we give formal distributed pseudocode for the amoebot operations. Algorithm 5 details the communication operations (Sect. 2.2.1) and Algorithms 6 and 7 detail the movement operations (Sect. 2.2.2). One possible implementation of the concurrency control operations (Sect. 2.2.3) is given in [22].

Appendix B: Expansion contention resolution

Recall that when an amoebot’s expansion collides with another movement, it must perform contention resolution such that exactly one contending amoebot succeeds in its expansion while all others fail. In this appendix, we detail and analyze one possible implementation of such a contention resolution scheme inspired by randomized backoff mechanisms for contention resolution in wireless networks [6, 8, 11]. We need one additional assumption: all amoebots know an upper bound T on the time required for an amoebot to complete any movement. For simplicity, we will assume geometric space (i.e., the triangular lattice $G_{\Delta }$), though this mechanism would generalize to any bounded degree graph.

The execution flow of our contention resolution mechanism is shown in Fig. 7 and its pseudocode is given in Algorithm 8. When A detects a collision, it retracts to its original node and retries its expansion after waiting for a delay chosen uniformly at random from [5T, 10T], where T is an upper bound on the time required for an amoebot to complete an expansion or retraction. In the remainder of this section, we verify the following claim.

Lemma 23

Suppose a set of amoebots are contending to expand into the same node of $G_{\Delta }$. If each amoebot waits for a delay chosen uniformly at random from [5T, 10T] before its expansion attempt, then exactly one contender succeeds in ${\mathcal {O}}({\log n})$ attempts w.h.p.⁴

Fig. 7

Execution flow of the $\textsc {Expand}$ operation with contention resolution for the calling amoebot A

Proof

We first bound the probability that two amoebots $A_1$ and $A_2$ collide in their respective expansion attempts into the same node. For each amoebot $A_i \in \{A_1, A_2\}$, let $t_i$ denote the start of its expansion attempt, $d_i$ denote its random delay, and $e_i$ denote the duration of its expansion if it were to succeed. The start time $t_i$ and expansion duration $e_i$ are fixed a priori by the adversary while the delay $d_i$ is chosen uniformly at random from the interval [5T, cT], where $c > 5$ is a constant. So, in summary, amoebot $A_i \in \{A_1, A_2\}$ is waiting in the time interval $[t_i, t_i + d_i)$ and is expanding in the interval $[t_i + d_i, t_i + d_i + e_i]$. Thus, the expansions of amoebots $A_1$ and $A_2$ collide if and only if:

$$\begin{aligned}&[t_1 + d_1, t_1 + d_1 + e_1] \cap [t_2 + d_2, t_2 + d_2 + e_2] \ne \emptyset \\&\quad \iff (t_1 + d_1 + e_1 \ge t_2 + d_2) \\&\qquad \wedge (t_1 + d_1 \le t_2 + d_2 + e_2) \\&\quad \iff t_2 - t_1 - e_1 \le d_1 - d_2 \le t_2 - t_1 + e_2 \end{aligned}$$

This implies:

$$\begin{aligned}&\text {Pr}\left[ {A_1\ \text {and}\ A_2\ \text {collide} \mid t_1, t_2, e_1, e_2}\right] \\&\quad = \text {Pr}\left[ {t_2 - t_1 - e_1 \le d_1 - d_2 \le t_2 - t_1 + e_2}\right] \\&\quad = \text {Pr}\left[ {d_1 - d_2 \le t_2 - t_1 + e_2}\right] \\&\qquad - \text {Pr}\left[ {d_1 - d_2 \le t_2 - t_1 - e_1}\right] \end{aligned}$$

Delays $d_1$ and $d_2$ are both uniform random variables over the interval [5T, cT], so the difference $d_1 - d_2$ follows the symmetric triangular distribution with lower bound $(5 - c)T$, upper bound $(c - 5)T$, and mode 0. W.l.o.g., suppose $t_1 < t_2$. There are two cases: when $t_2 - t_1 - e_1 \le 0$ and when $t_2 - t_1 - e_1 > 0$. If we have $t_2 - t_1 - e_1 \le 0$, then:

$$\begin{aligned}&\text {Pr}\left[ {d_1 - d_2 \le t_2 - t_1 + e_2}\right] \\&\qquad - \text {Pr}\left[ {d_1 - d_2 \le t_2 - t_1 - e_1}\right] \\&\quad = 1 - \frac{((c - 5)T - (t_2 - t_1 + e_2))^2}{((c - 5)T - (5 - c)T)((c - 5)T - 0)} \\&\qquad - \frac{(t_2 - t_1 - e_1 - (5 - c)T)^2}{((c - 5)T - (5 - c)T)(0 - (5 - c)T)} \\&\quad = \left[ 2(c - 5)^2T^2 - ((c - 5)T - t_2 + t_1 - e_2)^2\right. \\&\qquad \left. - ((c - 5)T + t_2 - t_1 - e_1)^2\right] / 2(c - 5)^2T^2 \\&\quad = \left[ 2(c - 5)^2T^2 - 2(c - 5)^2T^2 + 2(c - 5)Te_2\right. \\&\qquad + 2(c - 5)Te_1 - 2t_2^2 + 4t_2t_1 - 2t_2e_2 + 2t_2e_1 \\&\qquad \left. - 2t_1^2 + 2t_1e_2 - 2t_1e_1 - e_2^2 - e_1^2\right] / 2(c - 5)^2T^2 \\&\quad = \left[ 2(c - 5)T(e_1 + e_2) - 2(t_2 - t_1)(e_2 - e_1)\right. \\&\qquad \left. - 2(t_2 - t_1)^2 - e_1^2 - e_2^2\right] / 2(c - 5)^2T^2 \\&\quad < \left[ 4(c - 5)T^2 + 2(c + 1)T^2\right] / 2(c - 5)^2T^2 \\&\quad = 3(c - 3) / (c - 5)^2, \end{aligned}$$

which is a constant probability whenever $c > \frac{13 + \sqrt{33}}{2} \approx 9.373$. The upper bound follows from:

• Since T is the upper bound on the time required for an expansion, $e_1 + e_2 \le 2T$.

• We assumed that $t_1 < t_2$, but we also have that if $t_2 > t_1 + d_1 + e_1$, then there cannot be a collision. Thus, $t_2 - t_1 \le d_1 + e_1 \le cT + T$ is a necessary condition for a collision. We also have that $-T \le e_2 - e_1 \le T$, so we conclude that $-2(t_2 - t_1)(e_2 - e_1) \le 2(c + 1)T^2$.

• The last three numerator terms are all nonpositive, and thus can be upper bounded by 0.

In the second case, if we have $t_2 - t_1 - e_1 > 0$, then:

$$\begin{aligned}&\text {Pr}\left[ {d_1 - d_2 \le t_2 - t_1 + e_2}\right] \\&\qquad - \text {Pr}\left[ {d_1 - d_2 \le t_2 - t_1 - e_1}\right] \\&\quad = 1 - \frac{((c - 5)T - (t_2 - t_1 + e_2))^2}{((c - 5)T - (5 - c)T)((c - 5)T - 0)} \\&\qquad - 1 + \frac{((c - 5)T - (t_2 - t_1 - e_1))^2}{((c - 5)T - (5 - c)T)((c - 5)T - 0)} \\&\quad = \left[ ((c - 5)T - t_2 + t_1 + e_1)^2 \right. \\&\qquad \left. - ((c - 5)T - t_2 + t_1 + e_2)^2\right] / 2(c - 5)^2T^2 \\&\quad = \left[ 2(c - 5)Te_1 - 2(c - 5)Te_2 - 2t_2e_1 + 2t_2e_2 \right. \\&\quad \left. + 2t_1e_1 - 2t_1e_2 + e_1^2 - e_2^2\right] / 2(c - 5)^2T^2 \\&\quad = \left[ 2(c - 5)T(e_1 - e_2) - 2(t_2 - t_1)(e_1 - e_2)\right. \\&\qquad \left. + e_1^2 - e_2^2\right] / 2(c - 5)^2T^2 \\&\quad < \left[ 2(c - 5)T^2 + 2(c + 1)T^2 + T^2\right] / 2(c - 5)^2T^2 \\&\quad = (4c - 7) / 2(c - 5)^2, \end{aligned}$$

which is a constant probability whenever $c > 6 + \sqrt{15/2} \approx 8.739$. Therefore, in any case, the probability that the expansions of $A_1$ and $A_2$ collide when their delays are drawn uniformly at random from the interval [5T, cT] is at most a constant $p \in (0, 1)$ when $c > 9.373$.

Due to the structure of the triangular lattice $G_{\Delta }$, at most six amoebots may be concurrently expanding into the same node. We now establish that pairwise collisions of any of these amoebots’ expansions are independent. Given each expansion attempt’s starting time and expansion duration—which are fixed by the asynchronous execution—the interval of expansion is entirely determined by the delay. Since each delay is drawn independently and uniformly from [5T, cT], each pair of expansions’ time intervals and thus also their collision is independent. So, fixing an amoebot $A_1$,

$$\begin{aligned}&\text {Pr}\left[ {\text {an expansion of}\ A_1\ \text {succeeds} \mid t_1, e_1}\right] \\&\quad = \text {Pr}\left[ {A_1\ \text {and}\ A_i\ \text {do not collide} \mid t_1, t_i, e_1, e_i, \forall i \ne 1}\right] \\&\quad = \prod _{i \ne 1} (1 - \text {Pr}\left[ {A_1\ \text {and}\ A_i\ \text {collide} \mid t_1, t_i, e_1, e_i}\right] ) \\&\quad > (1 - p)^5, \end{aligned}$$

which is a constant probability since p is a constant probability.

In order to amplify this success probability for the desired w.h.p. result, we must establish independence of expansion attempts. We have already shown that pairwise collisions of amoebots’ expansions are independent, but this is insufficient to establish the independence of subsequent expansion attempts. In particular, $A_1$ and $A_2$ may collide while concurrently attempting to expand, causing them both to retract before reattempting their expansions. A third amoebot $A_3$ could then expand and collide with $A_1$ or $A_2$ while they are retracting, causing $A_3$ to also retract; a fourth amoebot $A_4$ could then expand and collide with $A_3$ while it retracts, and so on. In the worst case, if the expansions of $A_1$ and $A_2$ collide at time t, these cascading expansion-retraction collisions can continue until time $t + 5T$; this occurs if all retractions take the maximum time T and each amoebot $A_i$ (for $i = 3, \ldots , 6$, since there are at most six competing amoebots) collides with retracting amoebot $A_{i-1}$ at the last possible moment. However, it is impossible for these cascading collisions to continue after $t + 5T$: the earliest an amoebot could reattempt its expansion is after time $t + 5T$ if $A_1$ or $A_2$ immediately retracted after colliding at time t and then sampled the minimum possible delay, 5T. Therefore, the expansion attempt of an amoebot $A_i$ is independent of any of its previous attempts. So we have:

$$\begin{aligned}&\text {Pr}\left[ {\text {no amoebot successfully expands after}\ k\ \text {attempts}}\right] \\&\quad \le \text {Pr}\left[ {A_1\ \text {collides in all}\ k\ \text {expansion attempts}}\right] \\&\quad = \prod _{i=1}^k \left( 1 - \text {Pr}\left[ {A_1\text {'s}\ i\text {-th expansion attempt succeeds} \mid t_1^i, e_1^i}\right] \right) \\&\quad < \left( 1 - (1 - p)^5\right) ^k \end{aligned}$$

Setting $k = \ln n / (1 - p)^5$, we have the probability that no amoebot successfully expands after k attempts is at most

$$\begin{aligned} \left( 1 - (1 - p)^5\right) ^k \le e^{-(1 - p)^5 \cdot \frac{\ln n}{(1 - p)^5}} = \frac{1}{n} \end{aligned}$$

Once an amoebot’s expansion succeeds, it connects to all its new neighbors causing any contending expansions to immediately fail. Therefore, we conclude that exactly one amoebot will successfully expand in at most $\ln n = {\mathcal {O}}({\log n})$ attempts with high probability. $\square$