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 metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/hal-01514662
Contributor : Hal Ifip <>
Submitted on : Wednesday, April 26, 2017 - 3:22:04 PM
Last modification on : Wednesday, April 26, 2017 - 3:26:39 PM
Long-term archiving on: : Thursday, July 27, 2017 - 12:58:47 PM

File

978-3-642-40213-5_2_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

82

Files downloads

149