Back to the Main Page

Amorphous Computing Publications

Programming Paradigms

Synthetic Biology

Infrastructure for an Amorphous Computer

Models of Physics and Biology

Other papers unrelated to Amorphous Computing

Detailed Listing of Papers

Title: Morphogenesis as an Amorphous Computation
Author: Arnab Bhattacharyya
Published: ACM International Conference on Computing Frontiers, May 2006
Abstract:
In this paper, we present a programming language viewpoint for morphogenesis, the process of shape formation during embryological development. Specifically, we model morphogenesis as a self-organizing, self-repairing amorphous computation and describe a framework through which we can program large-scale shape formation by giving local instructions to cell-like objects. Then, using this programmatic perspective, we specify some example developmental processes and discuss the characteristics that make them suitable candidates for evolutionary variation and selection. Consistent with the theory of facilitated variation from evolutionary biology, we find that variation in developmental processes can be introduced and conserved due to the hierarchical organization of growth specification.
Conference version in postscript and PDF.
Title: Determining Articulator Configuration in Voiced Stop Consonants by Matching Time-domain Patterns in Pitch Periods
Author: Attila Kondacs
MIT Ph.D. Thesis, January 2005
PDF version
Abstract:
In this thesis I will be concerned with linking the observed speech signal to the configuration of articulators. Due to the potentially rapid motion of the articulators, the speech signal can be highly non-stationary. The typical linear analysis techniques that assume quasi-stationarity may not have sufficient time-frequency resolution to determine the place of articulation. I argue that the traditional low and high-level primitives of speech processing, frequency and phonemes, are inadequate and should be replaced by a representation with three layers: 1. short pitch period resonances and other spatio-temporal patterns 2. articulator configuration trajectories 3. syllables. The patterns indicate articulator configuration trajectories (how the tongue, jaws, etc. are moving), which are interpreted as syllables and words. My patterns are an alternative to frequency. I use short time-domain features of the sound waveform, which can be extracted from each vowel pitch period pattern, to identify the positions of the articulators with high reliability. These features are important because by capitalizing on detailed measurements within a single pitch period, the rapid articulator movements can be tracked. No linear signal processing approach can achieve the combination of sensitivity to short term changes and measurement accuracy resulting from these nonlinear techniques. The measurements I use are neurophysiologically plausible: the auditory system could be using similar methods. I have demonstrated this approach by constructing a robust technique for categorizing the English voiced stops as the consonants B, D, or G based on the vocalic portions of their releases. The classification recognizes 93.5%, 81.8% and 86.1% of the b, d and g to ae transitions with false positive rates 2.9%, 8.7% and 2.6% respectively.
Title: RamboNodes for the Metropolitan Ad Hoc Network
Author: Jacob Beal and Seth Gilbert
Published: MIT AI Memo 2003-027, December 2003
Workshop version presented at Workshop on Dependability in Wireless Ad Hoc Networks and Sensor Networks, part of the International Conference on Dependable Systems and Networks, June 2004.
Abstract:
We present an algorithm to store data robustly in a large, geographically distributed network by means of localized regions of data storage that move in response to changing conditions. For example, data might migrate away from failures or toward regions of high demand. The PersistentNode algorithm provides this service robustly, but with limited safety guarantees. We use the RAMBO framework to transform PersistentNode into RamboNode, an algorithm that guarantees atomic consistency in exchange for increased cost and decreased liveness. In addition, a half-life analysis of RamboNode shows that it is robust against continuous low-rate failures. Finally, we provide experimental simulations for the algorithm on 2000 nodes, demonstrating how it services requests and examining how it responds to failures.
PDF version.
Title: Near-Optimal Distributed Failure Circumscription
Author: Jacob Beal
Published: AI Memo 2003-017, August 2003
Conference Version presented at PDCS 2003, Los Angeles, November 2003
Abstract:
Small failures should only disrupt a small part of a network. One way to do this is by marking the surrounding area as untrustworthy --- circumscribing the failure. This can be done with a distributed algorithm using hierarchical clustering and neighbor relations, and the resulting circumscription is near-optimal for convex failures.
postscript version, PDF version, and Conference version in postscript and PDF.
Title: A Robust Amorphous Hierarchy from Persistent Nodes
Author: Jacob Beal
Published: AI Memo 2003-012, May 2003
Conference Version presented at Communication Systems and Networks 2003, Benalmadena, Spain, September 2003
Abstract:
For a very large network deployed in space with only nearby nodes able to talk to each other, we want to do tasks like robust routing and data storage. One way to organize the network is via a hierarchy, but hierarchies often have a few critical nodes whose death can disrupt organization over long distances. I address this with a system of distributed aggregates called Persistent Nodes, such that spatially local failures disrupt the hierarchy in an area proportional to the diameter of the failure. I describe and analyze this system, which has been implemented in simulation.
postscript version, PDF version, and conference version.
Title: Persistent Nodes for Reliable Memory in Geographically Local Networks
Author: Jacob Beal
Published: AI Memo 2003-011, April 2003
Abstract:
A Persistent Node is a redundant distributed mechanism for storing a key/value pair reliably in a geographically local network. In this paper, I develop a method of establishing Persistent Nodes in an amorphous matrix. I address issues of construction, usage, atomicity guarantees and reliability in the face of stopping failures. Applications include routing, congestion control, and data storage in gigascale networks.
postscript version, PDF version
Title: Leveraging Learning and Language Via Communication Bootstrapping
Author: Jacob Beal
Published: AI Memo 2003-007, March 2003
Abstract:
In a Communication Bootstrapping system, peer components with different perceptual worlds invent symbols and syntax based on correlations between their percepts. I propose that Communication Bootstrapping can also be used to acquire functional definitions of words and causal reasoning knowledge. I illustrate this point with several examples, then sketch the architecture of a system in progress which attempts to execute this task.
postscript version, PDF version
Title: Leaderless Distributed Hierarchy Formation
Author: Jacob Beal
Published: AI Memo 2002-021, December 2002
Abstract:
I present a system for robust leaderless organization of an amorphous network into hierarchical clusters. This system, which assumes that nodes are spatially embedded and can only talk to neighbors within a given radius, scales to networks of arbitrary size and converges rapidly. The amount of data stored at each node is logarithmic in the diameter of the network, and the hierarchical structure produces an addressing scheme such that there is an invertible relation between distance and address for any pair of nodes. The system adapts automatically to stopping failures, network partition, and reorganization.
postscript version
Title: Programmable Self-Assembly using Biologically-Inspired Multiagent Control
Author: Radhika Nagpal
Published: Autonomous Agents and Multiagent Systems Conference (AAMAS), July 2002
Abstract:
This paper presents a programming language that specifies a robust process for shape formation on a sheet of identically-programmed agents, by combining local organization primitives from epithelial cell morphogenesis and \textit{Drosophila} cell differentiation with combination rules from geometry. This work represents a significantly different approach to the design of self-organizing systems: the desired global shape is specified using an abstract geometry-based language, and the agent program is \textit{directly compiled} from the global specification. The resulting self-assembly process is extremely reliable in the face of random agent distributions, random agent death and varying agent numbers, without relying on global coordinates or centralized control.
postscript version
Title: Programmable Pattern-Formation and Scale-Independence
Author: Radhika Nagpal
Published: International Confernce on Complex Systems (ICCS), June 2002
Abstract:
This paper presents a programming language forpattern-formation on a surface of locally-interacting, identically-programmed agents, by combining local organization primitives from developmental biology with combination rules from geometry. The approach is significantly different from current approaches to the design of self-organizing systems: the desired global shape is specified using an abstract geometry-based language, and the agent program is {\em directly compiled} from the global specification. Using this approach any 2D Euclidean construction can be formed from local-interactions of the agents. In addition to being robust, the process is {\em scale-independent}, which implies that the pattern scales as the number of agents increases, with no modification of the agent program. The pattern also scales asymmetrically to produce related patterns, such as D'Arcy Thompson's famous transformations.
postscript version
Title: An Algorithm for Bootstrapping Communications
Author: Jacob Beal
Published: International Conference on Complex Systems (ICCS), June 2002
Abstract:
In a distributed model of intelligence, peer components need to communicate with one another. I present a system which enables two agents connected by a thick twisted bundle of wires to bootstrap a simple communication system from observations of a shared environment. The agents learn a large vocabulary of symbols, as well as inflections on those symbols which allow thematic role-frames to be transmitted. Language acquisition time is rapid and linear in the number of symbols and inflections. The final communication system is robust and performance degrades gradually in the face of problems.
postscript version
Title: Programming a Paintable Computer
Author: William J. Butera
Published: PhD Thesis, MIT Media Lab, Feb 2002
Abstract:
A paintable computer is defined as an agglomerate of numerous, finely dispersed, ultra-miniaturized computing particles; each positioned randomly, running asynchronously and communicating locally. Individual particles are tightly resource bound, and processing is necessarily distributed. Yet computing elements are vanishingly cheap and are regarded as freely expendable. In this regime, a limiting problem is the distribution of processing over a particle ensemble whose topology can vary unexpectedly.
The principles of material self-assembly are employed to guide the positioning of "process fragments" - autonomous, mobile pieces of a larger process. These fragments spatially position themselves and re-aggregate into a running process. We present the results of simulations to show that "process self-assembly" is viable, robust and supports a variety of useful applications on a paintable computer. We describe a hardware reference platform as an initial guide to the application domain. We describe a programming model which normatively defines the term process fragment and which provides environmental support for the fragment's mobility, scheduling and data exchange. The programming model is embodied in a simulator that supports development, test and visualization on a 2D particle ensemble. Experiments on simple combinations of fragments demonstrate robustness and explore the limits of scale invariance. Process fragments are shown interacting to approximate conservative fields, and using these fields to implement scaffolded and thermodynamic self-assembly. Four applications demonstrate practical relevance, delineate the application domain and collectively illustrate the paintable's capacity for storage, communication and signal processing. These four applications are Audio Streaming, Holistic Data Storage, Surface Bus and Image Segmentation.
pdf version
Title: Generating Communications Systems Through Shared Context
Author: Jacob Beal
Published: Master's Thesis, AI Tech Report 2002-002, January 2002
Abstract:
In a distributed model of intelligence, peer components need to communicate with one another. I present a system which enables two agents connected by a thick twisted bundle of wires to bootstrap a simple communication system from observations of a shared environment. The agents learn a large vocabulary of symbols, as well as inflections on those symbols which allow thematic role-frames to be transmitted. Language acquisition time is rapid and linear in the number of symbols and inflections. The final communication system is robust and performance degrades gradually in the face of problems.
postscript version
Title: An Algorithm for Bootstrapping Communications
Author: Jacob Beal
Published: AI Memo 2001-016, August 2001
Abstract:
I present an algorithm which allows two agents to generate a simple language based only on observations of a shared environment. Vocabulary and roles for the language are learned in linear time. Communication is robust and degrades gradually as complexity increases. Dissimilar modes of experience will lead to a shared kernel vocabulary.
postscript version
Title: Cellular Computation and Communications using Engineered Genetic Regulatory Networks
Author: Ron Weiss
Published: PhD Thesis, MIT Department of Electrical Engineering and Computer Science, Sept 2001
Abstract:

