Amorphous computing: a research agenda for the near future
Tóm tắt
Amorphous computing presents a novel computational paradigm. The respective computational models have been recently introduced and studied in a series of works by J. Wiedermann and his Ph.D. student L. Petrů. From a computational viewpoint, amorphous computing systems differ from the classical ones almost in every aspect: they consist of a set of tiny, independent and self-powered processors or robots that can communicate wirelessly to a limited distance. The processors are randomly placed in a closed area or volume and form an ad-hoc network; in some applications they can move, either actively, or passively (e.g., in a bloodstream). Assuming the exponential progress in all sciences resulting in our ability to produce amorphous computing systems with myriads of processors, an unmatched application potential is expected profoundly to change all areas of science and life. But prior to this state of the matters theoretical and practical studies of the computational properties and efficiency of amorphous computing systems must be performed. It is expected that an indispensable part of computer science will be affected by this trend.
Tài liệu tham khảo
Abelson H et al (1999) Amorphous computing. MIT Artificial Intelligence Laboratory Memo No. 1665
Abelson H, Allen D, Coore D, Hanson Ch, Homsy G, Knight TF Jr, Nagpal R, Rauch E, Sussman GJ, Weiss R (2000) Amorphous computing. Commun ACM 43(5):74–82
Abelson H, Beal J, Sussman GJ (2007) Amorphous computing. Computer Science and Artificial Intelligence Laboratory, Technical Report, MIT-CSAIL-TR-2007-030
Angluin D, Aspnes J, Eisenstat D, Ruppert E (2007) The computational power of population protocols. Distrib Comput 20(4):279–304
Bar-Yehuda R, Goldreich O, Itai A (1992) On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization. J Comput Syst Sci 45(1):104–126
Bullis K (2008) TR10. NanoRadio. Technology Review. MIT Technology Review, Cambridge. Retrieved 27 Feb 2008
Hoyle F (1957) The black cloud. Penguin Books, London
Kahn JM, Katz RH, Pister KS (1999) Next century challenges: mobile networking for “smart dust”. In: Proceedings of the 5th annual ACM/IEEE international conference on mobile computing and networking, MobiCom ’99, ACM, Seattle, pp 271–278
Kahn JM, Katz RH, Pister KSJ (2000) Emerging challenges: mobile networking for smart dust. J Commun Netw 2:188–196
Kurzweil R (2005) The singularity is near. Viking Books, New York
Petrů L (2009) Universality in amorphous computing. PhD dissertation thesis. Department of Mathematics and Physics, Charles University, Prague
Petrů L, Wiedermann J (2007) A model of an amorphous computer and its communication protocol. In: Proceedings of SOFSEM 2007: theory and practice of computer science. LNCS, vol 4362. Springer, Berlin, pp 446–455
Petrů L, Wiedermann J (2011) A universal flying amorphous computer. In: Proceedings of unconventional computation, 10th International Conference, UC'2011, LNCS, vol 6714, Springer, pp 189–200
Sailor MJ, Link JR (2005) Smart dust: nanostructured devices in a grain of sand. Chem Commun 11:1375
Vinge V (2000) A deepness in the sky. Tor Books, New York
Warneke B, Last M, Liebowitz B, Pister KSJ (2001) Smart dust: communicating with a cubic-millimeter computer. Computer 34(1):44–51
Warneke B, Atwood B, Pister KSJ (2001b) Smart dust mote forerunners. In: Proceedings of the 14th IEEE international conference on micro electro mechanical systems, 2001, MEMS 2001, pp 357–360
Wiedermann J (2011) Nanomachine Computing by Quorum Sensing. In: Kelemen J, Kelemenová A, (eds) Computation, cooperation, and life. Essays dedicated to Gheorghe Păun on the occassion of his 60th birthday, LNCS, vol 6610, Springer, pp 203–215
Wiedermann J, Petrů L (2007) Computability in amorphous structures. In: Proceedings of CiE 2007, computation and logic in the real world. LNCS, vol 4497. Springer, Berlin, pp 781–790
Wiedermann J, Petrů L (2009a) Communicating mobile nano-machines and their computational power. In: Third international ICST conference, NanoNet 2008, Boston, MA, USA, September 14–16, 2008, Revised Selected Papers, LNICST, vol 3, part 2. Springer, Berlin, pp 123–130
Wiedermann J, Petrů L (2009b) On the universal computing power of amorphous computing systems. Theory Comput Syst 46(4):995–1010. http://www.springerlink.com/content/k2x6266k78274m05/fulltext.pdf