Encyclopedia of Complexity and Systems Science

Living Edition
| Editors: Robert A. Meyers

Amorphous Computing

  • Hal AbelsonEmail author
  • Jacob Beal
  • Gerald Jay Sussman
Living reference work entry
DOI: https://doi.org/10.1007/978-3-642-27737-5_18-3


Amorphous computer

A collection of computational particles dispersed irregularly on a surface or throughout a volume, where individual particles have no a priori knowledge of their positions or orientations.

Computational particle

A (possibly faulty) individual device for an amorphous computer. Each particle has modest computing power and a modest amount of memory. The particles are not synchronized, although they are all capable of operating at similar speeds, since they are fabricated by the same process. All particles are programmed identically, although each particle has means for storing local state and for generating random numbers.


A function assigning a value to every particle in an amorphous computer.


A basic amorphous computing primitive that estimates the distance from each particle to the nearest particle designated as a source of the gradient.

Definition of the Subject

The goal of amorphous computing is to identify organizational principles and...

This is a preview of subscription content, log in to check access.


Primary Literature

  1. Abelson H, Sussman GJ, Sussman J (1996) Structure and interpretation of computer programs, 2nd edn. MIT Press, CambridgezbMATHGoogle Scholar
  2. Ashe HL, Briscoe J (2006) The interpretation of morphogen gradients. Development 133:385–394CrossRefGoogle Scholar
  3. Bachrach J, Beal J (2006) Programming a sensor network as an amorphous medium. In: DCOSS 2006 postersGoogle Scholar
  4. Bachrach J, Nagpal R, Salib M, Shrobe H (2003) Experimental results and theoretical analysis of a self-organizing global coordinate system for ad hoc sensor networks. Telecommun Syst J 26(2–4):213–233. Special Issue on Wireless System NetworksGoogle Scholar
  5. Bachrach J, Beal J, Fujiwara T (2007) Continuous space-time semantics allow adaptive program execution. In: IEEE international conference on self-adaptive and self-organizing systemsGoogle Scholar
  6. Beal J (2003) A robust amorphous hierarchy from persistent nodes. In: Commun System NetworksGoogle Scholar
  7. Beal J (2004) Programming an amorphous computational medium. In: Unconventional programming paradigms international workshopGoogle Scholar
  8. Beal J (2005) Amorphous medium language. In: Large-scale multi- agent systems workshop (LSMAS). Held in Conjunction with AAMAS-05Google Scholar
  9. Beal J, Bachrach J (2006) Infrastructure for engineered emergence on sensor/actuator networks. In: IEEE intelligent systemsGoogle Scholar
  10. Beal J, Sussman G (2005) Biologically-inspired robust spatial programming. Technical report AI Memo 2005–001, MITGoogle Scholar
  11. Beebee W (2007) M68hc1 1 gunk api book. http://www.swiss.ai.mit.edu/projects/amorphous/HC11/api.html. Accessed 31 May 2017
  12. Butera W (2002) Programming a paintable computer. PhD thesis, MITGoogle Scholar
  13. Campbell J, Pillai P, Goldstein SC (2005) The robot is the tether: active, adaptive power routing for modular robots with unary inter-robot connectors. In: IROSGoogle Scholar
  14. Clement L, Nagpal R (2003) Self-assembly and self-repairing topologies. In: Workshop on adaptability in multi-agent systems, RoboCup Australian OpenGoogle Scholar
  15. Codd EF (1968) Cellular automata. Academic, New YorkzbMATHGoogle Scholar
  16. Coore D (1998) Establishing a coordinate system on an amorphous computer. In: MIT student workshop on high performance computingGoogle Scholar
  17. Coore D (1999) Botanical computing: a developmental approach to generating interconnect topologies on an amorphous computer. PhD thesis, MITGoogle Scholar
  18. Coore D, Nagpal R, Weiss R (1997) Paradigms for structure in an amorphous computer. Technical report AI Memo 1614, MITGoogle Scholar
  19. D’Hondt E, D’Hondt T (2001a) Amorphous geometry. In: ECALGoogle Scholar
  20. D’Hondt E, D’Hondt T (2001b) Experiments in amorphous geometry. In: International conference on artificial intelligenceGoogle Scholar
  21. De Rosa M, Goldstein SC, Lee P, Campbell J, Pillai P (2006) Scalable shape sculpting via hole motion: motion planning in lattice-constrained module robots. In: Proceedings of the 2006 I.E. international conference on robotics and automation (ICRA’06)Google Scholar
  22. Demers A, Greene D, Hauser C, Irish W, Larson J, Shenker S, Stuygis H, Swinehart D, Terry D (1987) Epidemic algorithms for replicated database maintenance. In: 7th ACM symposium on operating systems princplesGoogle Scholar
  23. Dust Networks (2007) http://www.dust-inc.com. Accessed 31 May 2017
  24. Ganesan D, Krishnamachari B, Woo A, Culler D, Estrin D, Wicker S (2002) An empirical study of epidemic algorithms in large scale multihop wireless networks. Technical report IRB-TR-02-003, Intel Research BerkeleyGoogle Scholar
  25. Gayle O, Coore D (2006) Self-organizing text in an amorphous environment. In: ICCSGoogle Scholar
  26. Hill J, Szewcyk R, Woo A, Culler D, Hollar S, Pister K (2000) System architecture directions for networked sensors. In: ASPLOSGoogle Scholar
  27. Huzita H, Scimemi B (1989) The algebra of paper-folding. In: First international meeting of origami science and technologyGoogle Scholar
  28. igem (2006) 2006: international genetically engineered machine competition. http://www.igem2006.com. Accessed 31 May 2007
  29. Intanagonwiwat C, Govindan R, Estrin D (2000) Directed diffusion: a scalable and robust communication paradigm for sensor networks. In: Mobile computing and networking, pp 56–67Google Scholar
  30. Kahn JM, Katz RH, Pister KS J (1999) Mobile networking for smart dust. In: ACM/IEEE international conference on mobile computing and networking (MobiCom 99)Google Scholar
  31. Katzenelson J (1999) Notes on amorphous computing. (Unpublished Draft)Google Scholar
  32. Kleinrock L, Sylvester J (1978) Optimum transmission radii for packet radio networks or why six is a magic number. In: IEEE national telecommunication conference, pp 4.3.1–4.3.5Google Scholar
  33. Knight TF, Sussman GJ (1998) Cellular gate technology. In: First international conference on unconventional models of computation (UMC98)Google Scholar
  34. Kondacs A (2003) Biologically-inspired self-assembly of 2d shapes, using global-to-local compilation In: International joint conference on artificial intelligence (IJCAI)Google Scholar
  35. Mamei M, Zambonelli F (2003) Spray computers: Frontiers of self-organization for pervasive computing. In: WOAGoogle Scholar
  36. Mamei M, Zambonelli F (2004) Spatial computing: the tota approach. In: WOA, pp 126–142Google Scholar
  37. Mamei M, Zambonelli F (2005) Physical deployment of digital pheromones through rfid technology. In: AAMAS, pp 1353–1354Google Scholar
  38. Margolus N (1988) Physics and computation. PhD thesis, MITGoogle Scholar
  39. McLurkin J (2004) Stupid robot tricks: a behavior-based distributed algorithm library for programming swarms of robots. Master’s thesis, MITGoogle Scholar
  40. Mittal V, Demirbas M, Arora A (2003) Loci: local clustering service for large scale wireless sensor networks. Technical report OSU-CISRC-2/03-TR07, Ohio State UniversityGoogle Scholar
  41. Nagpal R (1999) Organizing a global coordinate system from local information on an amorphous computer. Technical report AI Memo 1666, MITGoogle Scholar
  42. Nagpal R (2001) Programmable self-assembly: constructing global shape using biologically-inspired local interactions and origami mathematics. PhD thesis, MITGoogle Scholar
  43. Nagpal R, Mamei M (2004) Engineering amorphous computing systems. In: Bergenti F, Gleizes MP, Zambonelli F (eds) Methodologies and software engineering for agent systems, the agent-oriented software engineering handbook. Kluwer, New York, pp 303–320CrossRefGoogle Scholar
  44. Newton R, Welsh M (2004) Region streams: functional macroprogramming for sensor networks. In: First international workshop on data management for sensor networks (DMSN)Google Scholar
  45. Newton R, Morrisett G, Welsh M (2007) The regiment macroprogramming system. In: International conference on information processing in sensor networks (IPSN’07)Google Scholar
  46. Patel A, Nagpal R, Gibson M, Perrimon N (2006) The emergence of geometric order in proliferating metazoan epithelia. Nature 442:1038–1041ADSCrossRefGoogle Scholar
  47. Payton D, Daily M, Estowski R, Howard M, Lee C (2001) Pheromone robotics. Auton Robot 11:319–324CrossRefzbMATHGoogle Scholar
  48. Priyantha N, Chakraborty A, Balakrishnan H (2000) The cricket location-support system. In: ACM international conference on mobile computing and networking (ACM MOBICOM)Google Scholar
  49. Raffle H, Parkes A, Ishii H (2004) Topobo: a constructive assembly system with kinetic memory. CHI pp 647–654Google Scholar
  50. Rauch E (1999) Discrete, amorphous physical models. Master’s thesis, MITGoogle Scholar
  51. Registry of standard biological parts. http://parts.mit.edu. Accessed 31 May 2007
  52. Servat D, Drogoul A (2002) Combining amorphous computing and reactive agent-based systems: a paradigm for pervasive intelligence? In: AAMASGoogle Scholar
  53. Stoy K (2003) Emergent control of self-reconfigurable robots. PhD thesis, University of Southern DenmarkGoogle Scholar
  54. Sutherland A (2003) Towards rseam: resilient serial execution on amorphous machines. Master’s thesis, MITGoogle Scholar
  55. von Neumann J (1951) The general and logical theory of automata. In: Jeffress L (ed) Cerebral mechanisms for behavior. Wiley, New York, p 16Google Scholar
  56. Weiss R (2001) Cellular computation and communications using engineered genetic regular networks. PhD thesis, MITGoogle Scholar
  57. Weiss R, Knight T (2000) Engineered communications for microbial robotics. In: Sixth international meeting on DNA based computers (DNA6)Google Scholar
  58. Weiss R, Basu S, Hooshangi S, Kalmbach A, Karig D, Mehreja R, Netravali I (2003) Genetic circuit building blocks for cellular computation, communications, and signal processing. Nat Comput 2(1):47–84CrossRefGoogle Scholar
  59. Welsh M, Mainland G (2004) Programming sensor networks using abstract regions. In: Proceedings of the first USENIX/ACM symposium on networked systems design and implementation (NSDI’04)Google Scholar
  60. Werfel J, Bar-Yam Y, Nagpal R (2005) Building patterned structures with robot swarms. In: IJCAIGoogle Scholar
  61. Whitehouse K, Sharp C, Brewer E, Culler D (2004) Hood: a neighborhood abstraction for sensor networks. In: Proceedings of the 2nd international conference on Mobile systems, applications, and servicesGoogle Scholar

Books and Reviews

  1. Abelson H, Allen D, Coore D, Hanson C, Homsy G, Knight T, Nagpal R, Rauch E, Sussman G, Weiss R (1999) Amorphous computing. Technical report AIM-1665, MITGoogle Scholar

Copyright information

© Springer Science+Business Media LLC 2017

Authors and Affiliations

  1. 1.Computer Science and Artificial Intelligence LaboratoryMassachusetts Institute of TechnologyCambridgeUSA