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:

I  McGraw-Hill UK  I  McGraw-Hill USA  I  Barnes&Noble  I  Amazon USA  I  Amazon UK  I  Internet Bookshop, UK  I




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. 


 
 

TABLE OF CONTENTS

See more details in formatted form. 
Contents i
List of Algorithms vii
Preface ix

Part I Fundamentals

1
1 Introduction 3
1.1 Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Theory of Distributed Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Relationship of Theory to Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Basic Algorithms in Message Passing Systems  9
2.1 Formal Model for Message Passing Systems . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Broadcast and Convergecast on a Spanning Tree . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Flooding and Building a Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Constructing a Depth­First Search Spanning Tree for a Specified Root . . . . . . 24
2.5 Constructing a Depth­First Search Spanning Tree without a Specified Root . . 26
3 Leader Election in Rings 31
3.1 The Leader Election Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Anonymous Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Asynchronous Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Synchronous Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 Mutual Exclusion in Shared Memory  61
4.1 Formal Model for Shared Memory Systems . . . . . . . . . . . . . . . . . . . . . . . . . 62 
4.2 The Mutual Exclusion Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3 Mutual Exclusion Using Powerful Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4 Mutual Exclusion Using Read/Write Registers . . . . . . . . . . . . . . . . . . . . . . . . 72
5 Fault-Tolerant Consensus  91
5.1 Synchronous Systems with Crash Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.2 Synchronous Systems with Byzantine Failures . . . . . . . . . . . . . . . . . . . . . . . . 102 
5.3 Impossibility in Asynchronous Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6 Causality and Time  129
6.1 Capturing Causality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.2 Examples of Using Causality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.3 Clock Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

Part II Simulations 

159
7 A Formal Model for Simulations  161
7.1 Problem Specifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
7.2 Communication Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.3 Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.4 Admissibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.5 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.6 Pseudocode Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8 Broadcast and Multicast  171
8.1 Specification of Broadcast Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
8.2 Implementing a Broadcast Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.3 Multicast in Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
8.4 An Application: Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
9 Distributed Shared Memory  195
9.1 Linearizable Shared Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
9.2 Sequentially Consistent Shared Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
9.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
9.4 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
10 Fault-Tolerant Simulations of Read/Write Objects  213
10.1 Fault-Tolerant Shared Memory Simulations . . . . . . . . . . . . . . . . . . . . . . . . 214
10.2 Simple Read/Write Register Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
10.3 Atomic Snapshot Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
10.4 Simulating Shared Registers in Message-Passing Systems . . . . . . . . . . . . . . 235
11 Simulating Synchrony  245
11.1 Synchronous Message Passing Specification . . . . . . . . . . . . . . . . . . . . . . . 246
11.2 Simulating Synchronous Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
11.3 Simulating Synchronous Processors and Synchronous Communication . . . . 249
11.4 Local vs. Global Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
12 Improving the Fault-Tolerance of Algorithms  257
12.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
12.2 Modeling Synchronous Processors and Byzantine Failures . . . . . . . . . . . . . 259
12.3 Simulating Identical Byzantine Failures on Top of Byzantine Failures . . . . . . 261
12.4 Simulating Omission Failures on Top of Identical Byzantine Failures . . . . . . 265
12.5 Simulating Crash Failures on Top of Omission Failures . . . . . . . . . . . . . . . . 271
12.6 Application: Consensus in the Presence of Byzantine Failures . . . . . . . . . . . 275
12.7 Asynchronous Identical Byzantine on Top of Byzantine Failures . . . . . . . . . 276
13 Fault-Tolerant Clock Synchronization  283
13.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
13.2 The Ratio of Faulty Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
13.3 A Clock Synchronization Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

Part III Advanced Topics 

301
14 Randomization  303
14.1 Leader Election: A Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
14.2 Mutual Exclusion with Small Shared Variables . . . . . . . . . . . . . . . . . . . . . . 311
14.3 Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
15 Wait-Free Simulations of Arbitrary Objects  329
15.1 Example: A FIFO Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
15.2 The Wait-Free Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
15.3 Universality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
16 Bounded Timestamps  351
16.1 Single-Generator Timestamp System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
16.2 Application: A Bounded Simulation of Multi-Reader Registers . . . . . . . . . . 365
16.3 Concurrent Timestamp System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
16.4 Application: A Bounded Simulation of Multi-Writer Registers . . . . . . . . . . . 373
17 Problems Solvable in Asynchronous Systems  377
17.1 k-Set Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
17.2 Approximate Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
17.3 Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
17.4 k-Exclusion and k-Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
18 Sparse Network Covers  405
18.1 Sparse Network Covers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
18.2 Routing with Low Memory Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
18.3 Application to Synchronizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
Bibliography  417
Index  437


 
 

CHAPTER DEPENDENCIES







ADDITIONAL MATERIAL

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