Skip to main content
SpringerLink
Log in

Amorphous Computing

  • Living reference work entry
  • First Online:
Encyclopedia of Complexity and Systems Science

  • 252 Accesses

Glossary

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.

Field:

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

Gradient:

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 via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Bibliography

Primary Literature

  • Abelson H, Sussman GJ, Sussman J (1996) Structure and interpretation of computer programs, 2nd edn. MIT Press, Cambridge

    MATH  Google Scholar 

  • Ashe HL, Briscoe J (2006) The interpretation of morphogen gradients. Development 133:385–394

    Article  Google Scholar 

  • Bachrach J, Beal J (2006) Programming a sensor network as an amorphous medium. In: DCOSS 2006 posters

    Google Scholar 

  • 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 Networks

    Google Scholar 

  • 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 systems

    Google Scholar 

  • Beal J (2003) A robust amorphous hierarchy from persistent nodes. In: Commun System Networks

    Google Scholar 

  • Beal J (2004) Programming an amorphous computational medium. In: Unconventional programming paradigms international workshop

    Google Scholar 

  • Beal J (2005) Amorphous medium language. In: Large-scale multi- agent systems workshop (LSMAS). Held in Conjunction with AAMAS-05

    Google Scholar 

  • Beal J, Bachrach J (2006) Infrastructure for engineered emergence on sensor/actuator networks. In: IEEE intelligent systems

    Google Scholar 

  • Beal J, Sussman G (2005) Biologically-inspired robust spatial programming. Technical report AI Memo 2005–001, MIT

    Google Scholar 

  • Beebee W (2007) M68hc1 1 gunk api book. http://www.swiss.ai.mit.edu/projects/amorphous/HC11/api.html. Accessed 31 May 2017

  • Butera W (2002) Programming a paintable computer. PhD thesis, MIT

    Google Scholar 

  • 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: IROS

    Google Scholar 

  • Clement L, Nagpal R (2003) Self-assembly and self-repairing topologies. In: Workshop on adaptability in multi-agent systems, RoboCup Australian Open

    Google Scholar 

  • Codd EF (1968) Cellular automata. Academic, New York

    MATH  Google Scholar 

  • Coore D (1998) Establishing a coordinate system on an amorphous computer. In: MIT student workshop on high performance computing

    Google Scholar 

  • Coore D (1999) Botanical computing: a developmental approach to generating interconnect topologies on an amorphous computer. PhD thesis, MIT

    Google Scholar 

  • Coore D, Nagpal R, Weiss R (1997) Paradigms for structure in an amorphous computer. Technical report AI Memo 1614, MIT

    Google Scholar 

  • D’Hondt E, D’Hondt T (2001a) Amorphous geometry. In: ECAL

    Google Scholar 

  • D’Hondt E, D’Hondt T (2001b) Experiments in amorphous geometry. In: International conference on artificial intelligence

    Google Scholar 

  • 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 

  • 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 princples

    Google Scholar 

  • Dust Networks (2007) http://www.dust-inc.com. Accessed 31 May 2017

  • 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 Berkeley

    Google Scholar 

  • Gayle O, Coore D (2006) Self-organizing text in an amorphous environment. In: ICCS

    Google Scholar 

  • Hill J, Szewcyk R, Woo A, Culler D, Hollar S, Pister K (2000) System architecture directions for networked sensors. In: ASPLOS

    Google Scholar 

  • Huzita H, Scimemi B (1989) The algebra of paper-folding. In: First international meeting of origami science and technology

    Google Scholar 

  • igem (2006) 2006: international genetically engineered machine competition. http://www.igem2006.com. Accessed 31 May 2007

  • 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–67

    Google Scholar 

  • 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 

  • Katzenelson J (1999) Notes on amorphous computing. (Unpublished Draft)

    Google Scholar 

  • 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.5

    Google Scholar 

  • Knight TF, Sussman GJ (1998) Cellular gate technology. In: First international conference on unconventional models of computation (UMC98)

    Google Scholar 

  • 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 

  • Mamei M, Zambonelli F (2003) Spray computers: Frontiers of self-organization for pervasive computing. In: WOA

    Google Scholar 

  • Mamei M, Zambonelli F (2004) Spatial computing: the tota approach. In: WOA, pp 126–142

    Google Scholar 

  • Mamei M, Zambonelli F (2005) Physical deployment of digital pheromones through rfid technology. In: AAMAS, pp 1353–1354

    Google Scholar 

  • Margolus N (1988) Physics and computation. PhD thesis, MIT

    Google Scholar 

  • McLurkin J (2004) Stupid robot tricks: a behavior-based distributed algorithm library for programming swarms of robots. Master’s thesis, MIT

    Google Scholar 

  • 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 University

    Google Scholar 

  • Nagpal R (1999) Organizing a global coordinate system from local information on an amorphous computer. Technical report AI Memo 1666, MIT

    Google Scholar 

  • Nagpal R (2001) Programmable self-assembly: constructing global shape using biologically-inspired local interactions and origami mathematics. PhD thesis, MIT

    Google Scholar 

  • 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–320

    Chapter  Google Scholar 

  • 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 

  • Newton R, Morrisett G, Welsh M (2007) The regiment macroprogramming system. In: International conference on information processing in sensor networks (IPSN’07)

    Google Scholar 

  • Patel A, Nagpal R, Gibson M, Perrimon N (2006) The emergence of geometric order in proliferating metazoan epithelia. Nature 442:1038–1041

    Article  ADS  Google Scholar 

  • Payton D, Daily M, Estowski R, Howard M, Lee C (2001) Pheromone robotics. Auton Robot 11:319–324

    Article  MATH  Google Scholar 

  • 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 

  • Raffle H, Parkes A, Ishii H (2004) Topobo: a constructive assembly system with kinetic memory. CHI pp 647–654

    Google Scholar 

  • Rauch E (1999) Discrete, amorphous physical models. Master’s thesis, MIT

    Google Scholar 

  • Registry of standard biological parts. http://parts.mit.edu. Accessed 31 May 2007

  • Servat D, Drogoul A (2002) Combining amorphous computing and reactive agent-based systems: a paradigm for pervasive intelligence? In: AAMAS

    Google Scholar 

  • Stoy K (2003) Emergent control of self-reconfigurable robots. PhD thesis, University of Southern Denmark

    Google Scholar 

  • Sutherland A (2003) Towards rseam: resilient serial execution on amorphous machines. Master’s thesis, MIT

    Google Scholar 

  • von Neumann J (1951) The general and logical theory of automata. In: Jeffress L (ed) Cerebral mechanisms for behavior. Wiley, New York, p 16

    Google Scholar 

  • Weiss R (2001) Cellular computation and communications using engineered genetic regular networks. PhD thesis, MIT

    Google Scholar 

  • Weiss R, Knight T (2000) Engineered communications for microbial robotics. In: Sixth international meeting on DNA based computers (DNA6)

    Google Scholar 

  • 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–84

    Article  Google Scholar 

  • 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 

  • Werfel J, Bar-Yam Y, Nagpal R (2005) Building patterned structures with robot swarms. In: IJCAI

    Google Scholar 

  • 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 services

    Google Scholar 

Books and Reviews

  • 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, MIT

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, USA

    Hal Abelson, Jacob Beal & Gerald Jay Sussman

Authors
  1. Hal Abelson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jacob Beal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gerald Jay Sussman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hal Abelson .

Editor information

Editors and Affiliations

  1. Ramtech Ltd., Larkspur, California, USA

    Robert A. Meyers

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer Science+Business Media LLC

About this entry

Cite this entry

Abelson, H., Beal, J., Sussman, G.J. (2017). Amorphous Computing. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27737-5_18-3

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-27737-5_18-3

  • Received:

  • Accepted:

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-27737-5

  • Online ISBN: 978-3-642-27737-5

  • eBook Packages: Springer Reference Physics and AstronomyReference Module Physical and Materials ScienceReference Module Chemistry, Materials and Physics

Publish with us

Policies and ethics

Search

Navigation