Nano-Net. Third International ICST Conference, NanoNet 2008, Boston, MA, USA, September 14-16, 2008, Revised Selected Papers

Research Article

Communicating Mobile Nano-Machines and Their Computational Power

Download
329 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-02427-6_21,
        author={Jiř\^{\i} Wiedermann and Luk\^{a}š Petrů},
        title={Communicating Mobile Nano-Machines and Their Computational Power},
        proceedings={Nano-Net. Third International ICST Conference, NanoNet 2008, Boston, MA, USA, September 14-16, 2008, Revised Selected Papers},
        proceedings_a={NANO-NET},
        year={2012},
        month={5},
        keywords={molecular communication nanomachines timed probabilistic automata communication protocol universal computing},
        doi={10.1007/978-3-642-02427-6_21}
    }
    
  • Jiří Wiedermann
    Lukáš Petrů
    Year: 2012
    Communicating Mobile Nano-Machines and Their Computational Power
    NANO-NET
    Springer
    DOI: 10.1007/978-3-642-02427-6_21
Jiří Wiedermann1,*, Lukáš Petrů2,*
  • 1: Academy of Sciences of the Czech Republic
  • 2: Charles University
*Contact email: jiri.wiedermann@cs.cas.cz, lukas.petru@st.cuni.cz

Abstract

A computational model of molecularly communicating mobile nanomachines is defined. Nanomachines are modeled by a variant of finite-state automata—so-called timed probabilistic automata—augmented by a severely restricted communication mechanism capturing the main features of molecular communication. We show that for molecular communication among such motile machines an asynchronous stochastic protocol originally designed for wireless (radio) communication in so-called amorphous computers with static computational units can also be used. We design an algorithm that using the previous protocol, randomness and timing delays selects with a high probability a leader from among sets of anonymous candidates. This enables a probabilistic simulation of one of the simplest known model of a programmable computer—so-called counter automaton—proving that networks of mobile nanomachines possess universal computing power.