On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems

Abstract : Decentralized runtime monitoring involves a set of monitors observing the behavior of system executions with respect to some correctness property. It is generally assumed that, as soon as a violation of the property is revealed by any of the monitors at runtime, some recovery code can be executed for bringing the system back to a legal state. This implicitly assumes that each monitor produces a binary opinion, true or false, and that the recovery code is launched as soon as one of these opinions is equal to false. In this paper, we formally prove that, in a failure-prone asynchronous computing model, there are correctness properties for which there is no such decentralized monitoring. We show that there exist some properties which, in order to be monitored in a wait-free decentralized manner, inherently require that the monitors produce a number of opinions larger than two. More specifically, our main result is that, for every k, 1 ≤ k ≤ n, there exists a property that requires at least k opinions to be monitored by n monitors. We also present a corresponding distributed monitor using at most k + 1 opinions, showing that our lower bound is nearly tight.
Type de document :
Pré-publication, Document de travail
2014
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01011079
Contributeur : Corentin Travers <>
Soumis le : mercredi 25 juin 2014 - 18:27:16
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : jeudi 25 septembre 2014 - 10:37:06

Fichier

rv2014TR-2014jun21-sergio.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01011079, version 1

Collections

Citation

Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers. On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems. 2014. 〈hal-01011079〉

Partager

Métriques

Consultations de la notice

102

Téléchargements de fichiers

98