2016/11/21 by Giuseppe Antonio Di Luna, Paola Flocchini, Di Luna, Giuseppe Antonio +9 · 1 citation
Computer Science · Engineering · Social Sciences · #Access Control and Trust #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1611.06864
arxiv created 2016/11/21 · openalex publication_date 2016/11/21 · arxiv updated 2016/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of simulating traditional population protocols under weaker models of communication, which include one-way interactions (as opposed to two-way interactions) and omission faults (i.e., failure by an agent to read its partner's state during an interaction), which in turn may be detectable or undetectable. We focus on the impact of a leader, and we give a complete characterization of the models in which the presence of a unique leader in the system allows the construction of simulators: when simulations are possible, we give explicit protocols; when they are not, we give proofs of impossibility. Specifically, if each agent has only a finite amount of memory, the simulation is possible only if there are no omission faults. If agents have an unbounded amount of memory, the simulation is possible as long as omissions are detectable. If an upper bound on the number of omissions involving the leader is known, the simulation is always possible, except in the one-way model in which one side is unable to detect the interaction.