Amorphous Computing - Algorithms, Tools, and Patterns

Algorithms, Tools, and Patterns

(Some of these algorithms have no known names. Where a name is not known, a descriptive one is given.)

• "Fickian communication". Devices communicate by generating messages which diffuse through the medium in which the devices dwell. Message strength will follow the inverse square law as described by Fick's law of diffusion. Examples of such communication are common in biological and chemical systems.

• "Link diffusive communication". Devices communicate by propagating messages down links wired from device to device. Unlike "Fickian communication", there is not necessarily a diffusive medium in which the devices dwell and thus the spatial dimension is irrelevant and Fick's Law is not applicable. Examples are found in Internet routing algorithms such as the Diffusing Update Algorithm. Most algorithms described in the amorphous computing literature assume this kind of communication.

• "Wave Propagation". (Ref 1) A device emits a message with an encoded hop-count. Devices which have not seen the message previously, increment the hop count, and re-broadcast. A wave propagates through the medium and the hop-count across the medium will effectively encode a distance gradient from the source.

• "Random ID". Each device gives itself a random id, the random space being sufficiently large to preclude duplicates.

• "Growing-point program". (Coore). Processes that move among devices according to 'tropism' (movement of an organism due to external stimuli).

• "Wave coordinates". DARPA PPT slides. To be written.

• "Neighborhood query". (Nagpal) A device samples the state of its neighbors by either a push or pull mechanism.

• "Peer-pressure". Each device maintains a state and communicates this state to its neighbors. Each device uses some voting scheme to determine whether or not to change state to its neighbor's state. The algorithm partitions space according to the initial distributions and is an example of a clustering algorithm.

• "Self maintaining line". (Lauren Lauren, Clement). A gradient is created from one end-point on a plane covered with devices via Link Diffusive Communication. Each device is aware of its value in the gradient and the id of its neighbor that is closer to the origin of the gradient. The opposite end-point detects the gradient and informs its closer neighbor that it is part of a line. This propagates up the gradient forming a line which is robust against disruptions in the field. (Illustration needed).

• "Club Formation". (Coore, Coore ,Nagpal, Weiss). Local clusters of processors elect a leader to serve as a local communication hub.

• "Coordinate formation" (Nagpal). Multiple gradients are formed and used to form a coordinate system via triangulation.