Distributed Algorithms, second edition

An Intuitive Approach
 
 
MIT Press
  • erschienen am 2. März 2018
  • |
  • 272 Seiten
 
E-Book | ePUB mit Adobe-DRM | Systemvoraussetzungen
978-0-262-34552-1 (ISBN)
 
The new edition of a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models.

This book offers students and researchers a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models. It avoids mathematical argumentation, often a stumbling block for students, teaching algorithmic thought rather than proofs and logic. This approach allows the student to learn a large number of algorithms within a relatively short span of time. Algorithms are explained through brief, informal descriptions, illuminating examples, and practical exercises. The examples and exercises allow readers to understand algorithms intuitively and from different perspectives. Proof sketches, arguing the correctness of an algorithm or explaining the idea behind fundamental results, are also included. The algorithms presented in the book are for the most part "classics,” selected because they shed light on the algorithmic design of distributed systems or on key issues in distributed computing and concurrent programming.

This second edition has been substantially revised. A new chapter on distributed transaction offers up-to-date treatment of database transactions and the important evolving area of transactional memory. A new chapter on security discusses two exciting new topics: blockchains and quantum cryptography. Sections have been added that cover such subjects as rollback recovery, fault-tolerant termination detection, and consensus for shared memory. An appendix offers pseudocode descriptions of many algorithms. Solutions and slides are available for instructors.

Distributed Algorithms can be used in courses for upper-level undergraduates or graduate students in computer science, or as a reference for researchers in the field.

  • Englisch
  • Cambridge
  • |
  • USA
MIT Press
  • Reflowable
103 B&W ILLUS.
  • 19,41 MB
978-0-262-34552-1 (9780262345521)
weitere Ausgaben werden ermittelt
Wan Fokkink is Professor of Theoretical Computer Science at the VU University, Amsterdam.
  • Intro
  • Title Page
  • Copyright Page
  • Table of Contents
  • Preface
  • 1. Introduction
  • 2. Preliminaries
  • 2.1 Mathematical Notions
  • 2.2 Message Passing
  • 2.3 Shared Memory
  • 2.4 Exercises
  • 3. Snapshots
  • 3.1 Chandy-Lamport Algorithm
  • 3.2 Lai-Yang Algorithm
  • 3.3 Peterson-Kearns Rollback Recovery Algorithm
  • 3.4 Exercises
  • 4. Waves
  • 4.1 Traversal Algorithms
  • 4.2 Tree Algorithm
  • 4.3 Echo Algorithm
  • 4.4 Exercises
  • 5. Deadlock Detection
  • 5.1 Wait-for Graphs
  • 5.2 Bracha-Toueg Algorithm
  • 5.3 Exercises
  • 6. Termination Detection
  • 6.1 Dijkstra-Scholten Algorithm
  • 6.2 Rana's Algorithm
  • 6.3 Safra's Algorithm
  • 6.4 Weight Throwing
  • 6.5 Fault-Tolerant Weight Throwing
  • 6.6 Exercises
  • 7. Garbage Collection
  • 7.1 Reference Counting
  • 7.2 Garbage Collection Implies Termination Detection
  • 7.3 Tracing
  • 7.4 Exercises
  • 8. Routing
  • 8.1 Chandy-Misra Algorithm
  • 8.2 Merlin-Segall Algorithm
  • 8.3 Toueg's Algorithm
  • 8.4 Frederickson's Algorithm
  • 8.5 Packet Switching
  • 8.6 Routing on the Internet
  • 8.7 Exercises
  • 9. Election
  • 9.1 Election in Rings
  • 9.2 Tree Election Algorithm
  • 9.3 Echo Algorithm with Extinction
  • 9.4 Minimum Spanning Trees
  • 9.5 Exercises
  • 10. Anonymous Networks
  • 10.1 Impossibility of Election in Anonymous Rings
  • 10.2 Probabilistic Algorithms
  • 10.3 Itai-Rodeh Election Algorithm for Rings
  • 10.4 Echo Algorithm with Extinction for Anonymous Networks
  • 10.5 Computing the Size of an Anonymous Ring Is Impossible
  • 10.6 Itai-Rodeh Ring Size Algorithm
  • 10.7 Election in IEEE 1394
  • 10.8 Exercises
  • 11. Synchronous Networks
  • 11.1 Awerbuch's Synchronizer
  • 11.2 Bounded Delay Networks with Local Clocks
  • 11.3 Election in Anonymous Rings with Bounded Expected Delay
  • 11.4 Exercises
  • 12. Consensus with Crash Failures
  • 12.1 Impossibility of 1-Crash Consensus
  • 12.2 Bracha-Toueg Crash Consensus Algorithm
  • 12.3 Failure Detectors
  • 12.4 Consensus with a Weakly Accurate Failure Detector
  • 12.5 Chandra-Toueg Algorithm
  • 12.6 Consensus for Shared Memory
  • 12.7 Exercises
  • 13. Consensus with Byzantine Failures
  • 13.1 Bracha-Toueg Byzantine Consensus Algorithm
  • 13.2 Mahaney-Schneider Synchronizer
  • 13.3 Lamport-Shostak-Pease Broadcast Algorithm
  • 13.4 Lamport-Shostak-Pease Authentication Algorithm
  • 13.5 Exercises
  • 14. Mutual Exclusion
  • 14.1 Ricart-Agrawala Algorithm
  • 14.2 Raymond's Algorithm
  • 14.3 Agrawal-El Abbadi Algorithm
  • 14.4 Peterson's Algorithm
  • 14.5 Bakery Algorithm
  • 14.6 Fischer's Algorithm
  • 14.7 Test-and-Test-and-Set Lock
  • 14.8 Queue Locks
  • 14.9 Exercises
  • 15. Barriers
  • 15.1 Sense-Reversing Barrier
  • 15.2 Combining Tree Barrier
  • 15.3 Tournament Barrier
  • 15.4 Dissemination Barrier
  • 15.5 Exercises
  • 16. Distributed Transactions
  • 16.1 Serialization
  • 16.2 Two- and Three-Phase Commit Protocols
  • 16.3 Transactional Memory
  • 16.4 Exercises
  • 17. Self-Stabilization
  • 17.1 Dijkstra's Token Ring for Mutual Exclusion
  • 17.2 Arora-Gouda Spanning Tree Algorithm
  • 17.3 Afek-Kutten-Yung Spanning Tree Algorithm
  • 17.4 Exercises
  • 18. Security
  • 18.1 Basic Techniques
  • 18.2 Blockchains
  • 18.3 Quantum Cryptography
  • 18.4 Exercises
  • 19. Online Scheduling
  • 19.1 Jobs
  • 19.2 Schedulers
  • 19.3 Resource Access Control
  • 19.4 Exercises
  • A. Appendix: Pseudocode Descriptions
  • A.1 Chandy-Lamport Snapshot Algorithm
  • A.2 Lai-Yang Snapshot Algorithm
  • A.3 Cidon's Depth-First Search Algorithm
  • A.4 Tree Algorithm
  • A.5 Echo Algorithm
  • A.6 Shavit-Francez Termination Detection Algorithm
  • A.7 Rana's Termination Detection Algorithm
  • A.8 Safra's Termination Detection Algorithm
  • A.9 Weight-Throwing Termination Detection Algorithm
  • A.10 Chandy-Misra Routing Algorithm
  • A.11 Merlin-Segall Routing Algorithm
  • A.12 Toueg's Routing Algorithm
  • A.13 Frederickson's Breadth-First Search Algorithm
  • A.14 Dolev-Klawe-Rodeh Election Algorithm
  • A.15 Gallager-Humblet-Spira Minimum Spanning Tree Algorithm
  • A.16 IEEE 1394 Election Algorithm
  • A.17 Awerbuch's Synchronizer
  • A.18 Ricart-Agrawala Mutual Exclusion Algorithm
  • A.19 Raymond's Mutual Exclusion Algorithm
  • A.20 Agrawal-El Abbadi Mutual Exclusion Algorithm
  • A.21 MCS Queue Lock
  • A.22 CLH Queue Lock with Timeouts
  • A.23 Afek-Kutten-Yung Spanning Tree Algorithm
  • References
  • Index