(pdf version)
Title: Programmable Self-Assembly: Constructing Global Shape using Biologically-inspired Local Interactions and Origami Mathematics
Author: Radhika Nagpal
Published: PhD Thesis, MIT Department of Electrical Engineering and Computer Science, June 2001
Abstract:
In this thesis I present a language for instructing a sheet of identically-programmed, flexible, autonomous agents (``cells'') to assemble themselves into a predetermined global shape, using local interactions. The global shape is described as a folding construction on a continuous sheet, using a set of axioms from paper-folding (origami). I provide a means of automatically deriving the cell program, executed by all cells, from the global shape description.
With this language, a wide variety of global shapes and patterns can be synthesized, using only local interactions between identically-programmed cells. Examples include flat layered shapes, all plane Euclidean constructions, and a variety of tessellation patterns. In contrast to approaches based on cellular automata or evolution, the cell program is directly derived from the global shape description and is composed from a small number of biologically-inspired primitives: gradients, neighborhood query, polarity inversion, cell-to-cell contact and flexible folding. The cell programs are robust, without relying on regular cell placement, global coordinates, or synchronous operation and can tolerate a small amount of random cell death. I show that an average cell neighborhood of 15 is sufficient to reliably self-assemble complex shapes and geometric patterns on randomly distributed cells.
The language provides many insights into the relationship between local and global descriptions of behavior, such as the advantage of constructive languages, mechanisms for achieving global robustness, and mechanisms for achieving scale-independent shapes from a single cell program. The language suggests a mechanism by which many related shapes can be created by the same cell program, in the manner of D'Arcy Thompson's famous coordinate transformations. The thesis illuminates how complex morphology and pattern can emerge from local interactions, and how one can engineer robust self-assembly.
postscript version
Title: Trans-membrane signal transduction and biochemical Turing pattern formation
Author: Mark M. Millonas and Erik M. Rauch
Preprint; AI Memo 1670, September 1999.
Abstract:
The Turing mechanism for the production of a broken spatial symmetry in an initially homogeneous system of reacting and diffusing substances has attracted much interest as a potential model for certain aspects of morphogenesis such as pre-patterning in the embryo, and has also served as a model for self-organization in more generic systems. The two features necessary for the formation of Turing patterns are short-range autocatalysis and long-range inhibition which usually only occur when the diffusion rate of the inhibitor is significantly greater than that of the activator. This observation has sometimes been used to cast doubt on applicability of the Turing mechanism to cellular patterning since many messenger molecules that diffuse between cells do so at more-or-less similar rates. Here we show that stationary, symmetry-breaking Turing patterns can form in physiologically realistic systems even when the extracellular diffusion coefficients are equal; the kinetic properties of the ``receiver" and ``transmitter" proteins responsible for signal transduction will be primary factors governing this process.
postscript version, HTML version
Title: Organizing a Global Coordinate System from Local Information on an Amorphous Computer
Author: Radhika Nagpal
Published: AI Memo 1666, August 1999.
Abstract:
This paper demonstrates that it is possible to generate a reasonably accurate coordinate system on randomly distributed processors, using only local information and local communication. By coordinate system we imply that each element assigns itself a logical coordinate that maps to its global physical location, starting with no apriori knowledge of position or orientation. The algorithm presented is inspired by biological systems that use chemical gradients to determine the position of cells. Extensive analysis and simulation results are presented. Two key results are: there is a critical minimum average neighborhood size of 15 for good accuracy and there is a fundamental limit on the resolution of any coordinate system determined strictly from local communication. We also demonstrate that using this algorithm, random distributions of processors produce significantly better accuracy than regular processor grids - such as those used by cellular automata. This has implications for discrete models of biology as well as for building smart sensor arrays.
postscript version,
Title: Amorphous Computing
Author: H. Abelson, D. Allen, D. Coore, C. Hanson, G. Homsy, T. Knight, R. Nagpal, E. Rauch, G. Sussman and R. Weiss
Published: AI Memo 1665, August 1999.
Abstract:
Amorphous computing is the development of organizational principles and programming languages for obtaining coherent behavior from the cooperation of myriads of unreliable parts that are interconnected in unknown, irregular, and time-varying ways. The impetus for amorphous computing comes from developments in microfabrication and fundamental biology, each of which is the basis of a kernel technology that makes it possible to build or grow huge numbers of almost-identical information-processing units at almost no cost. This paper sets out a research agenda for realizing the potential of amorphous computing and surveys some initial progress, both in programming and in fabrication. We describe some approaches to programming amorphous systems, which are inspired by metaphors from biology and physics. We also present the basic ideas of cellular computing, an approach to constructing digital-logic circuits within living cells by representing logic levels by concentrations DNA-binding proteins.
postscript version, PDF version
Title: Discrete, Amorphous Physical Models
Author: Erik Rauch
Published: Master's Thesis, MIT Department of Electrical Engineering and Computer Science, May 31, 1999

Abstract:
Discrete models of physical phenomena are an attractive alternative to continuous models such as partial differential equations. In discrete models, such as cellular automata, space is treated as having finitely many locations per unit volume. Physical processes are modelled by rules that typically depend on a small number of nearby locations. Such models have the feature that they depend critically on a regular (crystalline) lattice, as well as the global synchronization of all sites. We might well ask, on the grounds of minimalism, whether the global synchronization and crystalline lattice are inherent in any discrete formulation. Is it possible to do without these conditions and still have a useful physical model? Or are they somehow fundamental?
We will answer this question by presenting a class of models that are "extremely local" in the sense that the update rule does not depend on synchronization with other sites, or on detailed knowledge of the lattice geometry. All interactions involve only a single pair of sites. The models have the further advantage that they exactly conserve the analog of quantities such as momentum and energy which are conserved in physics. A framework for simulating the asynchronous, parallel model with irregular geometry on a sequential computer is be presented. Evidence is given that the models agree well qualitatively and quantitatively with continuous differential equations.
We will draw parallels between the various kinds of physical models and various computing architectures, and show that the class of models presented corresponds to a new parallel computing architecture known as an amorphous computer.
postscript version, HTML version

Title: Botanical Computing: A Developmental Approach to Generating Interconnect Topologies on an Amorphous Computer
Author: Daniel Coore
Published: PhD Thesis, MIT Department of Electrical Engineering and Computer Science, Feb 1999

