We consider the problem of simulating traditional population protocols under weaker models of communication, which include one-pway interactions (as opposed to two-pway 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-pway model in which one side is unable to detect the interaction.

Population protocols with faulty interactions: The impact of a leader / Di Luna, G. A.; Flocchini, P.; Izumi, T.; Izumi, T.; Santoro, N.; Viglietta, G.. - 10236:(2017), pp. 454-466. (Intervento presentato al convegno 10th International Conference on Algorithms and Complexity, CIAC 2017 tenutosi a Athens; Greece) [10.1007/978-3-319-57586-5_38].

Population protocols with faulty interactions: The impact of a leader

Di Luna G. A.
;
2017

Abstract

We consider the problem of simulating traditional population protocols under weaker models of communication, which include one-pway interactions (as opposed to two-pway 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-pway model in which one side is unable to detect the interaction.
2017
10th International Conference on Algorithms and Complexity, CIAC 2017
population protocols; fault-tolerance; algorithms
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Population protocols with faulty interactions: The impact of a leader / Di Luna, G. A.; Flocchini, P.; Izumi, T.; Izumi, T.; Santoro, N.; Viglietta, G.. - 10236:(2017), pp. 454-466. (Intervento presentato al convegno 10th International Conference on Algorithms and Complexity, CIAC 2017 tenutosi a Athens; Greece) [10.1007/978-3-319-57586-5_38].
File allegati a questo prodotto
File Dimensione Formato  
DiLuna_Population-protocols_2017.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 3.38 MB
Formato Adobe PDF
3.38 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1327434
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact