ISBN-10:
0262026775
ISBN-13:
9780262026772
Pub. Date:
12/06/2013
Publisher:
MIT Press
Distributed Algorithms: An Intuitive Approach

Distributed Algorithms: An Intuitive Approach

by Wan Fokkink
Current price is , Original price is $50.0. You

Temporarily Out of Stock Online

Please check back later for updated availability.

Overview

A comprehensive guide to distributed algorithms that emphasizes examples and exercises rather than mathematical argumentation.

This book offers students and researchers a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models. It avoids mathematical argumentation, often a stumbling block for students, teaching algorithmic thought rather than proofs and logic. This approach allows the student to learn a large number of algorithms within a relatively short span of time. Algorithms are explained through brief, informal descriptions, illuminating examples, and practical exercises. The examples and exercises allow readers to understand algorithms intuitively and from different perspectives. Proof sketches, arguing the correctness of an algorithm or explaining the idea behind fundamental results, are also included. An appendix offers pseudocode descriptions of many algorithms.

Distributed algorithms are performed by a collection of computers that send messages to each other or by multiple software threads that use the same shared memory. The algorithms presented in the book are for the most part “classics,” selected because they shed light on the algorithmic design of distributed systems or on key issues in distributed computing and concurrent programming.

Distributed Algorithms can be used in courses for upper-level undergraduates or graduate students in computer science, or as a reference for researchers in the field.

Product Details

ISBN-13: 9780262026772
Publisher: MIT Press
Publication date: 12/06/2013
Series: The MIT Press
Edition description: New Edition
Pages: 248
Product dimensions: 8.00(w) x 9.00(h) x 0.69(d)
Age Range: 18 Years

About the Author

Wan Fokkink is Professor of Theoretical Computer Science at the VU University, Amsterdam.

Table of Contents

Preface xi

1 Introduction 1

2 Preliminaries 3

2.1 Mathematical Notions 3

2.2 Message Passing 5

2.3 Shared Memory 10

2.4 Exercises 12

3 Snapshots 15

3.1 Chandy-Lamport Algorithm 16

3.2 Lai-Yang Algorithm 17

3.3 Peterson-Kearns Rollback Recovery Algorithm 18

3.4 Exercises 21

4 Waves 23

4.1 Traversal Algorithms 23

4.2 Tree Algorithm 26

4.3 Echo Algorithm 28

4.4 Exercises 29

5 Deadlock Detection 31

5.1 Wait-for Graphs 31

5.2 Bracha-Toueg Algorithm 32

5.3 Exercises 39

6 Termination Detection 41

6.1 Dijkstra-Scholten Algorithm 42

6.2 Rana's Algorithm 43

6.3 Safra's Algorithm 45

6.4 Weight Throwing 46

6.5 Fault-Tolerant Weight Throwing 47

6.6 Exercises 49

7 Garbage Collection 51

7.1 Reference Counting 51

7.2 Garbage Collection Implies Termination Detection 54

7.3 Tracing 54

7.4 Exercises 55

8 Routing 57

8.1 Chandy-Misra Algorithm 57

8.2 Merlin-Segall Algorithm 59

8.3 Toueg's Algorithm 62

8.4 Frederickson's Algorithm 64

8.5 Packet Switching 68

8.6 Routing on the Internet 70

8.7 Exercises 71

9 Election 75

9.1 Election in Rings 75

9.2 Tree Election Algorithm 79

9.3 Echo Algorithm with Extinction 80

9.4 Minimum Spanning Trees 81

9.5 Exercises 86

10 Anonymous Networks 89

10.1 Impossibility of Election in Anonymous Rings 89

10.2 Probabilistic Algorithms 90

10.3 Itai-Rodeh Election Algorithm for Rings 91

10.4 Echo Algorithm with Extinction for Anonymous Networks 92

10.5 Computing the Size of an Anonymous Ring Is Impossible 94

10.6 Itai-Rodeh Ring Size Algorithm 95

10.7 Election in IEEE 1394 97

10.8 Exercises 98

11 Synchronous Networks 101

11.1 Awerbuch's Synchronizer 101

11.2 Bounded Delay Networks with Local Clocks 104

11.3 Election in Anonymous Rings with Bounded Expected Delay 105

11.4 Exercises 108

12 Consensus with Crash Failures 109

12.1 Impossibility of 1-Crash Consensus 110

