%0 Conference Proceedings
%T On the Complexity of Adding Convergence
%+ Computer Science department [Michigan Tech]
%A Klinkhamer, Alex
%A Ebnenasir, Ali
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 5th International Conference on Fundamentals of Software Engineering (FSEN)
%C Tehran, Iran
%Y Farhad Arbab
%Y Marjan Sirjani
%I Springer Berlin Heidelberg
%3 Fundamentals of Software Engineering
%V LNCS-8161
%P 17-33
%8 2013-04-24
%D 2013
%R 10.1007/978-3-642-40213-5_2
%K Self-Stabilization
%K Convergence
%K NP-Completeness
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%2 https://inria.hal.science/hal-01514662/document
%2 https://inria.hal.science/hal-01514662/file/978-3-642-40213-5_2_Chapter.pdf
%L hal-01514662
%U https://inria.hal.science/hal-01514662
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC2
%~ IFIP-WG2-2
%~ IFIP-FSEN
%~ IFIP-LNCS-8161