Abstract:
An amorphous computing medium is a system of irregularly placed, asynchronous, locally interacting computing elements. I have demonstrated that amorphous media can be configured by a program, common to all computing elements, to generate highly complex prespecified patterns. For example, I can specify that an amorphous medium manifest a pattern representing the interconnection structure of an arbitrary electrical circuit.
My strategy is inspired by a botanical metaphor based on growing points and tropisms. To make this strategy explicit, I have developed the Growing Point Language (GPL). A growing point is a locus of activity in an amorphous medium. A growing point propagates through the medium by transferring its activity from one computing element to a neighbor. As a growing point passes through the medium it effects the differentiation of the behaviors of the computing elements it visits. The trajectory of the growing point is controlled by signals that are automatically carried through the medium from other differentiated elements. Such a response is called a tropism. In this way a GPL program can exploit locality to make crude geometric inferences.
There is a wide variety of patterns that are expressible in GPL. Examples include: Euclidean constructions, branching structures and simple text. I prove that amorphous media can be programmed to draw any prespecified planar graph, and I obtain upper bounds on the amount of storage required by the individual processors to realize such a graph. I also analyze how the effectiveness of GPL programs depends upon the distribution of the computing elements.
postscript version

Title: Toward in vivo Digital Circuits
Authors: Ron Weiss, George Homsy, Thomas F. Knight
Presented: Dimacs Workshop on Evolution as Computation, Princeton, NJ, January 1999.

