Number of the records: 1

A Universal Flying Amorphous Computer

SYSNO ASEP	0364445
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	A Universal Flying Amorphous Computer
Author(s)	Petrů, Lukáš (UIVT-O) Wiedermann, Jiří (UIVT-O)_{RID, SAI, ORCID}
Source Title	Unconventional Computation. - Berlin : Springer, 2011 / Calude C.S. ; Kari J. ; Petre I. ; Rozenberg G. - ISSN 0302-9743 - ISBN 978-3-642-21340-3
Pages	s. 189-200
Number of pages	12 s.
Action	UC 2011. Unconventional Computation /10/
Event date	06.06.2011-10.06.2011
VEvent location	Turku
Country	FI - Finland
Event type	WRD
Language	eng - English
Country	DE - Germany
Keywords	amorphous computing ; model of computation ; universality
Subject RIV	IN - Informatics, Computer Science
R&D Projects	GAP202/10/1333 GA ČR - Czech Science Foundation (CSF)
CEZ	AV0Z10300504 - UIVT-O (2005-2011)
EID SCOPUS	79959320253
DOI	10.1007/978-3-642-21341-0_22
Annotation	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.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2012

Number of the records: 1