On the Power of Weaker Pairwise Interaction: Fault-Tolerant Simulation of Population Protocols
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. 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. We answer this question by presenting simulators that work under certain assumptions and by proving that simulation is impossible without such assumptions.
|Conference||37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017|
Luna, G.A.D. (Giuseppe Antonio Di), Flocchini, P. (Paola), Izumi, T. (Taisuke), Izumi, T. (Tomoko), Santoro, N, & Viglietta, G. (Giovanni). (2017). On the Power of Weaker Pairwise Interaction: Fault-Tolerant Simulation of Population Protocols. In Proceedings - International Conference on Distributed Computing Systems (pp. 2472–2477). doi:10.1109/ICDCS.2017.50