Fault-tolerant simulation of population protocols

DOI10.1007/S00446-020-00377-0zbMATH Open1497.68041arXiv1610.09435OpenAlexW3018780942MaRDI QIDQ2220403FDOQ2220403

Authors: P. Flocchini, Taisuke Izumi, Tomoko Izumi, N. Santoro, G. Viglietta, Giuseppe Antonio Di Luna 

Publication date: 22 January 2021

Published in: Distributed Computing (Search for Journal in Brave)

Abstract: In this paper we investigate the computational power of Population Protocols (PP) under some unreliable and/or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. An omission failure, a notion that this paper introduces for the first time in the context of PP, is the loss by one or both parties of the information transmitted in an interaction. The failure may or may not be detected by either party. On the other hand, in one-way models, communication happens only in one direction: only one of the two agents can change its state depending on both agents' states, and the other agent may or may not be aware of the interaction. These notions can be combined, obtaining one-way protocols with (possibly detectable) omission failures. A general question is what additional power is necessary and sufficient to completely overcome the weakness of one-way protocols and enable them to simulate two-way protocols, with and without omission failures. As a basic feature, a simulator needs to implement an atomic communication of states between two agents; this task is further complicated by the anonymity of the agents, their lack of knowledge of the system, and the limited amount of memory that they may have. We provide the first answers to these questions by presenting and analyzing several simulators, i.e., wrapper protocols converting any protocol for the standard two-way model into one running on a weaker one.

Full work available at URL: https://arxiv.org/abs/1610.09435

Recommendations

• The computational power of population protocols
• Population protocols with unreliable communication
• Population protocols and related models

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Distributed systems (68M14) Network protocols (68M12)

Cites Work

• Computation in networks of passively mobile finite-state sensors
• The computational power of population protocols
• Fast computation by population protocols with a leader
• Title not available (Why is that?)
• Stably computable predicates are semilinear
• Mediated population protocols
• A simple population protocol for fast robust approximate majority
• On the convergence of population protocols when population goes to infinity
• The Dynamics of Probabilistic Population Protocols
• All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• A self-stabilizing transformer for population protocols with covering
• Passively mobile communicating machines that use restricted space
• Fast and exact majority in population protocols
• How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
• Space-optimal counting in population protocols
• Title not available (Why is that?)
• Mediated population protocols: leader election and applications
• Polylogarithmic-time leader election in population protocols
• Speed Faults in Computation by Chemical Reaction Networks
• Brief Announcement

Cited In (3)

• Protocols with constant local storage and unreliable communication
• Title not available (Why is that?)
• Population protocols with unreliable communication

This page was built for publication: Fault-tolerant simulation of population protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220403)