A Universal Flying Amorphous Computer

0364445 - ÚI 2012 RIV DE eng C - Conference Paper (international conference)
Petrů, Lukáš - Wiedermann, Jiří
A Universal Flying Amorphous Computer.
Unconventional Computation. Berlin: Springer, 2011 - (Calude, C.; Kari, J.; Petre, I.; Rozenberg, G.), s. 189-200. Lecture Notes in Computer Science, 6714. ISBN 978-3-642-21340-3. ISSN 0302-9743.
[UC 2011. Unconventional Computation /10/. Turku (FI), 06.06.2011-10.06.2011]
R&D Projects: GA ČR GAP202/10/1333
Institutional research plan: CEZ:AV0Z10300504
Keywords : amorphous computing * model of computation * universality
Subject RIV: IN - Informatics, Computer Science

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 communication protocols that cannot guarantee a reliable message delivery. In this work we concentrate on a so-called flying amorphous computer whose units are in a constant motion. The units are modelled by miniature RAMs communicating via radio. We design a distributed probabilistic communication protocol and an algorithm enabling a simulation of a RAM infinite time. The underlying algorithms make use of a number of original ideas having no counterpart in the classical theory of distributed computing. Our result is the first one showing computational universality of a flying amorphous computer.
Permanent Link: http://hdl.handle.net/11104/0199930