Elements of Distributed Computing

Front Cover
John Wiley & Sons, May 23, 2002 - Computers - 448 pages
A lucid and up-to-date introduction to the fundamentals of distributed computing systems

As distributed systems become increasingly available, the need for a fundamental discussion of the subject has grown. Designed for first-year graduate students and advanced undergraduates as well as practicing computer engineers seeking a solid grounding in the subject, this well-organized text covers the fundamental concepts in distributed computing systems such as time, state, simultaneity, order, knowledge, failure, and agreement in distributed systems.

Departing from the focus on shared memory and synchronous systems commonly taken by other texts, this is the first useful reference based on an asynchronous model of distributed computing, the most widely used in academia and industry. The emphasis of the book is on developing general mechanisms that can be applied to a variety of problems. Its examples-clocks, locks, cameras, sensors, controllers, slicers, and synchronizers-have been carefully chosen so that they are fundamental and yet useful in practical contexts.

The text's advantages include:

  • Emphasizes general mechanisms that can be applied to a variety of problems
  • Uses a simple induction-based technique to prove correctness of all algorithms
  • Includes a variety of exercises at the end of each chapter
  • Contains material that has been extensively class tested
  • Gives instructor flexibility in choosing appropriate balance between practice and theory of distributed computing
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Model of a Computation
11
Logical Clocks
27
Verifying Clock Algorithms
39
Clocks of Different Dimensions
49
Using Timestamps
65
Tokens and Quorums
81
Drinking Philosophers Problem
93
Leader Election
107
Repeated Global Computation
231
Synchronizers
245
Slicers
255
Distributed Shared Memory
271
SelfStabilization
287
Knowledge and Common Knowledge
297
Consensus Under Asynchrony
307
Consensus Under Synchrony
325

Global State
115
Observing Global Predicates
131
Observing Conjunctive Predicates
149
Channel Predicates
167
Termination Detection
177
Control of a Distributed Computation
183
Causal Message Ordering
195
Synchronous and Total Order
203
Computation of a Global Function
219
Failure Detectors
337
Solvable Problems in Asynchronous Systems
347
Checkpointing for Recovery
363
Message Logging for Recovery
375
A Partial Order
395
Bibliography
403
Index
420
Copyright

Common terms and phrases

Popular passages

Page 403 - An efficient and faulttolerant solution for distributed mutual exclusion.
Page 418 - S. Venkatesan and B. Dathan. Testing and debugging distributed programs using global predicates.

About the author (2002)

VIJAY K. GARG, PhD, is a professor in the Electrical and Computer Engineering Department at the University of Texas at Austin and a leading researcher in distributed computing systems..

Bibliographic information