Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Unbounded Allocation in Bounded Heaps Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

On the Complexity of Adding Convergence

verfasst von : Alex Klinkhamer, Ali Ebnenasir

Erschienen in: Fundamentals of Software Engineering

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Unbounded Allocation in Bounded Heaps
Nächstes Kapitel Deadlock Checking by Data Race Detection
Fußnoten
1
Low atomicity programs enable the modeling of distributed programs.
 
Literatur
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17(11), 643–644 (1974)
Arora, A.: A foundation of fault-tolerant computing. PhD thesis, The University of Texas at Austin (1992)
Arora, A., Gouda, M.G.: Closure and convergence: A foundation of fault-tolerant computing. IEEE Transactions on Software Engineering 19(11), 1015–1027 (1993)
Liu, Z., Joseph, M.: Transformation of programs for fault-tolerance. Formal Aspects of Computing 4(5), 442–469 (1992)
Arora, A., Gouda, M., Varghese, G.: Constraint satisfaction as a basis for designing nonmasking fault-tolerant systems. Journal of High Speed Networks 5(3), 293–306 (1996)
Kulkarni, S.S., Arora, A.: Automating the addition of fault-tolerance. In: Formal Techniques in Real-Time and Fault-Tolerant Systems, pp. 82–93. Springer, London (2000)
Alpern, B., Schneider, F.B.: Defining liveness. Information Processing Letters 21, 181–185 (1985)
Kulkarni, S.S., Ebnenasir, A.: Complexity issues in automated synthesis of failsafe fault-tolerance. IEEE Transactions on Dependable and Secure Computing (TDSC) 2(3), 201–215 (2005)
Gary, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman (1979)
Davis, M., Putnam, H.: A computing procedure for quantification theory. Communications of the ACM 7(3), 201–215 (1960)
Ebnenasir, A., Kulkarni, S.S.: SAT-based synthesis of fault-tolerance. In: Fast Abstracts of the International Conference on Dependable Systems and Networks (2004)
Gouda, M.: The triumph and tribulation of system stabilization. In: Helary, J.-M., Raynal, M. (eds.) WDAG 1995. LNCS, vol. 972, pp. 1–18. Springer, Heidelberg (1995)
Gouda, M.G.: The theory of weak stabilization. In: Datta, A.K., Herman, T. (eds.) WSS 2001. LNCS, vol. 2194, pp. 114–123. Springer, Heidelberg (2001)
Lamport, L., Lynch, N. : Handbook of Theoretical Computer Science: Chapter 18, Distributed Computing: Models and Methods. Elsevier Science Publishers B. V. (1990)
Nesterenko, M., Arora, A.: Stabilization-preserving atomicity refinement. Journal of Parallel and Distributed Computing 62(5), 766–791 (2002)
Demirbas, M., Arora, A.: Convergence refinement. In: Proceedings of the 22nd International Conference on Distributed Computing Systems, pp. 589–597. IEEE Computer Society, Washington, DC (2002)
Dijkstra, E.W.: A Discipline of Programming. Prentice-Hall (1990)
Arora, A., Kulkarni, S.S.: Designing masking fault-tolerance via nonmasking fault-tolerance. IEEE Transactions on Software Engineering 24(6), 435–450 (1998)
Varghese, G.: Self-stabilization by local checking and correction. PhD thesis, MIT/LCS/TR-583 (1993)
Ebnenasir, A.: Automatic Synthesis of Fault-Tolerance. PhD thesis, Michigan State University (May 2005)
Jhumka, A.: Automated design of efficient fail-safe fault tolerance. PhD thesis, Darmstadt University of Technology (2004)
Jhumka, A., Freiling, F.C., Fetzer, C., Suri, N.: An approach to synthesise safe systems. International Journal of Security and Networks 1(1/2), 62–74 (2006)
Bonakdarpour, B., Kulkarni, S.S.: Exploiting symbolic techniques in automated synthesis of distributed programs with large state space. In: Proceedings of the 27th International Conference on Distributed Computing Systems, pp. 3–10. IEEE Computer Society, Washington, DC (2007)
Abujarad, F., Kulkarni, S.S.: Automated constraint-based addition of nonmasking and stabilizing fault-tolerance. Theoretical Computer Science 412(33), 4228–4246 (2011)
Farahat, A., Ebnenasir, A.: A lightweight method for automated design of convergence in network protocols. ACM Transactions on Autonomous and Adaptive Systems (TAAS) 7(4), 38:1–38:36 (2012)
Ebnenasir, A., Farahat, A.: Swarm synthesis of convergence for symmetric protocols. In: Proceedings of the Ninth European Dependable Computing Conference, pp. 13–24 (2012)
Bonakdarpour, B., Kulkarni, S.S.: Revising distributed UNITY programs is NP-complete. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 408–427. Springer, Heidelberg (2008)
Metadaten
Titel
On the Complexity of Adding Convergence
verfasst von
Alex Klinkhamer
Ali Ebnenasir
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Buch
Fundamentals of Software Engineering

Print ISBN: 978-3-642-40212-8

Electronic ISBN: 978-3-642-40213-5

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-3-642-40213-5_2

Premium Partner

    Bildnachweise