|
|
Distributed
Computing ¨
Publisher's
page for the book (with table of contents) ¨
A review
from DS Online ¨
Errata for the second edition ¨
Main changes from the first edition ¨
Information about the first edition (including errata and courses using
the book) |
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
- 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 (exercise
solutions and lecture notes for a sample course) is available for instructors only;
send mail to Hagit Attiya.