On the Complexity of Adding Convergence

Abstract : This paper investigates the complexity of designing Self-Stabilizing (SS) distributed programs, where an SS program meets two properties, namely closure and convergence. Convergence requires that, from any state, the computations of an SS program reach a set of legitimate states (a.k.a. invariant). Upon reaching a legitimate state, the computations of an SS program remain in the set of legitimate states as long as no faults occur; i.e., Closure. We illustrate that, in general, the problem of augmenting a distributed program with convergence, i.e., adding convergence, is NP-complete (in the size of its state space). An implication of our NP-completeness result is the hardness of adding nonmasking fault tolerance to distributed programs, which has been an open problem for the past decade.
Type de document :
Communication dans un congrès
Farhad Arbab; Marjan Sirjani. 5th International Conference on Fundamentals of Software Engineering (FSEN), Apr 2013, Tehran, Iran. Springer Berlin Heidelberg, Lecture Notes in Computer Science, LNCS-8161, pp.17-33, 2013, Fundamentals of Software Engineering. 〈10.1007/978-3-642-40213-5_2〉
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-01514662
Contributeur : Hal Ifip <>
Soumis le : mercredi 26 avril 2017 - 15:22:04
Dernière modification le : mercredi 26 avril 2017 - 15:26:39
Document(s) archivé(s) le : jeudi 27 juillet 2017 - 12:58:47

Fichier

978-3-642-40213-5_2_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Alex Klinkhamer, Ali Ebnenasir. On the Complexity of Adding Convergence. Farhad Arbab; Marjan Sirjani. 5th International Conference on Fundamentals of Software Engineering (FSEN), Apr 2013, Tehran, Iran. Springer Berlin Heidelberg, Lecture Notes in Computer Science, LNCS-8161, pp.17-33, 2013, Fundamentals of Software Engineering. 〈10.1007/978-3-642-40213-5_2〉. 〈hal-01514662〉

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

10