Guidelines for Verification of Population ProtocolsReport as inadecuate




Guidelines for Verification of Population Protocols - Download this document for free, or read online. Document in PDF available to download.

1 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications

Abstract : We address the problem of verification by model-checking of the basic population protocol \pp model of Angluin et al. This problem has received special attention the last two years and new tools have been proposed to deal with it. We show that the problem can be solved using the existing model-checking tools, e.g., Spin and Prism. For this, we apply the counting abstraction to obtain an abstract model of a \pp\ which can be efficiently verified by the existing model-checking tools. Moreover, this abstraction preserves the correct stabilization property of \pp. To deal with the fairness assumed in the \pp\ model, we provide two recipes. The first one gives sufficient conditions under which the \pp\ fairness can be replaced by the weak fairness implemented in Spin. We show that this recipe can be applied to several \pp\ models. In the second recipe, we show how to use the probabilistic model-checking and the tool Prism to deal completely with the fairness of the \pp\ model. The correctness of this recipe is based on existing theorems on finite discrete Markov chains.

keyword : Population protocol model-checking Spin Prism





Author: Julien Clément - Carole Delporte-Gallet - Hugues Fauconnier - Mihaela Sighireanu -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents