Distributed Computing : Principles, Algorithms, and Systems

Designing distributed computing systems is a complex process requiring a solid understanding of the design problems and the theoretical and practical aspects of their solutions. This comprehensive textbook covers the fundamental principles and models underlying the theory, algorithms and systems aspects of distributed computing. Broad and detailed coverage of the theory is balanced with practical systems-related issues such as mutual exclusion, deadlock detection, authentication, and failure recovery. Algorithms are carefully selected, lucidly presented, and described without complex proofs. Simple explanations and illustrations are used to elucidate the algorithms. Important emerging topics such as peer-to-peer networks and network security are also considered. With vital algorithms, numerous illustrations, examples and homework problems, this textbook is suitable for advanced undergraduate and graduate students of electrical and computer engineering and computer science. Practitioners in data networking and sensor networks will also find this a valuable resource. Additional resources are available online at (http://www.cambridge.org/9780521876346) www.cambridge.org/9780521876346 . Cover 1 Half-title 3 Title 5 Copyright 6 Dedication 7 Contents 9 Preface 17 Background 17 Description, approach, and features 18 Readership 18 Acknowledgements 19 Access to resources 19 CHAPTER 1 Introduction 21 1.1 Definition 21 1.2 Relation to computer system components 22 1.3 Motivation 23 1.4 Relation to parallel multiprocessor/multicomputer systems 25 1.4.1 Characteristics of parallel systems 25 1.4.2 Flynn’s taxonomy 30 1.4.3 Coupling, parallelism, concurrency, and granularity 31 Coupling 31 Parallelism or speedup of a program on a specific system 32 Parallelism within a parallel/distributed program 32 Concurrency of a program 32 Granularity of a program 32 1.5 Message-passing systems versus shared memory systems 33 1.5.1 Emulating message-passing on a shared memory system (MP → SM) 34 1.5.2 Emulating shared memory on a message-passing system ( SM→ MP) 34 1.6 Primitives for distributed communication 34 1.6.1 Blocking/non-blocking, synchronous/asynchronous primitives 34 1.6.2 Processor synchrony 38 1.6.3 Libraries and standards 39 1.7 Synchronous versus asynchronous executions 39 1.7.1 Emulating an asynchronous system by a synchronous system (A→ S) 41 1.7.2 Emulating a synchronous system by an asynchronous system (S→ A) 41 1.7.3 Emulations 41 1.8 Design issues and challenges 42 1.8.1 Distributed systems challenges from a system perspective 42 1.8.2 Algorithmic challenges in distributed computing 44 Designing useful execution models and frameworks 44 Dynamic distributed graph algorithms and distributed routing algorithms 44 Time and global state in a distributed system 44 Synchronization/coordination mechanisms 45 Group communication, multicast, and ordered message delivery 46 Monitoring distributed events and predicates 46 Distributed program design and verification tools 46 Debugging distributed programs 46 Data replication, consistency models, and caching 46 World Wide Web design – caching, searching, scheduling 47 Distributed shared memory abstraction 47 Reliable and fault-tolerant distributed systems 48 Load balancing 49 Real-time scheduling 50 Performance 50 1.8.3 Applications of distributed computing and newer challenges 50 Mobile systems 50 Sensor networks 51 Ubiquitous or pervasive computing 51 Peer-to-peer computing 52 Publish-subscribe, content distribution, and multimedia 52 Distributed agents 52 Distributed data mining 53 Grid computing 53 Security in distributed systems 53 1.9 Selection and coverage of topics 53 1.10 Chapter summary 54 1.11 Exercises 55 1.12 Notes on references 56 References 57 CHAPTER 2 A model of distributed computations 59 2.1 A distributed program 59 2.2 A model of distributed executions 60 Causal precedence relation 61 Logical vs. physical concurrency 62 2.3 Models of communication networks 62 2.4 Global state of a distributed system 63 2.4.1 Global state 64 2.5 Cuts of a distributed computation 65 2.6 Past and future cones of an event 66 2.7 Models of process communications 67 2.8 Chapter summary 68 2.9 Exercises 68 2.10 Notes on references 68 References 69 CHAPTER 3 Logical time 70 3.1 Introduction 70 3.2 A framework for a system of logical clocks 72 3.2.1 Definition 72 3.2.2 Implementing logical clocks 72 3.3 Scalar time 73 3.3.1 Definition 73 3.3.2 Basic properties 74 Consistency property 74 Total Ordering 74 Event counting 74 No strong consistency 74 3.4 Vector time 75 3.4.1 definition 75 3.4.2 Basic properties 76 Isomorphism 76 Strong consistency 77 Event counting 77 Applications 77 A brief historical perspective of vector clocks 77 3.4.3 On the size of vector clocks 77 3.5 Efficient implementations of vector clocks 79 3.5.1 Singhal–Kshemkalyani’s differential technique 80 3.5.2 Fowler–Zwaenepoel’s direct-dependency technique 82 3.6 Jard–Jourdan’s adaptive technique 85 3.7 Matrix time 88 3.7.1 Definition 88 3.7.2 Basic properties 89 3.8 Virtual time 89 3.8.1 Virtual time definition 90 Characteristics of virtual time 91 3.8.2 Comparison with Lamport’s logical clocks 91 3.8.3 Time warp mechanism 92 3.8.4 The local control mechanism 93 Antimessages and the rollback mechanism 93 3.8.5 Global control mechanism 95 Global virtual time 95 Applications of GVT 96 Memory management and flow control 96 Normal termination detection 97 Error handling 97 Input and output 97 Snapshots and crash recovery 97 3.9 Physical clock synchronization: NTP 98 3.9.1 Motivation 98 3.9.2 Definitions and terminology 99 3.9.3 Clock inaccuracies 100 Offset delay estimation method 100 Clock offset and delay estimation 100 3.10 Chapter summary 101 3.11 Exercises 104 3.12 Notes on references 104 References 104 CHAPTER 4 Global state and snapshot recording algorithms 107 4.1 Introduction 107 4.2 System model and definitions 110 4.2.1 System model 110 4.2.2 A consistent global state 111 4.2.3 Interpretation in terms of cuts 111 4.2.4 Issues in recording a global state 112 4.3 Snapshot algorithms for FIFO channels 113 4.3.1 Chandy–Lamport algorithm 113 The algorithm 114 Correctness 115 Complexity 115 4.3.2 Properties of the recorded global state 115 4.4 Variations of the Chandy–Lamport algorithm 117 4.4.1 Spezialetti–Kearns algorithm 117 Efficient snapshot recording 118 Efficient dissemination of the recorded snapshot 118 4.4.2 Venkatesan’s incremental snapshot algorithm 119 4.4.3 Helary’s wave synchronization method 120 4.5 Snapshot algorithms for non-FIFO channels 121 4.5.1 Lai–Yang algorithm 122 4.5.2 Li et al.’s algorithm 123 4.5.3 Mattern’s algorithm 125 4.6 Snapshots in a causal delivery system 126 4.6.1 Process state recording 127 4.6.2 Channel state recording in Acharya–Badrinath algorithm 127 4.6.3 Channel state recording in Alagar–Venkatesan algorithm 128 4.7 Monitoring global state 129 4.8 Necessary and sufficient conditions for consistent global snapshots 130 4.8.1 Zigzag paths and consistent global snapshots 132 A zigzag path 132 Difference between a zigzag path and a causal path 132 Consistent global snapshots 133 4.9 Finding consistent global snapshots in a distributed computation 134 4.9.1 Finding consistent global snapshots 135 Extending to a consistent snapshot 135 First observation 135 Second observation 136 Third observation 137 4.9.2 Manivannan–Netzer–Singhal algorithm for enumerating consistent snapshots 138 4.9.3 Finding Z-paths in a distributed computation 139 Construction of an R-graph 139 4.10 Chapter summary 141 4.11 Exercises 142 4.12 Notes on references 142 References 143 CHAPTER 5 Terminology and basic algorithms 146 5.1 Topology abstraction and overlays 146 5.2 Classifications and basic concepts 148 5.2.1 Application executions and control algorithm executions 148 5.2.2 Centralized and distributed algorithms 149 5.2.3 Symmetric and asymmetric algorithms 149 5.2.4 Anonymous algorithms 150 5.2.5 Uniform algorithms 150 5.2.6 Adaptive algorithms 150 5.2.7 Deterministic versus non-deterministic executions 151 5.2.8 Execution inhibition 151 5.2.9 Synchronous and asynchronous systems 152 5.2.10 Online versus offline algorithms 153 5.2.11 Failure models 153 Process failure models [26] 153 Communication failure models 154 5.2.12 Wait-free algorithms 154 5.2.13 Communication channels 155 5.3 Complexity measures and metrics 155 5.4 Program structure 157 5.5 Elementary graph algorithms 158 5.5.1 Synchronous single-initiator spanning tree algorithm using flooding 158 5.5.2 Asynchronous single-initiator spanning tree algorithm using flooding 160 5.5.3 Asynchronous concurrent-initiator spanning tree algorithm using flooding 163 Design 1 163 Design 2 165 5.5.4 Asynchronous concurrent-initiator depth first search spanning tree algorithm 166 5.5.5 Broadcast and convergecast on a tree 168 5.5.6 Single source shortest path algorithm: synchronous Bellman–Ford 169 5.5.7 Distance vector routing 170 5.5.8 Single source shortest path algorithm: asynchronous Bellman–Ford 171 5.5.9 All sources shortest paths: asynchronous distributed Floyd–Warshall 171 5.5.10 Asynchronous and synchronous constrained flooding (w/o a spanning tree) 175 Asynchronous algorithm (Algorithm 5.9) 175 Synchronous algorithm (Algorithm 5.10) 176 5.5.11 Minimum-weight spanning tree (MST) algorithm in a synchronous system 177 5.5.12 Minimum-weight spanning tree (MST) in an asynchronous system 182 5.6 Synchronizers 183 General observations on synchronous and asynchronous algorithms 183 A simple synchronizer 184 The synchronizer 185 The synchronizer 186 The synchronizer 186 5.7 Maximal independent set (MIS) 189 5.8 Connected dominating set 191 5.9 Compact routing tables 192 5.10 Leader election 194 5.11 Challenges in designing distributed graph algorithms 195 5.12 Object replication problems 196 5.12.1 Problem definition 196 5.12.2 Algorithm outline 197 5.12.3 Reads and writes 197 Read 197 Write 198 Implementation 198 5.12.4 Converging to an replication scheme 198 5.13 Chapter summary 202 5.14 Exercises 203 5.15 Notes on references 205 References 206 CHAPTER 6 Message ordering and group communication 209 Notation 209 6.1 Message ordering paradigms 210 6.1.1 Asynchronous executions 210 6.1.2 FIFO executions 211 6.1.3 Causally ordered (CO) executions 211 6.1.4 Synchronous execution (SYNC) 214 6.2 Asynchronous execution with synchronous communication 215 6.2.1 Executions realizable with synchronous communication (RSC) 216 6.2.2 Hierarchy of ordering paradigms 219 6.2.3 Simulations 219 Asynchronous programs on synchronous systems 219 Synchronous programs on asynchronous systems 220 6.3 Synchronous program order on an asynchronous system 220 Non-determinism 221 6.3.1 Rendezvous 221 6.3.2 Algorithm for binary rendezvous 222 6.4 Group communication 225 6.5 Causal order (CO) 226 6.5.1 The Raynal–Schiper–Toueg algorithm [22] 227 6.5 Causal order (CO) 228 Multicasts M51 and M42 233 Multicast M43 233 Learning implicit information at P2 and P3 234 Processing at P6 234 Processing at P1 235 6.6 Total order 235 6.6.1 Centralized algorithm for total order 236 6.6.2 Three-phase distributed algorithm 236 Sender 236 Receivers 238 Complexity 238 6.7 A nomenclature for multicast 240 6.8 Propagation trees for multicast 241 6.9 Classification of application-level multicast algorithms 245 Communication history-based algorithms 246 Privilege-based algorithms 246 Moving sequencer algorithms 247 Fixed sequencer algorithms 247 Destination agreement algorithms 247 6.10 Semantics of fault-tolerant group communication 248 6.11 Distributed multicast algorithms at the network layer 250 6.11.1 Reverse path forwarding (RPF) for constrained flooding 250 6.11.2 Steiner trees 251 Steiner tree problem 251 6.11.3 Multicast cost functions 252 6.11.4 Delay-bounded Steiner trees 253 Delay-bounded minimal Steiner tree problem 253 6.11.5 Core-based trees 255 6.12 Chapter summary 256 6.13 Exercises 256 6.14 Notes on references 258 References 259 CHAPTER 7 Termination detection 261 7.1 Introduction 261 7.2 System model of a distributed computation 262 Definition of termination detection 263 7.3 Termination detection using distributed snapshots 263 7.3.1 Informal description 263 7.3.2 Formal description 263 7.3.3 Discussion 264 7.4 Termination detection by weight throwing 265 Basic idea 265 Notation 266 7.4.1 Formal description 266 7.4.2 Correctness of the algorithm 266 7.5 A spanning-tree-based termination detection algorithm 267 7.5.1 Definitions 268 7.5.2 A simple algorithm 268 A problem with the algorithm 268 7.5.3 The correct algorithm 269 The basic idea 269 The algorithm description 270 7.5.4 An example 271 7.5.5 Performance 273 7.6 Message-optimal termination detection 273 7.6.1 The main idea 274 7.6.2 Formal description of the algorithm 275 7.6.3 Performance 277 7.7 Termination detection in a very general distributed computing model 277 7.7.1 Model definition and assumptions 278 AND, OR, and AND-OR models 278 The k out of n model 278 Predicate fulfilled 278 7.7.2 Notation 278 7.7.3 Termination definitions 279 7.7.4 A static termination detection algorithm 279 Informal description 279 Formal description 280 Performance 281 7.7.5 A dynamic termination detection algorithm 281 Informal description 281 Formal description 282 Performance 283 7.8 Termination detection in the atomic computation model 283 Assumptions 283 7.8.1 The atomic model of execution 284 7.8.2 A naive counting method 284 7.8.3 The four counter method 285 7.8.4 The sceptic algorithm 286 7.8.5 The time algorithm 287 Formal description 287 7.8.6 Vector counters method 288 Performance 290 7.8.7 A channel counting method 290 Formal description 290 Performance 292 7.9 Termination detection in a faulty distributed system 292 Assumptions 293 7.9.1 Flow detecting scheme 293 The concept of flow invariant 293 7.9.2 Taking snapshots 294 7.9.3 Description of the algorithm 295 Data structures 295 7.9.2 Taking snapshots 296 7.9.4 Performance analysis 298 7.10 Chapter summary 299 7.11 Exercises 299 7.12 Notes on references 300 References 300 CHAPTER 8 Reasoning with knowledge 302 8.1 The muddy children puzzle 302 8.2 Logic of knowledge 303 8.2.1 Knowledge operators 303 8.2.2 The muddy children puzzle again 304 8.2.3 Kripke structures 305 8.2.4 Muddy children puzzle using Kripke structures 307 Scenario A 307 Scenario B 308 8.2.5 Properties of knowledge 308 8.3 Knowledge in synchronous systems 309 8.4 Knowledge in asynchronous systems 310 8.4.1 Logic and definitions 310 8.4.2 Agreement in asynchronous systems 311 8.4.3 Variants of common knowledge 312 Epsilon common knowledge 312 Eventual common knowledge 312 Timestamped common knowledge 313 Concurrent common knowledge 313 8.4.4 Concurrent common knowledge 313 Snapshot-based algorithm 315 Complexity 315 Three-phase send-inhibitory algorithm 315 The three-phase send-inhibitory tree algorithm 316 Complexity 316 Inhibitory ring algorithm 316 Complexity 316 8.5 Knowledge transfer 318 8.6 Knowledge and clocks 320 8.7 Chapter summary 321 8.8 Exercises 322 8.9 Notes on references 323 References 323 CHAPTER 9 Distributed mutual exclusion algorithms 325 9.1 Introduction 325 9.2 Preliminaries 326 9.2.1 System model 326 9.2.2 Requirements of mutual exclusion algorithms 327 9.2.3 Performance metrics 327 Low and high load performance 328 Best and worst case performance 328 9.3 Lamport’s algorithm 329 Correctness 330 Performance 332 An optimization 332 9.4 Ricart–Agrawala algorithm 332 Correctness 333 Performance 335 9.5 Singhal’s dynamic information-structure algorithm 335 System model 336 Data structures 336 Initialization 337 9.5.1 Description of the algorithm 337 An explanation of the algorithm 339 9.5.2 Correctness 339 Achieving mutual exclusion 339 Freedom from deadlocks 340 9.5.3 Performance analysis 340 Low load condition 340 Heavy load condition 341 9.5.4 Adaptivity in heterogeneous traffic patterns 341 9.6 Lodha and Kshemkalyani’s fair mutual exclusion algorithm 341 9.6.1 System model 342 9.6.2 Description of the algorithm 342 9.6.3 Safety, fairness and liveness 345 9.6.4 Message complexity 345 9.7 Quorum-based mutual exclusion algorithms 347 9.8 Maekawa’s algorithm 348 Correctness 349 Performance 350 9.8.1 Problem of deadlocks 350 Handling deadlocks 350 9.9 Agarwal–El Abbadi quorum-based algorithm 351 9.9.1 Constructing a tree-structured quorum 351 9.9.2 Analysis of the algorithm for constructing tree-structured quorums 353 9.9.3 Validation 353 9.9.4 Examples of tree-structured quorums 353 9.9.5 The algorithm for distributed mutual exclusion 355 9.9.6 Correctness proof 356 9.10 Token-based algorithms 356 9.11 Suzuki–Kasami’s broadcast algorithm 356 Correctness 358 Performance 358 9.12 Raymond’s tree-based algorithm 359 9.12.1 The HOLDER variables 360 9.12.2 The operation of the algorithm 361 Data structures 361 9.12.3 Description of the algorithm 362 ASSIGN_PRIVILEGE 362 MAKE_REQUEST 362 Events 363 Message overtaking 363 9.12.4 Correctness 364 Mutual exclusion is guaranteed 364 Deadlock is impossible 364 Starvation is impossible 365 9.12.5 Cost and performance analysis 366 9.12.6 Algorithm initialization 367 9.12.7 Node failures and recovery 367 9.13 Chapter summary 368 9.14 Exercises 368 9.15 Notes on references 369 References 370 CHAPTER 10 Deadlock detection in distributed systems 372 10.1 Introduction 372 10.2 System model 372 10.2.1 Wait-for graph (WFG) 373 10.3 Preliminaries 373 10.3.1 Deadlock handling strategies 373 10.3.2 Issues in deadlock detection 374 Detection of deadlocks 374 Correctness criteria 375 Resolution of a detected deadlock 375 10.4 Models of deadlocks 375 10.4.1 The single-resource model 376 10.4.2 The AND model 376 10.4.3 The OR model 376 10.4.4 The AND-OR model 377 10.4.5 The p model 377 10.4.6 Unrestricted model 378 10.5 Knapp’s classification of distributed deadlock detection algorithms 378 10.5.1 Path-pushing algorithms 378 10.5.2 Edge-chasing algorithms 379 10.5.3 Diffusing computation-based algorithms 379 10.5.4 Global state detection-based algorithms 379 10.6 Mitchell and Merritt’s algorithm for the single-resource model 380 Message complexity 382 10.7 Chandy–Misra–Haas algorithm for the AND model 382 Data structures 383 The algorithm 383 Performance analysis 384 10.8 Chandy–Misra–Haas algorithm for the OR model 384 Basic idea 384 The algorithm 385 Performance analysis 385 10.9 Kshemkalyani–Singhal algorithm for the P-out-of- model 385 System model 387 10.9.1 Informal description of the algorithm 387 The problem of termination detection 388 10.9.2 The algorithm 389 Correctness 394 Complexity analysis 394 10.10 Chapter summary 394 10.11 Exercises 395 10.12 Notes on references 395 References 396 CHAPTER 11 Global predicate detection 399 11.1 Stable and unstable predicates 399 11.1.1 Stable predicates 400 Deadlock [13, 17] 400 Termination [20] 400 11.1.2 Unstable predicates 402 11.2 Modalities on predicates 402 11.2.1 Complexity of predicate detection 404 11.3 Centralized algorithm for relational predicates 404 11.4 Conjunctive predicates 408 11.4.1 Interval-based centralized algorithm for conjunctive predicates 409 Termination 412 Complexity 412 11.4.2 Global state-based centralized algorithm for , where is conjunctive 412 11.5 Distributed algorithms for conjunctive predicates 415 11.5.1 Distributed state-based token algorithm for, Possibly (Phi) where Phi is conjunctive 415 11.5.2 Distributed interval-based token algorithm for Definitely (Phi), where is conjunctive 417 11.5.3 Distributed interval-based piggybacking algorithm for Possibly (Phi), where Phi is conjuctive 421 11.6 Further classification of predicates 424 11.7 Chapter summary 425 11.8 Exercises 426 11.9 Notes on references 427 References 428 CHAPTER 12 Distributed shared memory 430 12.1 Abstraction and advantages 430 12.2 Memory consistency models 433 12.2.1 Strict consistency/atomic consistency/linearizability 434 Implementations 435 12.2.2 Sequential consistency 437 Implementations 438 Local-read algorithm 439 Local-write algorithm 439 12.2.3 Causal consistency 440 Implementation 442 12.2.4 PRAM (pipelined RAM) or processor consistency 442 Implementations 443 12.2.5 Slow memory 443 Implementations 444 12.2.6 Hierarchy of consistency models 444 12.2.7 Other models based on synchronization instructions 444 Weak consistency [11] 445 Release consistency [12] 445 Entry consistency [9] 446 12.3 Shared memory mutual exclusion 447 12.3.1 Lamport’s bakery algorithm 447 12.3.2 Lamport’s WRWR mechanism and fast mutual exclusion 449 12.3.3 Hardware support for mutual exclusion 452 12.4 Wait-freedom 454 12.5 Register hierarchy and wait-free simulations 454 12.5.1 Construction 1: SRSW safe to MRSW safe 457 12.5.2 Construction 2: SRSW regular to MRSW regular 458 12.5.3 Construction 3: boolean MRSW safe to integer-valued MRSW safe 458 12.5.4 Construction 4: boolean MRSW safe to boolean MRSW regular 459 12.5.5 Construction 5: boolean MRSW regular to integer-valued MRSW regular 460 12.5.6 Construction 6: boolean MRSW regular to integer-valued MRSW atomic 462 12.5.7 Construction 7: integer MRSW atomic to integer MRMW atomic 464 12.5.8 Construction 8: integer SRSW atomic to integer MRSW atomic 465 Achieving linearizability 466 12.6 Wait-free atomic snapshots of shared objects 467 Complexity 471 12.7 Chapter summary 471 12.8 Exercises 472 12.9 Notes on references 473 References 474 CHAPTER 13 Checkpointing and rollback recovery 476 13.1 Introduction 476 13.2 Background and definitions 477 13.2.1 System model 477 13.2.2 A local checkpoint 478 13.2.3 Consistent system states 478 13.2.4 Interactions with the outside world 479 13.2.5 Different types of messages 480 In-transit messages 481 Lost messages 481 Delayed messages 481 Orphan messages 481 Duplicate messages 481 13.3 Issues in failure recovery 482 13.4 Checkpoint-based recovery 484 13.4.1 Uncoordinated checkpointing 484 13.4.2 Coordinated checkpointing 485 Blocking coordinated checkpointing 486 Non-blocking checkpoint coordination 486 13.4.3 Impossibility of min-process non-blocking checkpointing 487 13.4.4 Communication-induced checkpointing 488 Model-based checkpointing 489 Index-based checkpointing 490 13.5 Log-based rollback recovery 490 13.5.1 Deterministic and non-deterministic events 490 The no-orphans consistency condition 491 13.5.2 Pessimistic logging 492 13.5.3 Optimistic logging 493 13.5.4 Causal logging 494 13.6 Koo–Toueg coordinated checkpointing algorithm 496 13.6.1 The checkpointing algorithm 496 First phase 496 Second phase 496 Correctness 497 An optimization 497 13.6.2 The rollback recovery algorithm 497 First phase 498 Second phase 498 Correctness 498 An optimization 498 13.7 Juang–Venkatesan algorithm for asynchronous checkpointing and recovery 498 13.7.1 System model and assumptions 499 13.7.2 Asynchronous checkpointing 500 13.7.3 The recovery algorithm 500 Notation and data structure 500 Basic idea 500 Description of the algorithm 501 13.8 Manivannan–Singhal quasi-synchronous checkpointing algorithm 503 13.8.1 Checkpointing algorithm 504 Properties 504 13.8.2 Recovery algorithm 506 An explanation 506 13.8.3 Comprehensive message handling 509 Handling the replay of messages 509 Handling of received messages 510 Case 1: is a delayed message 511 Case 2: was sent in the current incarnation 511 Case 3: Message was sent in a future incarnation 511 Features 511 13.9 Peterson–Kearns algorithm based on vector time 512 13.9.1 System model 512 Notation 512 13.9.2 Informal description of the algorithm 513 Handling in-transit orphan messages 514 13.9.3 Formal description of the rollback protocol 515 The rollback protocol 515 13.9.4 Correctness proof 517 13.10 Helary–Mostefaoui–Netzer–Raynal communication-induced protocol 519 13.10.1 Design principles 520 To checkpoint or not to checkpoint? 520 Reducing the number of forced checkpoints 521 13.10.2 The checkpointing protocol 523 13.11 Chapter summary 525 13.12 Exercises 526 13.13 Notes on references 526 References 527 CHAPTER 14 Consensus and agreement algorithms 530 14.1 Problem definition 530 14.1.1 The Byzantine agreement and other problems 532 The Byzantine agreement problem 532 The consensus problem 533 The interactive consistency problem 533 14.1.2 Equivalence of the problems and notation 534 14.2 Overview of results 534 14.3 Agreement in a failure-free system (synchronous or asynchronous) 535 14.4 Agreement in (message-passing) synchronous systems with failures 536 14.4.1 Consensus algorithm for crash failures (synchronous system) 536 14.4.2 Consensus algorithms for Byzantine failures (synchronous system) 537 14.4.3 Upper bound on Byzantine processes 537 Byzantine agreement tree algorithm: exponential (synchronous system) 539 Phase-king algorithm for consensus: polynomial (synchronous system) 546 14.5 Agreement in asynchronous message-passing systems with failures 549 14.5.1 Impossibility result for the consensus problem 549 14.5.2 Terminating reliable broadcast 551 14.5.3 Distributed transaction commit 552 14.5.4 k-set consensus 552 14.5.5 Approximate agreement 553 Algorithm outline 553 Notation 555 Convergence rate of approximation 556 Correctness 557 Complexity 558 14.5.6 Renaming problem 558 Problem definition 558 Algorithm 559 Correctness 562 14.5.7 Reliable broadcast 564 14.6 Wait-free shared memory consensus in asynchronous systems 564 14.6.1 Impossibility result 564 14.6.2 Consensus numbers and consensus hierarchy [14] 567 FIFO queue 569 Compare&Swap 570 Read–modify–write abstraction 571 14.6.3 Universality of consensus objects [14] 572 A non-blocking universal algorithm 573 A wait-free universal algorithm 576 14.6.4 Shared memory k-set consensus 576 14.6.5 Shared memory renaming 577 14.6.6 Shared memory renaming using splitters 580 14.7 Chapter summary 582 14.8 Exercises 583 14.9 Notes on references 584 References 585 CHAPTER 15 Failure detectors 587 15.1 Introduction 587 15.2 Unreliable failure detectors 588 15.2.1 The system model 588 Failure patterns and environments 589 15.2.2 Failure detectors 589 15.2.3 Completeness and accuracy properties 590 Completeness 590 Accuracy 591 Eventual accuracy 591 15.2.4 Types of failure detectors 592 15.2.5 Reducibility of failure detectors 592 15.2.6 Reducing weak failure detector W to a strong failure detector S 593 A correctness argument 594 15.2.7 Reducing an eventually weak failure detector . to an eventually strong failure detector... 595 An explanation of the algorithm 596 Correctness argument 597 15.3 The consensus problem 597 15.3.1 Solutions to the consensus problem 598 15.3.2 A solution using strong failure detector S 598 An explanation of the algorithm 599 15.3.3 A solution using eventually strong failure detector... 600 An explanation of the algorithm 602 15.4 Atomic broadcast 603 15.5 A solution to atomic broadcast 604 An explanation of the algorithm 604 15.6 The weakest failure detectors to solve fundamental agreement problems 605 Uniform consensus 606 Terminating reliable broadcast 606 15.6.1 Realistic failure detectors 606 15.6.2 The weakest failure detector for consensus 608 15.6.3 The weakest failure detector for terminating reliable broadcast 609 15.7 An implementation of a failure detector 609 Explanation of the algorithm 611 Correctness of the algorithm 611 15.8 An adaptive failure detection protocol 611 15.8.1 Lazy failure detection protocol (FDL) 612 Assumptions 612 Primitives provided 613 The protocol FDL 613 Properties of FDL 615 15.9 Exercises 616 15.10 Notes on references 616 References 616 CHAPTER 16 Authentication in distributed systems 618 16.1 Introduction 618 16.2 Background and definitions 619 16.2.1 Basis of authentication 619 16.2.2 Types of principals 620 16.2.3 A simple classification of authentication protocols 620 16.2.4 Notation 620 16.2.5 Design principles for cryptographic protocols 621 16.3 Protocols based on symmetric cryptosystems 622 16.3.1 Basic protocol 623 Weaknesses 623 16.3.2 Modified protocol with nonce 624 Weaknesses 624 16.3.3 Wide-mouth frog protocol 625 16.3.4 A protocol based on an authentication server 625 16.3.5 One-time password scheme 626 Protocol description 627 Weaknesses 629 16.3.6 Otway–Rees protocol 629 Weaknesses 630 16.3.7 Kerberos authentication service 631 Initial registration 631 The authentication protocol 631 Weaknesses 634 16.4 Protocols based on asymmetric cryptosystems 635 16.4.1 The basic protocol 635 16.4.2 A modified protocol with a certification authority 636 16.4.3 Needham and Schroeder protocol 637 Weaknesses 638 An impersonation attack on the protocol 638 16.4.4 SSL protocol 639 SSL record protocol 640 SSL handshake protocol 640 How SSL provides authentication 641 16.5 Password-based authentication 642 Preventing off-line dictionary attacks 643 16.5.1 Encrypted key exchange (EKE) protocol 643 16.5.2 Secure remote password (SRP) protocol 644 16.6 Authentication protocol failures 645 16.7 Chapter summary 646 16.8 Exercises 647 16.9 Notes on references 647 References 648 CHAPTER 17 Self-stabilization 651 17.1 Introduction 651 17.2 System model 652 17.3 Definition of self-stabilization 654 17.3.1 Randomized and probabilistic self-stabilization 655 17.4 Issues in the design of self-stabilization algorithms 656 Dijkstra’s self-stabilizing token ring system 656 17.4.1 The number of states in each of the individual units 657 First solution 657 Second solution 658 Special networks 661 Ghosh’s solution 661 17.4.2 Uniform vs. non-uniform networks 662 17.4.3 Central and distributed demons 663 17.4.4 Reducing the number of states in a token ring 664 17.4.5 Shared memory models 665 17.4.6 Mutual exclusion 665 17.4.7 Costs of self-stabilization 666 17.5 Methodologies for designing self-stabilizing systems 667 17.5.1 Layering and modularization 667 Common clock primitives 668 Topology-based primitives 668 17.6 Communication protocols 669 17.7 Self-stabilizing distributed spanning trees 670 17.8 Self-stabilizing algorithms for spanning-tree construction 672 17.8.1 Dolev, Israeli, and Moran algorithm 672 17.8.2 Afek, Kutten, and Yung algorithm for spanning-tree construction 675 17.8.3 Arora and Gouda algorithm for spanning-tree construction 675 17.8.4 Huang et al. algorithms for spanning-tree construction 676 17.8.5 Afek and Bremler algorithm for spanning-tree construction 676 17.9 An anonymous self-stabilizing algorithm for 1-maximal independent set in trees 677 Description of algorithm 678 17.10 A probabilistic self-stabilizing leader election algorithm 680 17.11 The role of compilers in self-stabilization 682 17.11.1 Compilers for sequential programs 682 17.11.2 Compilers for asynchronous message passing systems 683 17.11.3 Compilers for asynchronous shared memory systems 684 17.12 Self-stabilization as a solution to fault tolerance 685 Fault tolerance 685 17.13 Factors preventing self-stabilization 687 Symmetry 687 Termination 688 Isolation 688 Look-alike configurations 688 17.14 Limitations of self-stabilization 688 Need for an exceptional machine 689 Convergence–response tradeoffs 689 Pseudo-stabilization 689 Verification of self-stabilizing systems 690 17.15 Chapter summary 690 17.16 Exercises 690 17.17 Notes on references 691 References 691 CHAPTER 18 Peer-to-peer comp Cover......Page 1 Half-title......Page 3 Title......Page 5 Copyright......Page 6 Dedication......Page 7 Contents......Page 9 Background......Page 17 Readership......Page 18 Access to resources......Page 19 1.1 Definition......Page 21 1.2 Relation to computer system components......Page 22 1.3 Motivation......Page 23 1.4.1 Characteristics of parallel systems......Page 25 1.4.2 Flynn’s taxonomy......Page 30 Coupling......Page 31 Granularity of a program......Page 32 1.5 Message-passing systems versus shared memory systems......Page 33 1.6.1 Blocking/non-blocking, synchronous/asynchronous primitives......Page 34 1.6.2 Processor synchrony......Page 38 1.7 Synchronous versus asynchronous executions......Page 39 1.7.3 Emulations......Page 41 1.8.1 Distributed systems challenges from a system perspective......Page 42 Time and global state in a distributed system......Page 44 Synchronization/coordination mechanisms......Page 45 Data replication, consistency models, and caching......Page 46 Distributed shared memory abstraction......Page 47 Reliable and fault-tolerant distributed systems......Page 48 Load balancing......Page 49 Mobile systems......Page 50 Ubiquitous or pervasive computing......Page 51 Distributed agents......Page 52 1.9 Selection and coverage of topics......Page 53 1.10 Chapter summary......Page 54 1.11 Exercises......Page 55 1.12 Notes on references......Page 56 References......Page 57 2.1 A distributed program......Page 59 2.2 A model of distributed executions......Page 60 Causal precedence relation......Page 61 2.3 Models of communication networks......Page 62 2.4 Global state of a distributed system......Page 63 2.4.1 Global state......Page 64 2.5 Cuts of a distributed computation......Page 65 2.6 Past and future cones of an event......Page 66 2.7 Models of process communications......Page 67 2.10 Notes on references......Page 68 References......Page 69 3.1 Introduction......Page 70 3.2.2 Implementing logical clocks......Page 72 3.3.1 Definition......Page 73 No strong consistency......Page 74 3.4.1 definition......Page 75 Isomorphism......Page 76 3.4.3 On the size of vector clocks......Page 77 3.5 Efficient implementations of vector clocks......Page 79 3.5.1 Singhal–Kshemkalyani’s differential technique......Page 80 3.5.2 Fowler–Zwaenepoel’s direct-dependency technique......Page 82 3.6 Jard–Jourdan’s adaptive technique......Page 85 3.7.1 Definition......Page 88 3.8 Virtual time......Page 89 3.8.1 Virtual time definition......Page 90 3.8.2 Comparison with Lamport’s logical clocks......Page 91 3.8.3 Time warp mechanism......Page 92 Antimessages and the rollback mechanism......Page 93 Global virtual time......Page 95 Memory management and flow control......Page 96 Snapshots and crash recovery......Page 97 3.9.1 Motivation......Page 98 3.9.2 Definitions and terminology......Page 99 Clock offset and delay estimation......Page 100 3.10 Chapter summary......Page 101 References......Page 104 4.1 Introduction......Page 107 4.2.1 System model......Page 110 4.2.3 Interpretation in terms of cuts......Page 111 4.2.4 Issues in recording a global state......Page 112 4.3.1 Chandy–Lamport algorithm......Page 113 The algorithm......Page 114 4.3.2 Properties of the recorded global state......Page 115 4.4.1 Spezialetti–Kearns algorithm......Page 117 Efficient dissemination of the recorded snapshot......Page 118 4.4.2 Venkatesan’s incremental snapshot algorithm......Page 119 4.4.3 Helary’s wave synchronization method......Page 120 4.5 Snapshot algorithms for non-FIFO channels......Page 121 4.5.1 Lai–Yang algorithm......Page 122 4.5.2 Li et al.’s algorithm......Page 123 4.5.3 Mattern’s algorithm......Page 125 4.6 Snapshots in a causal delivery system......Page 126 4.6.2 Channel state recording in Acharya–Badrinath algorithm......Page 127 4.6.3 Channel state recording in Alagar–Venkatesan algorithm......Page 128 4.7 Monitoring global state......Page 129 4.8 Necessary and sufficient conditions for consistent global snapshots......Page 130 Difference between a zigzag path and a causal path......Page 132 Consistent global snapshots......Page 133 4.9 Finding consistent global snapshots in a distributed computation......Page 134 First observation......Page 135 Second observation......Page 136 Third observation......Page 137 4.9.2 Manivannan–Netzer–Singhal algorithm for enumerating consistent snapshots......Page 138 Construction of an R-graph......Page 139 4.10 Chapter summary......Page 141 4.12 Notes on references......Page 142 References......Page 143 5.1 Topology abstraction and overlays......Page 146 5.2.1 Application executions and control algorithm executions......Page 148 5.2.3 Symmetric and asymmetric algorithms......Page 149 5.2.6 Adaptive algorithms......Page 150 5.2.8 Execution inhibition......Page 151 5.2.9 Synchronous and asynchronous systems......Page 152 Process failure models [26]......Page 153 5.2.12 Wait-free algorithms......Page 154 5.3 Complexity measures and metrics......Page 155 5.4 Program structure......Page 157 5.5.1 Synchronous single-initiator spanning tree algorithm using flooding......Page 158 5.5.2 Asynchronous single-initiator spanning tree algorithm using flooding......Page 160 Design 1......Page 163 Design 2......Page 165 5.5.4 Asynchronous concurrent-initiator depth first search spanning tree algorithm......Page 166 5.5.5 Broadcast and convergecast on a tree......Page 168 5.5.6 Single source shortest path algorithm: synchronous Bellman–Ford......Page 169 5.5.7 Distance vector routing......Page 170 5.5.9 All sources shortest paths: asynchronous distributed Floyd–Warshall......Page 171 Asynchronous algorithm (Algorithm 5.9)......Page 175 Synchronous algorithm (Algorithm 5.10)......Page 176 5.5.11 Minimum-weight spanning tree (MST) algorithm in a synchronous system......Page 177 5.5.12 Minimum-weight spanning tree (MST) in an asynchronous system......Page 182 General observations on synchronous and asynchronous algorithms......Page 183 A simple synchronizer......Page 184 The synchronizer......Page 185 The synchronizer......Page 186 5.7 Maximal independent set (MIS)......Page 189 5.8 Connected dominating set......Page 191 5.9 Compact routing tables......Page 192 5.10 Leader election......Page 194 5.11 Challenges in designing distributed graph algorithms......Page 195 5.12.1 Problem definition......Page 196 Read......Page 197 5.12.4 Converging to an replication scheme......Page 198 5.13 Chapter summary......Page 202 5.14 Exercises......Page 203 5.15 Notes on references......Page 205 References......Page 206 Notation......Page 209 6.1.1 Asynchronous executions......Page 210 6.1.3 Causally ordered (CO) executions......Page 211 6.1.4 Synchronous execution (SYNC)......Page 214 6.2 Asynchronous execution with synchronous communication......Page 215 6.2.1 Executions realizable with synchronous communication (RSC)......Page 216 Asynchronous programs on synchronous systems......Page 219 6.3 Synchronous program order on an asynchronous system......Page 220 6.3.1 Rendezvous......Page 221 6.3.2 Algorithm for binary rendezvous......Page 222 6.4 Group communication......Page 225 6.5 Causal order (CO)......Page 226 6.5.1 The Raynal–Schiper–Toueg algorithm [22]......Page 227 6.5 Causal order (CO)......Page 228 Multicast M43......Page 233 Processing at P6......Page 234 6.6 Total order......Page 235 Sender......Page 236 Complexity......Page 238 6.7 A nomenclature for multicast......Page 240 6.8 Propagation trees for multicast......Page 241 6.9 Classification of application-level multicast algorithms......Page 245 Privilege-based algorithms......Page 246 Destination agreement algorithms......Page 247 6.10 Semantics of fault-tolerant group communication......Page 248 6.11.1 Reverse path forwarding (RPF) for constrained flooding......Page 250 Steiner tree problem......Page 251 6.11.3 Multicast cost functions......Page 252 Delay-bounded minimal Steiner tree problem......Page 253 6.11.5 Core-based trees......Page 255 6.13 Exercises......Page 256 6.14 Notes on references......Page 258 References......Page 259 7.1 Introduction......Page 261 7.2 System model of a distributed computation......Page 262 7.3.2 Formal description......Page 263 7.3.3 Discussion......Page 264 Basic idea......Page 265 7.4.2 Correctness of the algorithm......Page 266 7.5 A spanning-tree-based termination detection algorithm......Page 267 A problem with the algorithm......Page 268 The basic idea......Page 269 The algorithm description......Page 270 7.5.4 An example......Page 271 7.6 Message-optimal termination detection......Page 273 7.6.1 The main idea......Page 274 7.6.2 Formal description of the algorithm......Page 275 7.7 Termination detection in a very general distributed computing model......Page 277 7.7.2 Notation......Page 278 Informal description......Page 279 Formal description......Page 280 Informal description......Page 281 Formal description......Page 282 Assumptions......Page 283 7.8.2 A naive counting method......Page 284 7.8.3 The four counter method......Page 285 7.8.4 The sceptic algorithm......Page 286 Formal description......Page 287 7.8.6 Vector counters method......Page 288 Formal description......Page 290 7.9 Termination detection in a faulty distributed system......Page 292 The concept of flow invariant......Page 293 7.9.2 Taking snapshots......Page 294 Data structures......Page 295 7.9.2 Taking snapshots......Page 296 7.9.4 Performance analysis......Page 298 7.11 Exercises......Page 299 References......Page 300 8.1 The muddy children puzzle......Page 302 8.2.1 Knowledge operators......Page 303 8.2.2 The muddy children puzzle again......Page 304 8.2.3 Kripke structures......Page 305 Scenario A......Page 307 8.2.5 Properties of knowledge......Page 308 8.3 Knowledge in synchronous systems......Page 309 8.4.1 Logic and definitions......Page 310 8.4.2 Agreement in asynchronous systems......Page 311 Eventual common knowledge......Page 312 8.4.4 Concurrent common knowledge......Page 313 Three-phase send-inhibitory algorithm......Page 315 Complexity......Page 316 8.5 Knowledge transfer......Page 318 8.6 Knowledge and clocks......Page 320 8.7 Chapter summary......Page 321 8.8 Exercises......Page 322 References......Page 323 9.1 Introduction......Page 325 9.2.1 System model......Page 326 9.2.3 Performance metrics......Page 327 Best and worst case performance......Page 328 9.3 Lamport’s algorithm......Page 329 Correctness......Page 330 9.4 Ricart–Agrawala algorithm......Page 332 Correctness......Page 333 9.5 Singhal’s dynamic information-structure algorithm......Page 335 Data structures......Page 336 9.5.1 Description of the algorithm......Page 337 Achieving mutual exclusion......Page 339 Low load condition......Page 340 9.6 Lodha and Kshemkalyani’s fair mutual exclusion algorithm......Page 341 9.6.2 Description of the algorithm......Page 342 9.6.4 Message complexity......Page 345 9.7 Quorum-based mutual exclusion algorithms......Page 347 9.8 Maekawa’s algorithm......Page 348 Correctness......Page 349 Handling deadlocks......Page 350 9.9.1 Constructing a tree-structured quorum......Page 351 9.9.4 Examples of tree-structured quorums......Page 353 9.9.5 The algorithm for distributed mutual exclusion......Page 355 9.11 Suzuki–Kasami’s broadcast algorithm......Page 356 Performance......Page 358 9.12 Raymond’s tree-based algorithm......Page 359 9.12.1 The HOLDER variables......Page 360 Data structures......Page 361 MAKE_REQUEST......Page 362 Message overtaking......Page 363 Deadlock is impossible......Page 364 Starvation is impossible......Page 365 9.12.5 Cost and performance analysis......Page 366 9.12.7 Node failures and recovery......Page 367 9.14 Exercises......Page 368 9.15 Notes on references......Page 369 References......Page 370 10.2 System model......Page 372 10.3.1 Deadlock handling strategies......Page 373 Detection of deadlocks......Page 374 10.4 Models of deadlocks......Page 375 10.4.3 The OR model......Page 376 10.4.5 The p model......Page 377 10.5.1 Path-pushing algorithms......Page 378 10.5.4 Global state detection-based algorithms......Page 379 10.6 Mitchell and Merritt’s algorithm for the single-resource model......Page 380 10.7 Chandy–Misra–Haas algorithm for the AND model......Page 382 The algorithm......Page 383 Basic idea......Page 384 10.9 Kshemkalyani–Singhal algorithm for the P-out-of- model......Page 385 10.9.1 Informal description of the algorithm......Page 387 The problem of termination detection......Page 388 10.9.2 The algorithm......Page 389 10.10 Chapter summary......Page 394 10.12 Notes on references......Page 395 References......Page 396 11.1 Stable and unstable predicates......Page 399 Termination [20]......Page 400 11.2 Modalities on predicates......Page 402 11.3 Centralized algorithm for relational predicates......Page 404 11.4 Conjunctive predicates......Page 408 11.4.1 Interval-based centralized algorithm for conjunctive predicates......Page 409 11.4.2 Global state-based centralized algorithm for , where is conjunctive......Page 412 11.5.1 Distributed state-based token algorithm for, Possibly (Phi) where Phi is conjunctive......Page 415 11.5.2 Distributed interval-based token algorithm for Definitely (Phi), where is conjunctive......Page 417 11.5.3 Distributed interval-based piggybacking algorithm for Possibly (Phi), where Phi is conjuctive......Page 421 11.6 Further classification of predicates......Page 424 11.7 Chapter summary......Page 425 11.8 Exercises......Page 426 11.9 Notes on references......Page 427 References......Page 428 12.1 Abstraction and advantages......Page 430 12.2 Memory consistency models......Page 433 12.2.1 Strict consistency/atomic consistency/linearizability......Page 434 Implementations......Page 435 12.2.2 Sequential consistency......Page 437 Implementations......Page 438 Local-write algorithm......Page 439 12.2.3 Causal consistency......Page 440 12.2.4 PRAM (pipelined RAM) or processor consistency......Page 442 12.2.5 Slow memory......Page 443 12.2.7 Other models based on synchronization instructions......Page 444 Release consistency [12]......Page 445 Entry consistency [9]......Page 446 12.3.1 Lamport’s bakery algorithm......Page 447 12.3.2 Lamport’s WRWR mechanism and fast mutual exclusion......Page 449 12.3.3 Hardware support for mutual exclusion......Page 452 12.5 Register hierarchy and wait-free simulations......Page 454 12.5.1 Construction 1: SRSW safe to MRSW safe......Page 457 12.5.3 Construction 3: boolean MRSW safe to integer-valued MRSW safe......Page 458 12.5.4 Construction 4: boolean MRSW safe to boolean MRSW regular......Page 459 12.5.5 Construction 5: boolean MRSW regular to integer-valued MRSW regular......Page 460 12.5.6 Construction 6: boolean MRSW regular to integer-valued MRSW atomic......Page 462 12.5.7 Construction 7: integer MRSW atomic to integer MRMW atomic......Page 464 12.5.8 Construction 8: integer SRSW atomic to integer MRSW atomic......Page 465 Achieving linearizability......Page 466 12.6 Wait-free atomic snapshots of shared objects......Page 467 12.7 Chapter summary......Page 471 12.8 Exercises......Page 472 12.9 Notes on references......Page 473 References......Page 474 13.1 Introduction......Page 476 13.2.1 System model......Page 477 13.2.3 Consistent system states......Page 478 13.2.4 Interactions with the outside world......Page 479 13.2.5 Different types of messages......Page 480 Duplicate messages......Page 481 13.3 Issues in failure recovery......Page 482 13.4.1 Uncoordinated checkpointing......Page 484 13.4.2 Coordinated checkpointing......Page 485 Non-blocking checkpoint coordination......Page 486 13.4.3 Impossibility of min-process non-blocking checkpointing......Page 487 13.4.4 Communication-induced checkpointing......Page 488 Model-based checkpointing......Page 489 13.5.1 Deterministic and non-deterministic events......Page 490 The no-orphans consistency condition......Page 491 13.5.2 Pessimistic logging......Page 492 13.5.3 Optimistic logging......Page 493 13.5.4 Causal logging......Page 494 Second phase......Page 496 13.6.2 The rollback recovery algorithm......Page 497 13.7 Juang–Venkatesan algorithm for asynchronous checkpointing and recovery......Page 498 13.7.1 System model and assumptions......Page 499 Basic idea......Page 500 Description of the algorithm......Page 501 13.8 Manivannan–Singhal quasi-synchronous checkpointing algorithm......Page 503 Properties......Page 504 An explanation......Page 506 Handling the replay of messages......Page 509 Handling of received messages......Page 510 Features......Page 511 Notation......Page 512 13.9.2 Informal description of the algorithm......Page 513 Handling in-transit orphan messages......Page 514 The rollback protocol......Page 515 13.9.4 Correctness proof......Page 517 13.10 Helary–Mostefaoui–Netzer–Raynal communication-induced protocol......Page 519 To checkpoint or not to checkpoint?......Page 520 Reducing the number of forced checkpoints......Page 521 13.10.2 The checkpointing protocol......Page 523 13.11 Chapter summary......Page 525 13.13 Notes on references......Page 526 References......Page 527 14.1 Problem definition......Page 530 The Byzantine agreement problem......Page 532 The interactive consistency problem......Page 533 14.2 Overview of results......Page 534 14.3 Agreement in a failure-free system (synchronous or asynchronous)......Page 535 14.4.1 Consensus algorithm for crash failures (synchronous system)......Page 536 14.4.3 Upper bound on Byzantine processes......Page 537 Byzantine agreement tree algorithm: exponential (synchronous system)......Page 539 Phase-king algorithm for consensus: polynomial (synchronous system)......Page 546 14.5.1 Impossibility result for the consensus problem......Page 549 14.5.2 Terminating reliable broadcast......Page 551 14.5.4 k-set consensus......Page 552 Algorithm outline......Page 553 Notation......Page 555 Convergence rate of approximation......Page 556 Correctness......Page 557 Problem definition......Page 558 Algorithm......Page 559 Correctness......Page 562 14.6.1 Impossibility result......Page 564 14.6.2 Consensus numbers and consensus hierarchy [14]......Page 567 FIFO queue......Page 569 Compare&Swap......Page 570 Read–modify–write abstraction......Page 571 14.6.3 Universality of consensus objects [14]......Page 572 A non-blocking universal algorithm......Page 573 14.6.4 Shared memory k-set consensus......Page 576 14.6.5 Shared memory renaming......Page 577 14.6.6 Shared memory renaming using splitters......Page 580 14.7 Chapter summary......Page 582 14.8 Exercises......Page 583 14.9 Notes on references......Page 584 References......Page 585 15.1 Introduction......Page 587 15.2.1 The system model......Page 588 15.2.2 Failure detectors......Page 589 Completeness......Page 590 Eventual accuracy......Page 591 15.2.5 Reducibility of failure detectors......Page 592 15.2.6 Reducing weak failure detector W to a strong failure detector S......Page 593 A correctness argument......Page 594 15.2.7 Reducing an eventually weak failure detector . to an eventually strong failure detector.........Page 595 An explanation of the algorithm......Page 596 15.3 The consensus problem......Page 597 15.3.2 A solution using strong failure detector S......Page 598 An explanation of the algorithm......Page 599 15.3.3 A solution using eventually strong failure detector.........Page 600 An explanation of the algorithm......Page 602 15.4 Atomic broadcast......Page 603 An explanation of the algorithm......Page 604 15.6 The weakest failure detectors to solve fundamental agreement problems......Page 605 15.6.1 Realistic failure detectors......Page 606 15.6.2 The weakest failure detector for consensus......Page 608 15.7 An implementation of a failure detector......Page 609 15.8 An adaptive failure detection protocol......Page 611 Assumptions......Page 612 The protocol FDL......Page 613 Properties of FDL......Page 615 References......Page 616 16.1 Introduction......Page 618 16.2.1 Basis of authentication......Page 619 16.2.4 Notation......Page 620 16.2.5 Design principles for cryptographic protocols......Page 621 16.3 Protocols based on symmetric cryptosystems......Page 622 Weaknesses......Page 623 Weaknesses......Page 624 16.3.4 A protocol based on an authentication server......Page 625 16.3.5 One-time password scheme......Page 626 Protocol description......Page 627 16.3.6 Otway–Rees protocol......Page 629 Weaknesses......Page 630 The authentication protocol......Page 631 Weaknesses......Page 634 16.4.1 The basic protocol......Page 635 16.4.2 A modified protocol with a certification authority......Page 636 16.4.3 Needham and Schroeder protocol......Page 637 An impersonation attack on the protocol......Page 638 16.4.4 SSL protocol......Page 639 SSL handshake protocol......Page 640 How SSL provides authentication......Page 641 16.5 Password-based authentication......Page 642 16.5.1 Encrypted key exchange (EKE) protocol......Page 643 16.5.2 Secure remote password (SRP) protocol......Page 644 16.6 Authentication protocol failures......Page 645 16.7 Chapter summary......Page 646 16.9 Notes on references......Page 647 References......Page 648 17.1 Introduction......Page 651 17.2 System model......Page 652 17.3 Definition of self-stabilization......Page 654 17.3.1 Randomized and probabilistic self-stabilization......Page 655 Dijkstra’s self-stabilizing token ring system......Page 656 First solution......Page 657 Second solution......Page 658 Ghosh’s solution......Page 661 17.4.2 Uniform vs. non-uniform networks......Page 662 17.4.3 Central and distributed demons......Page 663 17.4.4 Reducing the number of states in a token ring......Page 664 17.4.6 Mutual exclusion......Page 665 17.4.7 Costs of self-stabilization......Page 666 17.5.1 Layering and modularization......Page 667 Topology-based primitives......Page 668 17.6 Communication protocols......Page 669 17.7 Self-stabilizing distributed spanning trees......Page 670 17.8.1 Dolev, Israeli, and Moran algorithm......Page 672 17.8.3 Arora and Gouda algorithm for spanning-tree construction......Page 675 17.8.5 Afek and Bremler algorithm for spanning-tree construction......Page 676 17.9 An anonymous self-stabilizing algorithm for 1-maximal independent set in trees......Page 677 Description of algorithm......Page 678 17.10 A probabilistic self-stabilizing leader election algorithm......Page 680 17.11.1 Compilers for sequential programs......Page 682 17.11.2 Compilers for asynchronous message passing systems......Page 683 17.11.3 Compilers for asynchronous shared memory systems......Page 684 Fault tolerance......Page 685 Symmetry......Page 687 17.14 Limitations of self-stabilization......Page 688 Pseudo-stabilization......Page 689 17.16 Exercises......Page 690 References......Page 691 18.1 Introduction......Page 697 18.1.2 Application layer overlays......Page 698 18.2 Data indexing and overlays......Page 699 Structured overlays......Page 700 18.3.1 Unstructured overlays: properties......Page 701 18.3.3 Search in Gnutella and unstructured overlays......Page 702 Search strategies......Page 703 18.3.4 Replication strategies......Page 704 18.3.5 Implementing replication strategies......Page 707 18.4.1 Overview......Page 708 18.4.2 Simple lookup......Page 709 18.4.3 Scalable lookup......Page 710 Node joins......Page 711 Node failures and departures......Page 714 18.5.1 Overview......Page 715 18.5.2 CAN initialization......Page 716 18.5.3 CAN routing......Page 717 18.5.4 CAN maintainence......Page 718 18.5.5 CAN optimizations......Page 720 18.6.1 Overview......Page 721 Prefix routing......Page 722 Router Table......Page 723 18.6.3 Object publication and object search......Page 725 18.6.4 Node insertion......Page 726 18.6.5 Node deletion......Page 727 18.7.1 Fairness: a game theory application......Page 728 18.7.2 Trust or reputation management......Page 729 Routing rule......Page 730 18.8.2 Bounds on DHT storage and routing distance......Page 731 18.9 Graph structures of complex networks......Page 732 18.10.1 Basic laws and their definitions......Page 734 18.10.2 Properties of the Internet......Page 735 Classification of scale-free networks......Page 737 Impact on network diameter......Page 738 Impact on network partitioning......Page 739 18.12 Small-world networks......Page 740 18.13 Scale-free networks......Page 741 18.13.1 Master-equation approach......Page 742 18.14 Evolving networks......Page 743 Continuum theory analysis......Page 745 18.16 Exercises......Page 747 18.17 Notes on references......Page 748 References......Page 749 Index......Page 751 Distributed computing has important applications in wireless and mobile networks, and the Internet. This textbook presents the fundamental principles, models and practical algorithms underlying all aspects of distributed computing. Illustrations and simple ideas will be used to present the algorithms and explain the main concepts, rather than complex proofs. Whilst the focus is primarily on the foundations and algorithms of distributed computing, practical systems-like problems such as mutual exclusion, deadlock detection and leader election, will also be addressed in detail. Some of the most interesting recent developments in the field - sensor networks, mobile computing, peer-to-peer computing and network security - are also covered. With new techniques of algorithm design, worked examples, exercises problems and solutions, this textbook is ideal for advanced undergraduates and graduate students of electrical and computer engineering and computer science, as well as practitioners working in data networking, wireless networking, and sensor networks