Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Konsistenz und Fehlertoleranz in Verteilten Systemen — Das Problem der Byzantinischen Generäle

  • Conference paper
GI — 17. Jahrestagung Computerintegrierter Arbeitsplatz im Büro

Part of the book series: Informatik-Fachberichte ((INFORMATIK,volume 156))

  • 123 Accesses

Zusammenfassung

Wir geben einen Überblick über fehlertolerante Verfahren zur Synchronisation von Verteilten Systemen. In einem derartigen System aus unabhängigen Prozessoren, die nur paarweise durch den Austausch von Nachrichten kommunizieren können, ist Synchronisation durch Hardware-Mechanismen nicht möglich, sondern nur durch algorithmische Methoden. Verlangt man von solchen Verfahren zusätzlich eine gewisse Fehlertoleranz, so wird die Aufgabe erheblich schwieriger.

Unter diesem Gesichtspunkt ist grundlagentheoretisch bislang am umfassendsten untersucht worden das Consensus Problem oder auch genannt das Problem der Byzantinischen Generäle. Hierbei wird von den fehlerfreien Prozessoren eine einmütige Entscheidung verlangt. Die Frage der Lösbarkeit und der Komplexität der entsprechenden Protokolle hängt von verschiedenen Parametern ab. Dazu gehören die Topologie des Netzwerkes, die Art und Anzahl der auftretenden Fehler und der Grad der zeitlichen Asynchronität von Prozessoren und des Kommunikationsflusses. Wir diskutieren grundlegende Methoden und Lösungsansätze für das Byzantinische Agreement und ähnliche Probleme.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 54.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 69.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

