×

A robust universal flying amorphous computer. (English) Zbl 1323.68276

Calude, Cristian S. (ed.) et al., Computing with new resources. Essays dedicated to Jozef Gruska on the occasion of his 80th birthday. Cham: Springer (ISBN 978-3-319-13349-2/pbk; 978-3-319-13350-8/ebook). Lecture Notes in Computer Science 8808, 421-435 (2014).
Summary: Amorphous computers are systems that derive their computational capability from the operation of vast numbers of simple, identical, randomly distributed and locally communicating units. The wireless communication ability and the memory capacity of the computational units is severely restricted due to their minimal size. Moreover, the units originally have no identifiers and can only use simple asynchronous communication protocols that cannot guarantee a reliable message delivery. In this work we concentrate on a so-called robust flying amorphous computer whose units are in a constant motion. The units are modelled by miniature RAMs communicating via radio. For this model we design a distributed probabilistic communication protocol and an algorithm enabling a simulation of a RAM in finite time. Our model is robust in the sense that if one or several computational units fail the computer will autonomously restart and reconfigure itself in order to initiate the computation anew. The underlying algorithms make use of a number of original ideas having no counterpart in the classical theory of distributed computing.
For the entire collection see [Zbl 1318.68011].

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Reading. Addison-Wesley, MA (1974) · Zbl 0326.68005
[2] Hoyle, F.: The Black Cloud. Penguin Books, 219 p. (1957).
[3] Kurzweil R.: The Singularity is Near. Viking Books, 652 pages (2005).
[4] Petru L.: Universality in Amorphous Computing. PhD Dissertation Thesis, Dept. of Math. and Physics, Charles University, Prague (2009).
[5] Petru, L., Wiedermann, J.: A Model of an Amorphous Computer and Its Communication Protocol. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plášil, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 446–455. Springer, Heidelberg (2007) · Zbl 1131.68460 · doi:10.1007/978-3-540-69507-3_38
[6] Petrū, L., Wiedermann, J.: A Universal Flying Amorphous Computer. In: Calude, C.S., Kari, J., Petre, I., Rozenberg, G. (eds.) UC 2011. LNCS, vol. 6714, pp. 189–200. Springer, Heidelberg (2011) · Zbl 1330.68079 · doi:10.1007/978-3-642-21341-0_22
[7] Petu L., Wiedermann, J.: Flying Amorphous Computer: A Robust Model. Technical report No. 1173, Institute of Computer Science, Academy of Sciences of the Czech Republic (December 2012).
[8] Vinge, V.: A Deepness in the Sky. Tor Books, 800 p. (January 2000).
[9] Wiedermann, J., Petru, L.: Computability in Amorphous Structures. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol. 4497, pp. 781–790. Springer, Heidelberg (2007) · Zbl 1151.68412 · doi:10.1007/978-3-540-73001-9_83
[10] Wiedermann, J., Petru, L.: Communicating Mobile Nano-Machines and Their Computational Power. In: Cheng, M. (ed.) NanoNet 2008. LNICST, vol. 3, pp. 123–130. Springer, Heidelberg (2009) · doi:10.1007/978-3-642-02427-6_21
[11] Wiedermann, J., Petru, L.: On the Universal Computing Power of Amorphous Computing Systems. Theory of Computing Systems 46(4), 995–1010 (2009) · Zbl 1187.68333 · doi:10.1007/s00224-009-9178-6
[12] Wiedermann, J.: Nanomachine Computing by Quorum Sensing. In: Kelemen, J., Kelemenová, A. (eds.) Computation, Cooperation, and Life. LNCS, vol. 6610, pp. 203–215. Springer, Heidelberg (2011) · Zbl 1330.68082 · doi:10.1007/978-3-642-20000-7_17
[13] Wiedermann, J.: Amorphous Computing: A Research Agenda for the Near Future. Natural Computing 11(1), 59–63 (2012) · Zbl 1251.68113 · doi:10.1007/s11047-011-9281-x
[14] Wiedermann, J.: Computability and Non-computability Issues in Amorphous Computing. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds.) TCS 2012. LNCS, vol. 7604, pp. 1–9. Springer, Heidelberg (2012) · Zbl 1362.68081 · doi:10.1007/978-3-642-33475-7_1
[15] Wiedermann, J.: The many forms of amorphous computational systems. In: H. Zenil (Ed.): A Computable Universe. Understanding Computation and Exploring Nature As Computation, p. 243–256. World Scientific, Singapore (2013). · Zbl 1256.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.