«Abstract. Amorphous computing considers the problem of controlling millions of spatially distributed unreliable devices which communicate only with ...»
Programming an Amorphous
Massachusetts Institute of Technology, Cambridge MA 02139, USA
Abstract. Amorphous computing considers the problem of controlling
millions of spatially distributed unreliable devices which communicate
only with nearby neighbors. To program such a system, we need a highlevel description language for desired global behaviors, and a system to
compile such descriptions into locally executing code which robustly creates and maintains the desired global behavior. I survey existing amorphous computing primitives and give desiderata for a language describing computation on an amorphous computer. I then bring these together in Amorphous Medium Language, which computes on an amorphous computer as though it were a space-ﬁlling computational medium.
1 Introduction Increasingly, we are faced with the prospect of programming spatially embedded mesh networks composed of huge numbers of unreliable parts. Projects in such diverse ﬁelds as sensor networks (e.g. NEST ), peer-to-peer wireless (e.g.
RoofNet ), smart materials (e.g. smart dusts [17, 26]), and biological computation [18, 29, 30] all envision deployed networks of large size (ranging from thousands to trillions of nodes) where only nodes nearby in space can communicate directly, and the network as a whole approximates the physical space through which it is deployed.
Any such large spatially embedded mesh network may be considered an amorphous computer. Amorphous computing studies the problem of controlling these networks from a perspective of group behavior, taking inspiration from biological processes such as morphogenesis and regeneration, in which unreliable simple processing units (cells) communicating locally (e.g. with chemical gradients) execute a shared program (DNA) and cooperate to reliably produce an organism’s anatomy.
Controlling an amorphous computer presents serious challenges. Spatially local communication means networks may have a high diameter, and large numbers of nodes place tight constraints on sustainable communication complexity.
Moreover, large numbers also mean that node failures and replacements are a continuous process rather than isolated events, threatening the stability of the network. If we are to program in this environment, we need high-level programming abstractions to separate the behaviors being programmed from the networking and robustness issues involved in executing that program on a spatially embedded mesh network.
J.-P. Banˆtre et al. (Eds.): UPP 2004, LNCS 3566, pp. 121–136, 2005.
a c Springer-Verlag Berlin Heidelberg 2005 122 J. Beal Let us deﬁne an amorphous medium to be a hypothetical continuous computational medium ﬁlling the space approximated by an amorphous computer.
I propose that this is an appropriate basis for abstraction: high-level behavior can then be described in terms of geometric regions of the amorphous medium, then executed approximately by the amorphous computer.
In support of this hypothesis, I ﬁrst detail the amorphous computing scenario, then survey existing amorphous computing primitives and describe how they can be viewed as approximating the behavior of an amorphous medium. I then present the Amorphous Medium Language, which describes program behavior in terms of nested processes occupying migrating regions of the space in which the network is embedded, describe AML’s key design elements — spatial processes, active process maintenance, and homeostasis — and illustrate the language by means of examples.
2 The Amorphous Computing Scenario The amorphous computing engineering domain presents a set of challenging requirements and prohibitions to the system designer, forcing confrontation of issues of robustness, distribution, and scalability. These constraints derive much of their inspiration from biological systems engaged in morphogenesis and regeneration, which must be accomplished by coordinating extremely large numbers of unreliable devices (cells).
The ﬁrst and foremost requirement is scalability: the number of devices may be large, anywhere from thousands to millions or even billions. Biological systems, in fact, may comprise trillions of cells. Practically, this means that an algorithm is reasonable only if its per-device asymptotic complexity (e.g. space or bandwidth per device) are polynomial in log n (where n is the number of devices) — and any bound signiﬁcantly greater than O(lg n) should be treated with considerable suspicion. Further, unlike ad-hoc networking and sensor networks scenarios, amorphous computing generally assumes cheap energy, local processing, and storage — in other words, as long as they do not have a high per-device asymptotic complexity, minimizing them is not of particular interest.
The network graph is determined by the spatial distribution of the devices in some Euclidean space, which collaborate via local communication. Devices are generally immobile unless the space in which they are embedded is moved (e.g. cutting and pasting ”smart paper”)1. A unit disc model is often used to create the network, in which a bidirectional link exists between two devices if and only if they are less than distance r apart. Local communication implies that the network is expected to have a high diameter, and, assuming a packet-based communication model, this means that the time for information to propagate through the network depends primarily on the number of hops it needs to travel.
Local communication also means that communication complexity is best meaNote that mobile devices might be programmed as immobile virtual devices [13, 14].
Programming an Amorphous Computational Medium 123 sured by maximum communication density — the maximum bandwidth required by a device — rather than by number of messages.
Due to the number of devices potentially involved, the system must not depend on much care and feeding of the individual devices. In general, it is assumed that every device is identically programmed, but that there can be a small amount of diﬀerentiation via initial conditions. Once the system is running, however, there is no per-device administration allowed.
There are strict limitations on the assumed network infrastructure. The system executes with partial synchrony — each device may be assumed to have a clock which ticks regularly, but the clocks may show diﬀerent times, run at (boundedly) diﬀerent rates, and have diﬀerent phases. In addition, the system may not assume complex services not presently extended to the amorphous domain — this is applied particularly to mean no global naming, routing, or coordinate service may be assumed.
Finally, in a large, spatially distributed network of devices, failures are not isolated events. Due to the sheer number of devices, point failures are best measured by an expected rate of device failure. This suggests also that methods of analysis like half-life analysis  will be more useful than standard f -failure analysis. In addition, because the network is spatially embedded, outside events may cause failure of arbitrary spatial regions — larger region failures are assumed to occur less frequently. Generally stopping failures have been used, in which the failing device or link simply ceases operating. Finally, maintenance requires recovery or replacement of failed devices: in either case, the eﬀect is that new devices join the network either individually or as a region.
3 Amorphous Computing Mechanisms Several existing amorphous computing algorithms will serve as useful primitives for constructing a language. Each mechanism summarized here has been implemented as a code module and demonstrated in simulation. Together they are a powerful toolkit from which primitives for high-level languages can be constructed.
3.1 Shared Neighborhood Data This simple mechanism allows neighboring devices to communicate by means of a shared-memory region, similar to the systems described in [7, 32]. Each device maintains a table of key-value pairs which it wishes to share (for example, the keys might be variable names and the values their bindings). Periodically each device transmits its table to its neighbors, informing them that it is still a neighbor and refreshing their view of its shared memory. Conversely, a neighbor is removed from the table if more than a certain time has elapsed since its last refresh. The module can then be queried for the set of neighbors, and the values its neighbors most recently held for any key in its table.
Shared neighborhood data can also be viewed as a sample of the amorphous medium within a unit neighborhood. Aggregate functions of the neighborhood 124 J. Beal data (e.g. average or maximum) are then approximations of the same functions on a neighborhood of the amorphous medium.
Maintaining shared neighborhood data requires storage and communication density proportional to the number of values being stored, size of the values, and number of neighbors.
3.2 Regions The region module maintains labels for contiguous sets of devices, approximating connected regions of the amorphous medium, using a mechanism similar to that in . A Region is deﬁned by a name and a boolean membership function.
When seeded in one or more devices, a Region spreads via shared neighborhood data to all adjoining devices that satisfy the membership test. When a Region is deallocated, a garbage collection mechanism spreads the deallocation throughout the participating devices, attempting to ensure that the defunct Region is removed totally.
Note that failures or evolving system state may separate a Region into disconnected components. While these are still logically the same Region, and may rejoin into a single connected component in the future, information will not generally pass between disconnected components. As a result, the state of disconnected components of a Region may evolve separately, and in particular garbage collection is only guaranteed to be eﬀective in a connected component of a Region.
Regions are organized into a tree, with every device belonging to the root Region. In order for a device to be a member of a Region, it must also be a member of that Region’s parent in the tree. This implicit compounding of membership tests allows Regions to exhibit stack-like behavior which will be useful for establishing execution scope in a high-level language.
Maintaining Regions requires storage and communication density proportional to the number of Regions being maintained, due to the maintenance of shared neighborhood data. Garbage collecting a Region requires time proportional to the diameter of the Region.
3.3 Gossip The gossip communication module  propagates information throughout a Region via shared neighborhood data, after the fashion of ﬂooding algorithms .
Gossip is all-to-all communication: each item of gossip has a merge function that combines local state with neighbor information to produce a merged whole.
When an item of gossip is garbage-collected, the deallocation propagates slowly to prevent regrowth into areas which have already been garbage-collected.
Gossip requires storage and communication density proportional to the number and size of gossip items being maintained in each Region of which a device is a member, due to the maintenance of shared neighborhood data. Garbage collecting an item of gossip takes time proportional to the diameter of the region.
Programming an Amorphous Computational Medium 125
3.4 Consensus and Reduction Non-failing devices participating in a strong consensus process must all choose the same value if any of them choose a value, and the chosen value must be held by at least one of the participants. Reduction is a generalization of consensus in which the chosen value is an aggregate function of values held by the participants (e.g. sum or average) — as before, all non-failing devices complete the operation holding the same value.
The Paxos consensus algorithm  has been demonstrated in an amorphous computing context , but scales badly. A gossip-based algorithm currently under development promises much better results: it appears that running a robust reduction process on a Region may require only storage and communication density logarithmic in the diameter of the Region and time linear in the diameter of the Region.
3.5 Read/Write Atomic Objects Atomic consistency means that all transactions with an object can be viewed as happening in some order, even if they overlap in time. If we designate a Region of an amorphous medium as a read/write atomic object, then reading or writing values at any point in the Region produces a consistent view of the value held by the Region over time.
Using consensus and reduction, quorum-based atomic transactions can be supported by a reconﬁgurable set of devices [23,15]. This has been demonstrated in simulation for amorphous computing , and scales as the underlying consensus and reduction algorithms do.
3.6 Active Gradient An active gradient [9, 11, 8] maintains a hop-count upwards from its source or sources — a set of devices which declare themselves to have count value zero — giving an approximation of radial distance in the amorphous medium, useful for establishing Regions. Points in the gradient converge to the minimum hop-count and repairs their values when they become invalid. The gradient runs within a Region, and may be further bounded (e.g. with a maximum number of hops).
When the supporting sources disappear, the gradient is garbage-collected; as in the case of gossip items, the garbage collection propagates slowly to prevent unwanted regrowth into previously garbage collected areas. A gradient may also carry version information, allowing its source to change more smoothly. Figure 1 shows an active gradient being used to maintain a line.
Maintaining a gradient requires a constant amount of storage and communication density for every device in range of the gradient, and garbage collecting a gradient takes time linear in the diameter of its extent.
3.7 Persistent Node A Persistent Node  is a robust mobile virtual object that occupies a ball in the amorphous medium (See Figure 2). A Persistent Node is a read/write 126 J. Beal