Literaturverzeichnis

  1. FCT Conf. on Foundations of Comupation Theory

    Google Scholar 

  2. FoCS IEEE Symp. on Foundations of Computation Theory

    Google Scholar 

  3. PoDC ACM Symp. on Principles of Distributed Systems

    Google Scholar 

  4. SToC ACM-SIGACT Symp. on Theory of Computing

    Google Scholar 

  5. H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg, R. Reischuk, Achievable Cases in an Asynchronous Environment, to app. Proc. 27. FoCS, 1987

    Google Scholar 

  6. C. Mohan, R. Strong, S. Finkelstein, Method for Distributed Transaction Commit and Recovery Using BA within Clusters of Processors, Proc. 2. PoDC, 1983, 89–103

    Google Scholar 

  7. M. Ben-Or, Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols, Proc. 2. PODC, 1983, 27–30

    Google Scholar 

  8. G. Bracha, An Asynchronous (n-1)/3-Resilient Consensus Protocoll, Proc. 3. PoDC, 1984, 154–162

    Google Scholar 

  9. G. Bracha, An 0(log n) Expected Rounds Randomized Byzantine Generals Algorithms, Proc. 17. SToC, 1985, 316–326

    Google Scholar 

  10. G. Bracha, S. Toueg, Asynchronous Consensus and Broadcast Protocols, J. ACM 32, 1985, 824–840

    Google Scholar 

  11. B. Coan, A Communication-Efficient Canonical Form for Fault-Tolerant Distributed Protocols, Proc. 5. PoDC, 1986, 63–72

    Google Scholar 

  12. B. Chor, C. Dwork, Randomization in Byzantine Agreement, Technical Report, 1987

    Google Scholar 

  13. B. Coan, D. Dolev, C. Dwork, L. Stockmeyer, The Distributed Firing Squad Problem,. Proc. 17. SToC, 1985, 335–345

    Google Scholar 

  14. D. Dolev, The Byzantine Generals Strike Again, J. Alg. 3, 1982, 14–30

    Article  Google Scholar 

  15. D. Dolev, C. Dwork, L. Stockmeyer, On the Minimal Synchronism Needed for Distributed Consensus, J. ACM 34, 1987, 77–97

    Article  Google Scholar 

  16. D. Dolev, M. Fischer, R. Fowler, N. Lynch, R. Strong, An Efficient Algorithm for Byzantine Agreement without Authentication, Inf. Control 52, 1982, 257–274

    Article  Google Scholar 

  17. D. Dolev, J. Halpern, R. Strong, On the Possibility and Impossibility of Achieving Clock Synchronization, Proc. 16. SToC, 1984, 504–511

    Google Scholar 

  18. D. Dolev, N. Lynch, S. Pinter, F. Stark, W. Weihl, Reaching Approximate Agreement in the Presence of Faults, J. ACM 33, 1986, 499–516

    Article  Google Scholar 

  19. C. Dwork, N. Lynch, L. Stockmeyer, Consensus in the Presence of Partial Synchrony, Proc. 3. PoDC, 1984, 103–118

    Google Scholar 

  20. C. Dwork, D. Peleg, N. Pippenger, E. Upfal, Fault Tolerance in Networks of Bounded Degree, Proc. 18. SToC, 1986, 370–379

    Google Scholar 

  21. D. Dolev, R. Reischuk, Bounds on Information Exchange for Byzantine Agreement, J. ACM 32, 1985, 191–204

    Article  Google Scholar 

  22. D. Dolev, R. Reischuk, R. Strong, ‘Eventual’ is Earlier than ’Immediate’, Proc. 23. FoCS, 1982, 196–203, to app. as Early Stopping in Byzantine Agreement, J. ACM, 1987

    Google Scholar 

  23. D. Dolev, R. Strong, Distributed Commit with Bounded Waiting, Proc. 2. Symp. on Reliability in Distributed Software and Database Systems, 1982

    Google Scholar 

  24. D. Dolev, R. Strong, Authenticated Algorithms for Byzantine Agreement, SIAM J. Comput. 12, 1983, 656–666

    Google Scholar 

  25. M. Fischer, The Consensus Problem in Unreliable Distributed Systems, Proc. 4. FCT, 1983, 127–140

    Google Scholar 

  26. M. Fischer, N. Lynch, A Lower Bound for the Time to Assure Interactive Consistency, Inf. Proc. Letters 14, 1982, 183–186

    Article  Google Scholar 

  27. M. Fischer, N. Lynch, M. Merritt, Easy Impossibility Proofs for Distributed Consensus Problems, Distr. Comp. 1, 1986, 26–39

    Google Scholar 

  28. M. Fischer, N. Lynch, M. Paterson, Impossibility of Distributed Consensus with 1 Faulty Process, J. ACM 32, 1985, 374–382

    Article  Google Scholar 

  29. J. Halpern, B. Simons, R. Strong, D. Dolev, Fault-Tolerant Clock Synchronization, Proc. 3. PoDC, 1984, 89–102

    Google Scholar 

  30. L. Lamport, The Weak Byzantine Generals Problem, J. ACM 30, 1983, 668–676

    Article  Google Scholar 

  31. L. Lamport, Using Time instead of Timeout for Fault-Tolerant Distributed Systems, ACM Tr. on Progr. Lang. and Systems 6, 1984, 254–280

    Google Scholar 

  32. J. Lundelius, N. Lynch, An Upper and Lower Bound for Clock Synchronization, Inf. Control 62, 1984, 190–204

    Google Scholar 

  33. L. Lamport, P. Melliar-Smith, Byzantine Clock Synchronisation, Proc. 3. PoDC, 1984, 68–74

    Google Scholar 

  34. L. Lamport, R. Shostak, M. Pease, The Byzantine Generals Problem, ACM Tr. on Progr. Lang. and Systems 4, 1982, 382–401

    Google Scholar 

  35. Y. Moses, D. Dolev, J. Halpern, Cheating Husbands and other Stories, Dis. Comp. 1, 1986, 167–176

    Google Scholar 

  36. M. Pease, R. Shostak, L. Lamport, Reaching Agreement in the Presence of Faults, J. ACM 27, 1980, 228–234

    Article  Google Scholar 

  37. M. Rabin, Randomized Byzantine Generals, Proc. 24. FoCS, 1983, 403–409

    Google Scholar 

  38. R. Reischuk, A New Solution for the Byzantine Generals Problem, Inf. Control 64, 1985, 23–42

    Article  Google Scholar 

  39. S. Toueg, Randomized BA, Proc. 3. PoDC, 1984, 163–178

    Google Scholar 

  40. R. Turpin, B. Coan, Extending Binary Byzantine Agreement to Multivalued Byzantine Agreement, Inf. Proc. Letters 18, 1984, 73–76

    Article  Google Scholar 

  41. S. Toueg, K. Perry, T. Srikanth, Fast Distributed Agreement, Proc. 4. PoDC, 1985, 87–101

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Theoretische Informatik, Technische Hochschule Darmstadt, D-6100, Darmstadt, Deutschland

    Rüdiger Reischuk

Authors
  1. Rüdiger Reischuk
    View author publications

    You can also search for this author in PubMed Google Scholar

Consortia

REISCHUK.DDADVSI.EARN

Editor information

Editors and Affiliations

  1. Institut für Infromatik, Technische Universität München, Arcisstraße 21, D-8000, München 2, Deutschland

    Manfred Paul

Rights and permissions

Reprints and permissions

Copyright information

© 1987 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Reischuk, R., REISCHUK.DDADVSI.EARN. (1987). Konsistenz und Fehlertoleranz in Verteilten Systemen — Das Problem der Byzantinischen Generäle. In: Paul, M. (eds) GI — 17. Jahrestagung Computerintegrierter Arbeitsplatz im Büro. Informatik-Fachberichte, vol 156. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-01110-2_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-01110-2_5

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-18478-2

  • Online ISBN: 978-3-662-01110-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation