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 interactions are detectable. If an upper bound on the number of omissions involving the leader is known, the simulation is possible in all omissive models. (C) 2018 Elsevier B.V. All rights reserved.
Population protocols with faulty interactions: The impact of a leader / Di Luna, G. A.; Flocchini, P.; Izumi, T.; Izumi, T.; Santoro, N.; Viglietta, G.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 754:(2019), pp. 35-49. [10.1016/j.tcs.2018.09.005]
Population protocols with faulty interactions: The impact of a leader
Di Luna G. A.
;
2019
Abstract
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 interactions are detectable. If an upper bound on the number of omissions involving the leader is known, the simulation is possible in all omissive models. (C) 2018 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
DiLuna_Population-protocols _2019.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
545.1 kB
Formato
Adobe PDF
|
545.1 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.