2016/10/28 by Giuseppe Antonio Di Luna, Paola Flocchini, Di Luna, Giuseppe Antonio +9
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #DNA and Biological Computing #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Stochastic processes and statistical mechanics #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1610.09435
openalex publication_date 2016/10/28 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
In this paper we investigate the computational power of Population Protocols\n(PP) under some unreliable and/or weaker interaction models. More precisely, we\nfocus on two features related to the power of interactions: omission failures\nand one-way communications. An omission failure, a notion that this paper\nintroduces for the first time in the context of PP, is the loss by one or both\nparties of the information transmitted in an interaction. The failure may or\nmay not be detected by either party. On the other hand, in one-way models,\ncommunication happens only in one direction: only one of the two agents can\nchange its state depending on both agents' states, and the other agent may or\nmay not be aware of the interaction. These notions can be combined, obtaining\none-way protocols with (possibly detectable) omission failures.\n A general question is what additional power is necessary and sufficient to\ncompletely overcome the weakness of one-way protocols and enable them to\nsimulate two-way protocols, with and without omission failures. As a basic\nfeature, a simulator needs to implement an atomic communication of states\nbetween two agents; this task is further complicated by the anonymity of the\nagents, their lack of knowledge of the system, and the limited amount of memory\nthat they may have.\n We provide the first answers to these questions by presenting and analyzing\nseveral simulators, i.e., wrapper protocols converting any protocol for the\nstandard two-way model into one running on a weaker one.\n