Abstract:
We propose a mapping from digital logic circuits into genetic regulatory networks with the following property: the chemical activity of such a genetic network {\it in vivo} implements the computation specified by the corresponding digital circuit. Logic signals are represented by the synthesis rates of cytoplasmic DNA binding proteins. Gates consist of structural genes for output proteins, fused to promoter/operator regions that are regulated by input proteins. The modular approach for building gates allows a free choice of signal proteins and thus enables the construction of complex circuits. This paper presents simulation results that demonstrate the feasibility of this approach. Furthermore, a technique for measuring gate input/output characteristics is introduced. We will use this technique to evaluate gates constructed in our laboratory. Finally, this paper outlines automated logic design and presents BioSpice, a prototype system for the design and verification of genetic digital circuits.
postscript version of paper, html version of talk

Title: Notes on Amorphous Computing
Author: Jacob Katzenelson
Published: July 18, 2000

Abstract:
The purpose of this note is to explore and communicate ideas related to the use of amorphous computers to numerical computing and, in particular, the simulation of partial differential equations.
postscript version

Title: Cellular Gate Technology
Authors: Thomas F. Knight and Gerald Jay Sussman
Presented: Proc. UMC98, First International Conference on Unconventional Models of Computation, Auckland, NZ, January 1998.

Abstract:
We propose a biochemically plausible mechanism for constructing digital logic signals and gates of significant complexity within living cells. These mechanisms rely largely on co-opting existing biochemical machinery and binding proteins found naturally within the cell, replacing difficult protein engineering problems with more straightforward engineering of novel combinations of gene control sequences and gene coding regions.

The resulting logic technology, although slow, allows us to engineer the chemical behavior of cells for use as sensors and effectors. One promising use of such technology is the control of fabrication processes at the molecular scale.
postscript version (17 pages), html version

