On the Complexity of Adding Convergence - Fundamentals of Software Engineering Access content directly
Conference Papers Year : 2013

On the Complexity of Adding Convergence

Alex Klinkhamer
  • Function : Author
  • PersonId : 1007024
Ali Ebnenasir
  • Function : Author
  • PersonId : 999411


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.
Fichier principal
Vignette du fichier
978-3-642-40213-5_2_Chapter.pdf (338.04 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01514662 , version 1 (26-04-2017)





Alex Klinkhamer, Ali Ebnenasir. On the Complexity of Adding Convergence. 5th International Conference on Fundamentals of Software Engineering (FSEN), Apr 2013, Tehran, Iran. pp.17-33, ⟨10.1007/978-3-642-40213-5_2⟩. ⟨hal-01514662⟩
39 View
42 Download



Gmail Facebook X LinkedIn More