Distributed Computing (book)

From The Preface

This book aims to provide a coherent view of the theory of distributed computing, highlighting common themes and basic techniques. It introduces the reader to the fundamental issues underlying the design of distributed systems—communication, coordination, synchronization and uncertainty—and to the fundamental algorithmic ideas and lower bound techniques.
This book covers the main elements of the theory of distributed computing, in a unifying approach which emphasizes the similarities between different models, when possible, or explains inherent discrepancies, when they exist. The book presents up-to-date results in a precise, and detailed, yet accessible manner. The emphasis is on fundamental ideas, not optimizations. More difficult results are typically presented as a series of increasingly complex solutions. The book highlights techniques and results that are applicable in several places throughout the text. This approach exposes the inherent similarities in solutions to seemingly diverse problems.

The major models of distributed computing are covered, varying by the mode of communication (message passing and shared memory), by the synchrony assumptions (synchronous, asynchronous and clocked), and by the failure type (crash and Byzantine). The relationships between the various models are demonstrated by simulations showing that algorithms designed for one model can be run in another model. The book covers a variety of problem domains within the models, including: leader election, mutual exclusion, consensus and clock synchronization. It presents several recent developments, including fast mutual exclusion algorithms, distributed shared memory, the wait-free hierarchy, and sparse network covers.

The text contains many accompanying figures and examples. Each chapter ends with a set of exercises and notes that discuss practical applications in existing systems, as well as a bibliographic history of the ideas.

Main Changes From The First Edition

  • A new chapter has been added on failure detectors and their application to solving consensus in asynchronous systems.
  • The two chapters on bounded timestamps and sparse network covers have been removed.
  • New material has been added to the existing chapters on
    • fast mutual exclusion,
    • queue locks,
    • practical clock synchronization, and
    • the processor lower bound for simulating shared memory with message passing
  • Errors have been corrected and the presentation improved throughout the book, including
    • a simpler proof of the round lower bound for consensus and
    • simpler randomized consensus algorithm.

Additional Material

Additional material (exercise solutions and lecture notes for a sample course) is available for instructors only; send mail to Hagit Attiya.