The Opinion Number of Set-Agreement

Abstract : This paper carries on the effort to bridging runtime verification with distributed computabil- ity, studying necessary conditions for monitoring failure prone asynchronous distributed systems. In a previous paper (to appear in RV 2014), it has been proved that there are correctness prop- erties that require a large number of opinions (e.g., true, false, perhaps, probably true, probably no, etc.) to be monitored. The main outcome of this paper is that the need for this large num- ber of opinions is not an artifact induced by the existence of artificial constructions. Instead, monitoring an important class of properties, requiring processes to produce at most k different values does requires a large number of opinions. Specifically, our main result is a proof that it is impossible to monitor k-set-agreement in an n-process system with fewer than min{2k, n} + 1 opinions. The lower bound is shown to be tight.
Type de document :
Communication dans un congrès
Marcos K. Aguilera; Leonardo Querzoni; Marc Shapiro. OPODIS 2014 - 18th International Conference on Principles of Distributed Systems, Dec 2014, Cortina d’Ampezzo, Italy. Springer, 8878, pp.155-170, 2014, LNCS - Lecture Notes in Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01073578
Contributeur : Corentin Travers <>
Soumis le : vendredi 10 octobre 2014 - 10:12:15
Dernière modification le : mercredi 28 février 2018 - 10:23:13
Document(s) archivé(s) le : dimanche 11 janvier 2015 - 10:25:42

Fichier

chcksa.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01073578, version 1

Citation

Pierre Fraigniaud, Sergio Rajsbaum, Matthieu Roy, Corentin Travers. The Opinion Number of Set-Agreement. Marcos K. Aguilera; Leonardo Querzoni; Marc Shapiro. OPODIS 2014 - 18th International Conference on Principles of Distributed Systems, Dec 2014, Cortina d’Ampezzo, Italy. Springer, 8878, pp.155-170, 2014, LNCS - Lecture Notes in Computer Science. 〈hal-01073578〉

Partager

Métriques

Consultations de la notice

162

Téléchargements de fichiers

66