12.2 Bracha-Toueg Crash Consensus Algorithm 111

12.3 Failure Detectors 113

12.4 Consensus with a Weakly Accurate Failure Detector 114

12.5 Chandra-Toueg Algorithm 114

12.6 Consensus for Shared Memory 117

12.7 Exercises 118

13 Consensus with Byzantine Failures 121

13.1 Bracha-Toueg Byzantine Consensus Algorithm 121

13.2 Mahaney-Schneider Synchronizer 125

13.3 Lamport-Shostak-Pease Broadcast Algorithm 127

13.4 Lamport-Shostak-Pease Authentication Algorithm 130

13.5 Exercises 132

14 Mutual Exclusion 135

14.1 Ricart-Agrawala Algorithm 136

14.2 Raymond's Algorithm 137

14.3 Agrawal-El Abbadi Algorithm 140

14.4 Peterson's Algorithm 142

14.5 Bakery Algorithm 145

14.6 Fischer's Algorithm 147

14.7 Test-and-Test-and-Set Lock 148

14.8 Queue Locks 149

14.9 Exercises 153

15 Barriers 157

15.1 Sense-Reversing Barrier 157

15.2 Combining Tree Barrier 158

15.3 Tournament Barrier 161

15.4 Dissemination Barrier 163

15.5 Exercises 165

16 Distributed Transactions 167

16.1 Serialization 168

16.2 Two- and Three-Phase Commit Protocols 171

16.3 Transactional Memory 173

16.4 Exercises 176

17 Self-Stabilization 177

17.1 Dijkstra's Token Ring for Mutual Exclusion 177

17.2 Arora-Gouda Spanning Tree Algorithm 180

17.3 Afek-Kutten-Yung Spanning Tree Algorithm 183

17.4 Exercises 185

18 Security 187

18.1 Basic Techniques 187

18.2 Blockchains 191

18.3 Quantum Cryptography 194

18.4 Exercises 198

19 Online Scheduling 201

19.1 Jobs 201

19.2 Schedulers 202

19.3 Resource Access Control 207

19.4 Exercises 209

A Appendix: Pseudocode Descriptions 211

A.1 Chandy-Lamport Snapshot Algorithm 212

A.2 Lai-Yang Snapshot Algorithm 212

A.3 Cidon's Depth-First Search Algorithm 214

A.4 Tree Algorithm 215

A.5 Echo Algorithm 215

A.6 Shavit-Francez Termination Detection Algorithm 216

A.7 Rana's Termination Detection Algorithm 217

A.8 Safra's Termination Detection Algorithm 218

A.9 Weight-Throwing Termination Detection Algorithm 219

A.10 Chandy-Misra Routing Algorithm 220

A.11 Merlin-Segall Routing Algorithm 221

A.12 Toueg's Routing Algorithm 222

A.13 Frederickson's Breadth-First Search Algorithm 223

A.14 Dolev-Klawe-Rodeh Election Algorithm 225

A.15 Gallager-Humblet-Spira Minimum Spanning Tree Algorithm 226

A.16 IEEE 1394 Election Algorithm 229

A.17 Awerbuch's Synchronizer 230

A.18 Ricart-Agrawala Mutual Exclusion Algorithm 231

A.19 Raymond's Mutual Exclusion Algorithm 232

A.20 Agrawal-El Abbadi Mutual Exclusion Algorithm 234

A.21 MCS Queue Lock 235

A.22 CLH Queue Lock with Timeouts 236

A.23 Afek-Kutten-Yung Spanning Tree Algorithm 237

References 241

Index 247

What People are Saying About This

Jan van Leeuwen

I am always fascinated by distributed processes. How can we design algorithms or protocols for them that work? Fokkink gives a unique introduction to the many original concepts and methods in distributed computing that we know today. A truly insightful book.

From the Publisher

I am always fascinated by distributed processes. How can we design algorithms or protocols for them that work? Fokkink gives a unique introduction to the many original concepts and methods in distributed computing that we know today. A truly insightful book.

Jan van Leeuwen , Utrecht University

An original and thought-provoking new approach to teaching distributed algorithms.

Maurice Herlihy , Brown University

Endorsement

An original and thought-provoking new approach to teaching distributed algorithms.

Maurice Herlihy, Brown University

Maurice Herlihy

An original and thought-provoking new approach to teaching distributed algorithms.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews