Many basic techniques in computer science have been founded on the assumption that physical computing resources are scarce but orderly, and that the cost of effective direct communication between physically distant parts of a computer system is affordable. In ubiquitous computing systems such as sensor networks, or in the design of nano-scale systems, these familiar assumptions may not hold.
What if we suppose instead that computing capacity is plentiful, but that only local communication is possible, and the exact structure of the communication network is not known in advance? This is the domain of spatial programming.
How can we program a locally connected network of randomly placed computing nodes to do a practical computing task, while taking advantage of the inherent parallel processing capacity of the network?
We believe that the organization and dynamics of biological processes may offer possibilities for the design of both hardware and software under these new conditions. This algorithm, a variation on insertion sort that is also a simplified abstract model of morphogenetic cell sorting in the development of multicellular organisms, explores how we might compute in this novel environment.
"Embedding Parallel Computation in a Stochastic Mesh Network: A Morphogenetic Approach,"
1, Article 3.