You are previewing Introduction to Distributed Algorithms, Second Edition.
O'Reilly logo
Introduction to Distributed Algorithms, Second Edition

Book Description

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.

Table of Contents

  1. Cover
  2. Title
  3. Copyright
  4. Dedication
  5. Contents
  6. Preface
  7. 1 Introduction: Distributed Systems
    1. 1.1 What is a Distributed System?
    2. 1.2 Architecture and Languages
    3. 1.3 Distributed Algorithms
    4. 1.4 Outline of the Book
  8. Part One: Protocols
    1. 2 The Model
      1. 2.1 Transition Systems and Algorithms
      2. 2.2 Proving Properties of Transition Systems
      3. 2.3 Causal Order of Events and Logical Clocks
      4. 2.4 Additional Assumptions, Complexity
      5. Exercises to Chapter 2
    2. 3 Communication Protocols
      1. 3.1 The Balanced Sliding-window Protocol
      2. 3.2 A Timer-based Protocol
      3. Exercises to Chapter 3
    3. 4 Routing Algorithms
      1. 4.1 Destination-based Routing
      2. 4.2 The All-pairs Shortest-path Problem
      3. 4.3 The Netchange Algorithm
      4. 4.4 Routing with Compact Routing Tables
      5. 4.5 Hierarchical Routing
      6. Exercises to Chapter 4
    4. 5 Deadlock-free Packet Switching
      1. 5.1 Introduction
      2. 5.2 Structured Solutions
      3. 5.3 Unstructured Solutions
      4. 5.4 Further Issues
      5. Exercises to Chapter 5
  9. Part Two: Fundamental Algorithms
    1. 6 Wave and Traversal Algorithms
      1. 6.1 Definition and Use of Wave Algorithms
      2. 6.2 A Collection of Wave Algorithms
      3. 6.3 Traversal Algorithms
      4. 6.4 Time Complexity: Depth-first Search
      5. 6.5 Remaining Issues
      6. Exercises to Chapter 6
    2. 7 Election Algorithms
      1. 7.1 Introduction
      2. 7.2 Ring Networks
      3. 7.3 Arbitrary Networks
      4. 7.4 The Korach–Kutten–Moran Algorithm
      5. Exercises to Chapter 7
    3. 8 Termination Detection
      1. 8.1 Preliminaries
      2. 8.2 Computation Trees and Forests
      3. 8.3 Wave-based Solutions
      4. 8.4 Other Solutions
      5. Exercises to Chapter 8
    4. 9 Anonymous Networks
      1. 9.1 Preliminaries
      2. 9.2 Deterministic Algorithms
      3. 9.3 A Probabilistic Election Algorithm
      4. 9.4 Computing the Network Size
      5. Exercises to Chapter 9
    5. 10 Snapshots
      1. 10.1 Preliminaries
      2. 10.2 Two Snapshot Algorithms
      3. 10.3 Using Snapshot Algorithms
      4. 10.4 Application: Deadlock Detection
      5. Exercises to Chapter 10
    6. 11 Sense of Direction and Orientation
      1. 11.1 Introduction and Definitions
      2. 11.2 Election in Rings and Chordal Rings
      3. 11.3 Computing in Hypercubes
      4. 11.4 Complexity-related Issues
      5. 11.5 Conclusions and Open Questions
      6. Exercises to Chapter 11
    7. 12 Synchrony in Networks
      1. 12.1 Preliminaries
      2. 12.2 Election in Synchronous Networks
      3. 12.3 Synchronizer Algorithms
      4. 12.4 Application: Breadth-first Search
      5. 12.5 The Archimedean Assumption
      6. Exercises to Chapter
  10. Part Three: Fault Tolerance
    1. 13 Fault Tolerance in Distributed Systems
      1. 13.1 Reasons for Using Fault-tolerant Algorithms
      2. 13.2 Robust Algorithms
      3. 13.3 Stabilizing Algorithms
    2. 14 Fault Tolerance in Asynchronous Systems
      1. 14.1 Impossibility of Consensus
      2. 14.2 Initially Dead Processes
      3. 14.3 Deterministically Achievable Cases
      4. 14.4 Probabilistic Consensus Algorithms
      5. 14.5 Weak Termination
      6. Exercises to Chapter 14
    3. 15 Fault Tolerance in Synchronous Systems
      1. 15.1 Synchronous Decision Protocols
      2. 15.2 Authenticating Protocols
      3. 15.3 Clock Synchronization
      4. Exercises to Chapter 15
    4. 16 Failure Detection
      1. 16.1 Model and Definitions
      2. 16.2 Solving Consensus with a Weakly Accurate Detector
      3. 16.3 Eventually Weakly Accurate Detectors
      4. 16.4 Implementation of Failure Detectors
      5. Exercises to Chapter 16
    5. 17 Stabilization
      1. 17.1 Introduction
      2. 17.2 Graph Algorithms
      3. 17.3 Methodology for Stabilization
      4. Exercises to Chapter 17
  11. Part Four: Appendices
    1. A Pseudocode Conventions
    2. B Graphs and Networks
  12. References
  13. Index