Distributed Computing

Distributed Computing

Fundamentals, Simulations, and Advanced Topics

By Hagit Attiya and Jennifer Welch

Published by McGraw-Hill Publishing Company, UK.

ISBN 0-07-709352 6

More information:

Order the book from:

McGraw-Hill UK
McGraw-Hill USA


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.


See more details in formatted form.

TABLE OF CONTENTS FOR "Distributed Computing Fundamentals, Simulations, and Advanced Topics"
List of Algorithmsvii
Part I Fundamentals1
1 Introduction3
1.1 Distributed Systems3
1.2 Theory of Distributed Computing4
1.3 Overview5
1.4 Relationship of Theory to Practice6
2 Basic Algorithms in Message Passing Systems9
2.1 Formal Model for Message Passing Systems9
2.2 Broadcast and Convergecast on a Spanning Tree15
2.3 Flooding and Building a Spanning Tree20
2.4 Constructing a Depth­First Search Spanning Tree for a Specified Root24
2.5 Constructing a Depth­First Search Spanning Tree without a Specified Root26
3 Leader Election in Rings31
3.1 The Leader Election Problem31
3.2 Anonymous Rings32
3.3 Asynchronous Rings34
3.4 Synchronous Rings43
4 Mutual Exclusion in Shared Memory61
4.1 Formal Model for Shared Memory Systems62
4.2 The Mutual Exclusion Problem65
4.3 Mutual Exclusion Using Powerful Primitives67
4.4 Mutual Exclusion Using Read/Write Registers72
5 Fault-Tolerant Consensus91
5.1 Synchronous Systems with Crash Failures92
5.2 Synchronous Systems with Byzantine Failures102
5.3 Impossibility in Asynchronous Systems111
6 Causality and Time129
6.1 Capturing Causality129
6.2 Examples of Using Causality138
6.3 Clock Synchronization145
Part II Simulations159
7 A Formal Model for Simulations161
7.1 Problem Specifications161
7.2 Communication Systems162
7.3 Processes164
7.4 Admissibility167
7.5 Simulations168
7.6 Pseudocode Conventions169
8 Broadcast and Multicast171
8.1 Specification of Broadcast Services172
8.2 Implementing a Broadcast Service176
8.3 Multicast in Groups184
8.4 An Application: Replication188
9 Distributed Shared Memory195
9.1 Linearizable Shared Memory196
9.2 Sequentially Consistent Shared Memory198
9.3 Algorithms198
9.4 Lower Bounds204
10 Fault-Tolerant Simulations of Read/Write Objects213
10.1 Fault-Tolerant Shared Memory Simulations214
10.2 Simple Read/Write Register Simulations216
10.3 Atomic Snapshot Objects228
10.4 Simulating Shared Registers in Message-Passing Systems235
11 Simulating Synchrony245
11.1 Synchronous Message Passing Specification246
11.2 Simulating Synchronous Processors247
11.3 Simulating Synchronous Processors and Synchronous Communication249
11.4 Local vs. Global Simulations254
12 Improving the Fault-Tolerance of Algorithms257
12.1 Overview257
12.2 Modeling Synchronous Processors and Byzantine Failures259
12.3 Simulating Identical Byzantine Failures on Top of Byzantine Failures261
12.4 Simulating Omission Failures on Top of Identical Byzantine Failures265
12.5 Simulating Crash Failures on Top of Omission Failures271
12.6 Application: Consensus in the Presence of Byzantine Failures275
12.7 Asynchronous Identical Byzantine on Top of Byzantine Failures276
13 Fault-Tolerant Clock Synchronization283
13.1 Problem Definition283
13.2 The Ratio of Faulty Processors285
13.3 A Clock Synchronization Algorithm290
Part III Advanced Topics301
14 Randomization303
14.1 Leader Election: A Case Study303
14.2 Mutual Exclusion with Small Shared Variables311
14.3 Consensus315
15 Wait-Free Simulations of Arbitrary Objects329
15.1 Example: A FIFO Queue330
15.2 The Wait-Free Hierarchy334
15.3 Universality336
16 Bounded Timestamps351
16.1 Single-Generator Timestamp System351
16.2 Application: A Bounded Simulation of Multi-Reader Registers365
16.3 Concurrent Timestamp System366
16.4 Application: A Bounded Simulation of Multi-Writer Registers373
17 Problems Solvable in Asynchronous Systems377
17.1 k-Set Consensus377
17.2 Approximate Agreement386
17.3 Renaming391
17.4 k-Exclusion and k-Assignment397
18 Sparse Network Covers405
18.1 Sparse Network Covers405
18.2 Routing with Low Memory Overhead409
18.3 Application to Synchronizers413
TABLE OF CONTENTS FOR "Distributed Computing Fundamentals, Simulations, and Advanced Topics"  




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