Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, April 26, 2017 - 3:22:04 PM
Last modification on : Saturday, February 27, 2021 - 3:52:02 PM
Long-term archiving on: : Thursday, July 27, 2017 - 12:58:47 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views


Files downloads