Dateiformat: ePUB
Kopierschutz: Adobe-DRM (Digital Rights Management)

Systemvoraussetzungen:

Computer (Windows; MacOS X; Linux): Installieren Sie bereits vor dem Download die kostenlose Software Adobe Digital Editions (siehe E-Book Hilfe).

Tablet/Smartphone (Android; iOS): Installieren Sie bereits vor dem Download die kostenlose App Adobe Digital Editions (siehe E-Book Hilfe).

E-Book-Reader: Bookeen, Kobo, Pocketbook, Sony, Tolino u.v.a.m. (nicht Kindle)

Das Dateiformat ePUB ist sehr gut für Romane und Sachbücher geeignet - also für "fließenden" Text ohne komplexes Layout. Bei E-Readern oder Smartphones passt sich der Zeilen- und Seitenumbruch automatisch den kleinen Displays an. Mit Adobe-DRM wird hier ein "harter" Kopierschutz verwendet. Wenn die notwendigen Voraussetzungen nicht vorliegen, können Sie das E-Book leider nicht öffnen. Daher müssen Sie bereits vor dem Download Ihre Lese-Hardware vorbereiten.

Bitte beachten Sie bei der Verwendung der Lese-Software Adobe Digital Editions: wir empfehlen Ihnen unbedingt nach Installation der Lese-Software diese mit Ihrer persönlichen Adobe-ID zu autorisieren!

Weitere Informationen finden Sie in unserer E-Book Hilfe.


Download (sofort verfügbar)

46,99 €
inkl. 7% MwSt.
Download / Einzel-Lizenz
ePUB mit Adobe-DRM
siehe Systemvoraussetzungen
E-Book bestellen