In this paper we investigate the computational power of population protocols under some unreliable 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 population protocols, 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. In one-way models, on the other hand, 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. We start our investigation by providing a complete classification of all the possible models arising from the aforementioned weaknesses, and establishing the computational hierarchy of these models. We then address for each model the fundamental question of what additional power is necessary and sufficient to completely overcome the model’s weakness and make it able to simulate faultless two-way protocols; by “simulator” we mean a wrapper protocol that, implementing an atomic communication of states between two agents, converts any standard two-way protocol into one that works in a weaker model. We answer this question by presenting simulators that work under certain assumptions (e.g., additional memory, unique IDs, etc.) and by proving that simulation is impossible without such assumptions.
Fault-tolerant simulation of population protocols / Di Luna, G. A.; Flocchini, P.; Izumi, T.; Izumi, T.; Santoro, N.; Viglietta, G.. - In: DISTRIBUTED COMPUTING. - ISSN 0178-2770. - (2020). [10.1007/s00446-020-00377-0]
Fault-tolerant simulation of population protocols
Di Luna G. A.
Primo
;
2020
Abstract
In this paper we investigate the computational power of population protocols under some unreliable 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 population protocols, 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. In one-way models, on the other hand, 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. We start our investigation by providing a complete classification of all the possible models arising from the aforementioned weaknesses, and establishing the computational hierarchy of these models. We then address for each model the fundamental question of what additional power is necessary and sufficient to completely overcome the model’s weakness and make it able to simulate faultless two-way protocols; by “simulator” we mean a wrapper protocol that, implementing an atomic communication of states between two agents, converts any standard two-way protocol into one that works in a weaker model. We answer this question by presenting simulators that work under certain assumptions (e.g., additional memory, unique IDs, etc.) and by proving that simulation is impossible without such assumptions.File | Dimensione | Formato | |
---|---|---|---|
DiLuna_preprint_Fault-tolerant_2020.pdf
accesso aperto
Note: https://link.springer.com/article/10.1007/s00446-020-00377-0
Tipologia:
Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.36 MB
Formato
Adobe PDF
|
1.36 MB | Adobe PDF | |
DiLuna_Fault-tolerant_2020.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
575.32 kB
Formato
Adobe PDF
|
575.32 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.