Distributed computing : fundamentals, simulations, and advanced topics / Hagit Attiya, Jennifer Welch.

Format:

Book

Author/Creator:

Attiya, Hagit.

Contributor:

Welch, Jennifer.

Alumni and Friends Memorial Book Fund.

Series:

Wiley series on parallel and distributed computing

Language:

English

Subjects (All):

Electronic data processing--Distributed processing.

Electronic data processing.

Physical Description:

xv, 414 pages : illustrations ; 24 cm.

Edition:

Second edition.

Place of Publication:

Hoboken, NJ : Wiley-Interscience.

Summary:

* Comprehensive introduction to the fundamental results in the mathematical foundations of distributed computing * Accompanied by supporting material, such as lecture notes and solutions for selected exercises * Each chapter ends with bibliographical notes and a set of exercises * Covers the fundamental models, issues and techniques, and features some of the more advanced topics

Contents:

1.1 Distributed Systems 1

1.2 Theory of Distributed Computing 2

1.4 Relationship of Theory to Practice 4

2 Basic Algorithms in Message-Passing Systems 9

2.1 Formal Models for Message Passing Systems 9

2.1.1 Systems 9

2.1.2 Complexity Measures 13

2.1.3 Pseudocode Conventions 14

2.2 Broadcast and Convergecast on a Spanning Tree 15

2.3 Flooding and Building a Spanning Tree 19

2.4 Constructing a Depth-First Search Spanning Tree for a Specified Root 23

2.5 Constructing a Depth-First Search Spanning Tree without a Specified Root 25

3 Leader Election in Rings 31

3.1 The Leader Election Problem 31

3.2 Anonymous Rings 32

3.3 Asynchronous Rings 34

3.3.1 An O(n[superscript 2]) Algorithm 34

3.3.2 An O(n log n) Algorithm 35

3.3.3 An [Omega](n log n) Lower Bound 38

3.4 Synchronous Rings 42

3.4.1 An O(n) Upper Bound 43

3.4.2 An [Omega](n log n) Lower Bound for Restricted Algorithms 48

4 Mutual Exclusion in Shared Memory 59

4.1 Formal Model for Shared Memory Systems 60

4.1.1 Systems 60

4.1.2 Complexity Measures 62

4.1.3 Pseudocode Conventions 62

4.2 The Mutual Exclusion Problem 63

4.3 Mutual Exclusion Using Powerful Primitives 65

4.3.1 Binary Test&Set Registers 65

4.3.2 Read-Modify-Write Registers 66

4.3.3 Lower Bound on the Number of Memory States 69

4.4 Mutual Exclusion Using Read/Write Registers 71

4.4.1 The Bakery Algorithm 71

4.4.2 A Bounded Mutual Exclusion Algorithm for Two Processors 73

4.4.3 A Bounded Mutual Exclusion Algorithm for n Processors 77

4.4.4 Lower Bound on the Number of Read/Write Registers 80

4.4.5 Fast Mutual Exclusion 84

5 Fault-Tolerant Consensus 91

5.1 Synchronous Systems with Crash Failures 92

5.1.1 Formal Model 92

5.1.2 The Consensus Problem 93

5.1.3 A Simple Algorithm 93

5.1.4 Lower Bound on the Number of Rounds 95

5.2 Synchronous Systems with Byzantine Failures 99

5.2.1 Formal Model 100

5.2.2 The Consensus Problem Revisited 100

5.2.3 Lower Bound on the Ratio of Faulty Processors 101

5.2.4 An Exponential Algorithm 103

5.2.5 A Polynomial Algorithm 106

5.3 Impossibility in Asynchronous Systems 108

5.3.1 Shared Memory

The Wait-Free Case 109

5.3.2 Shared Memory

The General Case 111

5.3.3 Message Passing 119

6 Causality and Time 125

6.1 Capturing Causality 126

6.1.1 The Happens-Before Relation 126

6.1.2 Logical Clocks 128

6.1.3 Vector Clocks 129

6.1.4 Shared Memory Systems 133

6.2 Examples of Using Causality 133

6.2.1 Consistent Cuts 134

6.2.2 A Limitation of the Happens-Before Relation: The Session Problem 137

6.3 Clock Synchronization 140

6.3.1 Modeling Physical Clocks 140

6.3.2 The Clock Synchronization Problem 143

6.3.3 The Two Processors Case 144

6.3.4 An Upper Bound 146

6.3.5 A Lower Bound 148

6.3.6 Practical Clock Synchronization: Estimating Clock Differences 149

Part II Simulations

7 A Formal Model for Simulations 157

7.1 Problem Specifications 157

7.2 Communication Systems 158

7.2.1 Asynchronous Point-to-Point Message Passing 159

7.2.2 Asynchronous Broadcast 159

7.3 Processes 160

7.4 Admissibility 163

7.5 Simulations 164

7.6 Pseudocode Conventions 165

8 Broadcast and Multicast 167

8.1 Specification of Broadcast Services 168

8.1.1 The Basic Service Specification 168

8.1.2 Broadcast Service Qualities 169

8.2 Implementing a Broadcast Service 171

8.2.1 Basic Broadcast Service 172

8.2.2 Single-Source FIFO Ordering 172

8.2.3 Totally Ordered Broadcast 172

8.2.4 Causality 175

8.2.5 Reliability 177

8.3 Multicast in Groups 179

8.3.1 Specification 180

8.3.2 Implementation 181

8.4 An Application: Replication 183

8.4.1 Replicated Database 183

8.4.2 The State Machine Approach 183

9 Distributed Shared Memory 189

9.1 Linearizable Shared Memory 190

9.2 Sequentially Consistent Shared Memory 192

9.3 Algorithms 193

9.3.1 Linearizability 193

9.3.2 Sequential Consistency 194

9.4 Lower Bounds 198

9.4.1 Adding Time and Clocks to the Layered Model 198

9.4.2 Sequential Consistency 199

9.4.3 Linearizability 199

10 Fault-Tolerant Simulations of Read/Write Objects 207

10.1 Fault-Tolerant Shared Memory Simulations 208

10.2 Simple Read/Write Register Simulations 209

10.2.1 Multi-Valued from Binary 210

10.2.2 Multi-Reader from Single-Reader 215

10.2.3 Multi-Writer from Single-Writer 219

10.3 Atomic Snapshot Objects 222

10.3.1 Handshaking Procedures 223

10.3.2 A Bounded Memory Simulation 225

10.4 Simulating Shared Registers in Message-Passing Systems 229

11 Simulating Synchrony 239

11.1 Synchronous Message-Passing Specification 240

11.2 Simulating Synchronous Processors 241

11.3 Simulating Synchronous Processors and Synchronous Communication 243

11.3.1 A Simple Synchronizer 243

11.3.2 Application: Constructing a Breadth-First Search Tree 247

11.4 Local vs. Global Simulations 247

12 Improving the Fault Tolerance of Algorithms 251

12.2 Modeling Synchronous Processors and Byzantine Failures 253

12.3 Simulating Identical Byzantine Failures on Top of Byzantine Failures 255

12.3.1 Definition of Identical Byzantine 255

12.3.2 Simulating Identical Byzantine 256

12.4 Simulating Omission Failures on Top of Identical Byzantine Failures 258

12.4.1 Definition of Omission 259

12.4.2 Simulating Omission 259

12.5 Simulating Crash Failures on Top of Omission Failures 264

12.5.1 Definition of Crash 264

12.5.2 Simulating Crash 265

12.6 Application: Consensus in the Presence of Byzantine Failures 268

12.7 Asynchronous Identical Byzantine on Top of Byzantine Failures 269

12.7.1 Definition of Asynchronous Identical Byzantine 269

12.7.2 Definition of Asynchronous Byzantine 270

12.7.3 Simulating Asynchronous Identical Byzantine 270

13 Fault-Tolerant Clock Synchronization 277

13.1 Problem Definition 277

13.2 The Ratio of Faulty Processors 279

13.3 A Clock Synchronization Algorithm 284

13.3.1 Timing Failures 284

13.3.2 Byzantine Failures 290

13.4 Practical Clock Synchronization: Identifying Faulty Clocks 291

Part III Advanced Topics

14 Randomization 297

14.1 Leader Election: A Case Study 297

14.1.1 Weakening the Problem Definition 297

14.1.2 Synchronous One-Shot Algorithm 299

14.1.3 Synchronous Iterated Algorithm and Expectation 300

14.1.4 Asynchronous Systems and Adversaries 302

14.1.5 Impossibility of Uniform Algorithms 303

14.1.6 Summary of Probabilistic Definitions 303

14.2 Mutual Exclusion with Small Shared Variables 305

14.3 Consensus 308

14.3.1 The General Algorithm Scheme 309

14.3.2 A Common Coin with Constant Bias 314

14.3.3 Tolerating Byzantine Failures 315

14.3.4 Shared Memory Systems 316

15 Wait-Free Simulations of Arbitrary Objects 321

15.1 Example: A FIFO Queue 322

15.2 The Wait-Free Hierarchy 326

15.3 Universality 327

15.3.1 A Nonblocking Simulation Using Compare&Swap 328

15.3.2 A Nonblocking Algorithm Using Consensus Objects 329

15.3.3 A Wait-Free Algorithm Using Consensus Objects 332

15.3.4 Bounding the Memory Requirements 335

15.3.5 Handling Nondeterminism 337

15.3.6 Employing Randomized Consensus 338

16 Problems Solvable in Asynchronous Systems 343

16.1 k-Set Consensus 344

16.2 Approximate Agreement 352

16.2.1 Known Input Range 352

16.2.2 Unknown Input Range 354

16.3 Renaming 356

16.3.1 The Wait-Free Case 357

16.3.2 The General Case 359

16.3.3 Long-Lived Renaming 360

16.4 k-Exclusion and k-Assignment 361

16.4.1 An Algorithm for k-Exclusion 362

16.4.2 An Algorithm for k-Assignment 364

17 Solving Consensus in Eventually Stable Systems 369

17.1 Preserving Safety in Shared Memory Systems 370

17.2 Failure Detectors 372

17.3 Solving Consensus using Failure

Detectors 373

17.3.1 Solving Consensus with [diamond]S 373

17.3.2 Solving Consensus with S 375

17.3.3 Solving Consensus with [Omega] 376

17.4 Implementing Failure Detectors 377

17.5 State Machine Replication with Failure Detectors 377.

Notes:

Includes bibliographical references (pages 381-400) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Alumni and Friends Memorial Book Fund.

ISBN:

0471453242

OCLC:

54046856

Publisher Number:

c2004.