Fault-tolerant simulation of population protocols
From MaRDI portal
Publication:2220403
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5605125 (Why is no real title available?)
- scientific article; zbMATH DE number 6850453 (Why is no real title available?)
- A self-stabilizing transformer for population protocols with covering
- A simple population protocol for fast robust approximate majority
- All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
- Brief Announcement
- Computation in networks of passively mobile finite-state sensors
- Fast and exact majority in population protocols
- Fast computation by population protocols with a leader
- How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
- Mediated population protocols
- Mediated population protocols: leader election and applications
- Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
- On the convergence of population protocols when population goes to infinity
- Passively mobile communicating machines that use restricted space
- Polylogarithmic-time leader election in population protocols
- Space-optimal counting in population protocols
- Speed Faults in Computation by Chemical Reaction Networks
- Stably computable predicates are semilinear
- The Dynamics of Probabilistic Population Protocols
- The computational power of population protocols
Cited in
(3)
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)