Title: Programming Biological Cells
Authors: Ron Weiss, George Homsy, Radhika Nagpal
Presented: 8th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '98), Wild and Crazy Ideas Session, San Jose, CA, 1998.

Abstract:
It appears that biological organisms can be harnessed as substrates for computation. Biological cells possess important characteristics, such as energy efficiency, self-reproduction, and miniature scale, that make them attractive for many applications. Examples include embedded intelligence in materials, sensing, smart medicine, and nanoscale fabrication. Vast numbers of programmed cells executing in parallel will enable cheap computation. This abstract argues that individual cells are programmable, and presents a programming paradigm for colonies of cells.
abstract

Title: An Algorithm for Group Formation in an Amorphous Computer
Authors: Radhika Nagpal and Daniel Coore
Published: Proceedings of the 10th International Conference on Parallel and Distributed Computing Systems (PDCS'98), Nevada, Oct 1998.

Abstract:
Amorphous computing \cite{white-paper} is the study of programming ultra-scale computing environments of smart sensors and actuators that communicate locally via wireless broadcast. In such environments, where individual elements have limited resources, aggregation into groups is useful for specialization, fault-tolerance, and resource allocation. This paper presents a new algorithm, called {\em clubs}, that takes advantage of the local communication to efficiently aggregate processors into groups in an amorphous computer. Time taken is proportional to the local density of processors, even in an asynchronous setting. The physical embedding of the amorphous comp uter is used to derive an upper bound on the number and density of grou ps formed. The clubs algorithm can be extended to adapt to processor failures and to find the maximal independent set (MIS) and Delta + 1 vertex coloring in O(log N) rounds, where N is the total number of elements and Delta is the maximum degree. Simulation results and example applications are presented.
PDCS paper (4 pages), AI Memo 1626 (more detail)

Title: Implementing Reaction Diffusion on an Amorphous Computer
Authors: Daniel Coore and Radhika Nagpal
Published: 1998 MIT Student Workshop on High Performance Computing in Science and Engineering, MIT/LCS/TR-737

Abstract:
Traditionally reaction-diffusion simulations have been perfo rmed on regularly discretised spaces. In an Amorphous Computer \cite{white-paper} the processors are distributed densely bu t randomly. By implementing the Gray-Scott model on an amorph ous computer simulation, we show that the patterns obtained by uniform discretisation can also be realised qualitatively on irregul ar, amorphous discretisations if diffusion is modelled correctly .
postscript version (extended abstract)

Title: Establishing a Coordinate System on an Amorphous Computer
Authors: Daniel Coore
Published: 1998 MIT Student Workshop on High Performance Computing in Science and Engineering, MIT/LCS/TR-737

Abstract:
This paper outlines an algorithm for an Amorphous Computer~\cite{white-paper} that causes each processor to assign itself a coordinate such that the resulting (logical) coordinate system maps approximately, under some affine transformation, to the physical coordinate system of the processors.
postscript version (extended abstract)

Title: Paradigms for Structure in an Amorphous Computer
Authors: Daniel Coore, Radhika Nagpal and Ron Weiss
Published: AI Memo 1614, 1997

Abstract:
Recent developments in microfabrication and nanotechnology will enable the inexpensive manufacturing of massive numbers of tiny computing elements with sensors and actuators. New programming paradigms are required for obtaining organized and coherent behavior from the cooperation of large numbers of unreliable processing elements that are interconnected in unknown, irregular, and possibly time-varying ways. {\em Amorphous computing} is the study of developing and programming such ultrascale computing environments. This paper presents an approach to programming an amorphous computer by spontaneously organizing an unstructured collection of processing elements into cooperative groups and hierarchies.
This paper introduces a structure called an {\em AC Hierarchy}, which logically organizes processors into groups at different levels of granularity. The AC hierarchy simplifies programming of an amorphous computer through new language abstractions, facilitates the design of efficient and robust algorithms, and simplifies the analysis of their performance. Several example applications are presented that greatly benefit from the AC hierarchy. This paper introduces three algorithms for constructing multiple levels of the hierarchy from an unstructured collection of processors.
postscript version