Introduction to distributed algorithms /
Gerard Tel.
- Second edition.
- 1 online resource (xii, 596 pages) : digital, PDF file(s).
Title from publisher's bibliographic system (viewed on 05 Oct 2015).
Introduction: Distributed Systems Architecture and Languages Distributed Algorithms Outline of the Book Protocols Model Transition Systems and Algorithms Proving Properties of Transition Systems Causal Order of Events and Logical Clocks Additional Assumptions, Complexity Communication Protocols Balanced Sliding-window Protocol A Timer-based Protocol Routing Algorithms Destination-based Routing All-pairs Shortest-path Problem Netchange Algorithm Routing with Compact Routing Tables Hierarchical Routing Deadlock-free Packet Switching Structured Solutions Unstructured Solutions Fundamental Algorithms Wave and Traversal Algorithms Definition and Use of Wave Algorithms A Collection of Wave Algorithms Traversal Algorithms Time Complexity: Depth-first Search Election Algorithms Ring Networks Arbitrary Networks Korach-Kutten-Moran Algorithm Termination Detection Computation Trees and Forests Wave-based Solutions Anonymous Networks Deterministic Algorithms A Probabilistic Election Algorithm Computing the Network Size Snapshots Two Snapshot Algorithms Using Snapshot Algorithms Application: Deadlock Detection Sense of Direction and Orientation Election in Rings and Chordal Rings Computing in Hypercubes Complexity-related Issues Synchrony in Networks Election in Synchronous Networks Synchronizer Algorithms Application: Breadth-first Search Archimedean Assumption Fault Tolerance Fault Tolerance in Distributed Systems Reasons for Using Fault-tolerant Algorithms Robust Algorithms Stabilizing Algorithms Fault Tolerance in Asynchronous Systems Impossibility of Consensus Initially Dead Processes Deterministically Achievable Cases Probabilistic Consensus Algorithms Weak Termination Fault Tolerance in Synchronous Systems Synchronous Decision Protocols Authenticating Protocols Clock Synchronization Failure Detection Solving Consensus with a Weakly Accurate Detector Eventually Weakly Accurate Detectors Implementation of Failure Detectors Stabilization Graph Algorithms Methodology for Stabilization A Pseudocode Conventions Graphs and Networks 1 1 -- 1.2 18 -- 1.3 26 -- 1.4 36 -- Part 1 41 -- 2 43 -- 2.1 44 -- 2.2 50 -- 2.3 54 -- 2.4 64 -- 3 74 -- 3.1 76 -- 3.2 85 -- 4 103 -- 4.1 105 -- 4.2 110 -- 4.3 123 -- 4.4 132 -- 4.5 149 -- 5 155 -- 5.2 158 -- 5.3 167 -- Part 2 179 -- 6 181 -- 6.1 182 -- 6.2 190 -- 6.3 202 -- 6.4 208 -- 7 227 -- 7.2 232 -- 7.3 245 -- 7.4 260 -- 8 268 -- 8.2 276 -- 8.3 284 -- 9 307 -- 9.2 317 -- 9.3 323 -- 9.4 327 -- 10 335 -- 10.2 340 -- 10.3 344 -- 10.4 349 -- 11 356 -- 11.2 364 -- 11.3 374 -- 11.4 386 -- 12 396 -- 12.2 404 -- 12.3 408 -- 12.4 414 -- 12.5 420 -- Part 3 425 -- 13 427 -- 13.1 427 -- 13.2 429 -- 13.3 435 -- 14 437 -- 14.1 437 -- 14.2 442 -- 14.3 445 -- 14.4 451 -- 14.5 462 -- 15 469 -- 15.1 470 -- 15.2 481 -- 15.3 493 -- 16 505 -- 16.2 510 -- 16.3 511 -- 16.4 515 -- 17 520 -- 17.2 526 -- 17.3 535 -- 551 -- B 556.
Distributed algorithms have been the subject of intense development over the last twenty years. The second edition of this successful textbook provides an up-to-date introduction both to the topic, and to the theory behind the algorithms. The clear presentation makes the book suitable for advanced undergraduate or graduate courses, whilst the coverage is sufficiently deep to make it useful for practising engineers and researchers. The author concentrates on algorithms for the point-to-point message passing model, and includes algorithms for the implementation of computer communication networks. Other key areas discussed are algorithms for the control of distributed applications (wave, broadcast, election, termination detection, randomized algorithms for anonymous networks, snapshots, deadlock detection, synchronous systems), and fault-tolerance achievable by distributed algorithms. The two new chapters on sense of direction and failure detectors are state-of-the-art and will provide an entry to research in these still-developing topics.
9781139168724 (ebook)
Electronic data processing--Distributed processing--Congresses. Computer algorithms--Congresses.