 |
Fundamentals of Software Engineering 5th International Conference, FSEN 2013 Tehran, Iran, April 24-26, 2013 |
 |
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.
Cited literature [27 references]
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
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