book

Distributed Systems, 2nd Edition

by Sukumar Ghosh

July 2014

Intermediate to advanced

554 pages

17h 49m

English

Chapman and Hall/CRC

Read now

Unlock full access

1.1 What Is a Distributed System?1.2 Why Distributed Systems1.3 Examples of Distributed Systems1.4 Important Issues in Distributed Systems1.5 Common Subproblems1.6 Implementing a Distributed System1.7 Parallel versus Distributed Systems1.8 Bibliographic NotesExercises
2.1 Introduction2.1.1 Processes and Threads2.1.2 Client–Server Model2.1.3 Middleware2.2 Network Protocols2.2.1 Ethernet2.2.2 Wireless Networks2.2.3 OSI Model2.2.4 IP2.2.5 Transport Layer Protocols2.2.6 Interprocess Communication Using Sockets2.3 Naming2.3.1 Domain Name Service2.3.2 Naming Service for Mobile Clients2.4 Remote Procedure Call2.4.1 Implementing RPC2.4.2 Sun ONC/RPC2.5 Remote Method Invocation2.6 Messages2.6.1 Transient and Persistent Messages2.6.2 Streams2.7 Web Services2.8 Event Notification2.9 Virtualization: Cloud Computing2.9.1 Classification of Cloud Services2.9.2 MapReduce2.9.3 Hadoop2.10 Mobile Agents2.11 Basic Group Communication Services2.12 Concluding Remarks2.13 Bibliographic NotesExercises
3.1 Need for a Model3.2 Message-Passing Model for Interprocess Communication3.2.1 Process Actions3.2.2 Channels3.2.3 Synchronous versus Asynchronous Systems3.2.4 Real-Time Systems3.3 Shared Variables3.3.1 Linda3.4 Modeling Mobile Agents3.5 Relationship among Models3.5.1 Strong and Weak Models3.5.2 Implementing a FIFO Channel Using a Non-FIFO Channel3.5.3 Implementing Message Passing Using Shared Memory3.5.4 Implementing Shared Memory Using Message Passing3.5.5 Impossibility Result with Channels3.6 Classification Based on Special Properties3.6.1 Reactive versus Transformational Systems3.6.2 Named versus Anonymous Systems3.7 Complexity Measures3.8 Concluding Remarks3.9 Bibliographic NotesExercises
4.1 Introduction4.2 Guarded Actions4.3 Nondeterminism4.4 Atomic Operations4.5 Fairness4.6 Central versus Distributed Schedulers4.7 Concluding Remarks4.8 Bibliographic NotesExercises
5.1 Introduction5.2 Correctness Criteria5.2.1 Safety Properties5.2.2 Liveness Properties5.3 Correctness Proofs5.3.1 Quick Review of Propositional Logic5.3.2 Brief Overview of Predicate Logic5.4 Assertional Reasoning: Proving Safety Properties5.5 Proving Liveness Properties Using Well-Founded Sets5.6 Programming Logic5.7 Predicate Transformers5.8 Concluding Remarks5.9 Bibliographic NotesExercises

6.1 Introduction6.1.1 Physical Time6.1.2 Sequential and Concurrent Events6.2 Logical Clocks6.3 Vector Clocks6.4 Physical Clock Synchronization6.4.1 Preliminary Definitions6.4.2 Clock Reading Error6.4.3 Algorithms for Internal Synchronization6.4.4 Algorithms for External Synchronization6.5 Concluding Remarks6.6 Bibliographic NotesExercises
7.1 Introduction7.2 Solutions on Message-Passing Systems7.2.1 Lamport’s Solution7.2.2 Ricart–Agrawala’s Solution7.2.3 Maekawa’s Solution7.3 Token-Passing Algorithms7.3.1 Suzuki–Kasami Algorithm7.3.2 Raymond’s Algorithm7.4 Solutions on the Shared-Memory Model7.4.1 Peterson’s Algorithm7.5 Mutual Exclusion Using Special Instructions7.5.1 Solution Using Test-and-Set7.5.2 Solution Using Load-Linked and Store-Conditional7.6 Group Mutual Exclusion7.7 Concluding Remarks7.8 Bibliographic NotesExercises
8.1 Introduction8.2 Properties of Consistent Snapshots8.2.1 Cuts and Consistent Cuts8.3 Chandy–Lamport Algorithm8.3.1 Two Examples8.3.1.1 Example 1: Counting of Tokens8.3.1.2 Example 2: Communicating State Machines8.4 Lai–Yang Algorithm8.5 Distributed Debugging8.5.1 Constructing the State Lattice8.5.2 Evaluating Predicates8.6 Concluding Remarks8.7 Bibliographic NotesExercises
9.1 Introduction9.2 Elementary Algorithm for All-to-All Broadcasting9.3 Termination-Detection Algorithms9.3.1 Dijkstra–Scholten Algorithm9.3.2 Termination Detection on a Unidirectional Ring9.3.3 Credit-Recovery Algorithm for Termination Detection9.4 Wave Algorithms9.4.1 Propagation of Information with Feedback9.5 Distributed Deadlock Detection9.5.1 Resource Deadlock and Communication Deadlock9.5.2 Detection of Resource Deadlock9.5.3 Detection of Communication Deadlock9.6 Concluding Remarks9.7 Bibliographic NotesExercises
10.1 Introduction10.2 Routing Algorithms10.2.1 Computation of Shortest Path10.2.1.1 Complexity Analysis10.2.1.2 Chandy–Misra Modification of the Shortest Path Algorithm10.2.2 Distance-Vector Routing10.2.3 Link-State Routing10.2.4 Interval Routing10.2.4.1 Interval Routing Rule10.2.5 Prefix Routing10.3 Graph Traversal10.3.1 Spanning Tree Construction10.3.2 Tarry’s Graph Traversal Algorithm10.3.3 Minimum Spanning Tree Construction10.3.3.1 Overall Strategy10.3.3.2 Detecting the Least Weight Outgoing Edge10.3.3.3 Message Complexity10.4 Graph Coloring10.4.1 (D + 1)-Coloring Algorithm10.4.2 6-Coloring of Planar Graphs10.5 Cole–Vishkin Reduction Algorithm for Tree Coloring10.6 Maximal Independent Set: Luby’s Algorithm10.7 Concluding Remarks10.8 Bibliographic NotesExercises
11.1 Introduction11.2 Leader Election11.2.1 Bully Algorithm11.2.2 Maxima Finding on a Ring11.2.2.1 Chang–Roberts Algorithm11.2.2.2 Franklin’s Algorithm11.2.2.3 Peterson’s Algorithm11.2.3 Election in Arbitrary Networks11.2.4 Election in Anonymous Networks11.3 Synchronizers11.3.1 ABD Synchronizer11.3.2 Awerbuch’s Synchronizers11.3.2.1 α-Synchronizer11.3.2.2 β-Synchronizer11.3.2.3 γ-Synchronizer11.3.2.4 Performance of Synchronizer-Based Algorithms11.4 Concluding Remarks11.5 Bibliographic NotesExercises
12.1 Introduction12.2 Classification of Faults12.3 Specification of Faults12.4 Fault-Tolerant Systems12.4.1 Masking Tolerance12.4.2 Nonmasking Tolerance12.4.3 Fail-Safe Tolerance12.4.4 Graceful Degradation12.4.5 Detection of Failures in Synchronous Systems12.5 Tolerating Crash Failures12.5.1 Double and Triple Modular Redundancy12.6 Tolerating Omission Failures12.6.1 Stenning’s Protocol12.6.2 Sliding Window Protocol12.6.3 Alternating Bit Protocol12.6.4 How TCP Works12.7 Concluding Remarks12.8 Bibliographic NotesExercises
13.1 Introduction13.2 Consensus in Asynchronous Systems13.2.1 Bivalent and Univalent States13.3 Consensus in Synchronous Systems: Byzantine Generals Problem13.3.1 Solution with No Traitor13.3.2 Solution with Traitors: Interactive Consistency Criteria13.3.3 Consensus with Oral Messages13.3.3.1 Impossibility Result13.3.3.2 OM(m) Algorithm13.3.4 Consensus Using Signed Messages13.4 Paxos Algorithm13.4.1 Safety Properties13.4.2 Liveness Properties13.5 Failure Detectors13.5.1 Solving Consensus Using Failure Detectors13.5.1.1 Consensus Using P13.5.1.2 Consensus Using S13.5.1.3 Rationale13.5.1.4 Implementing a Failure Detector13.6 Concluding Remarks13.7 Bibliographic NotesExercises
14.1 Introduction14.2 Classification of Transactions14.2.1 Flat Transactions14.2.2 Nested Transactions14.2.3 Distributed Transactions14.3 Implementing Transactions14.4 Concurrency Control and Serializability14.4.1 Testing for Serializability14.4.2 Two-Phase Locking14.4.3 Concurrency Control via Time Stamp Ordering14.5 Atomic Commit Protocols14.5.1 One-Phase Commit14.5.2 Two-Phase Commit14.5.3 Three-Phase Commit14.6 Recovery from Failures14.6.1 Stable Storage14.6.2 Checkpointing and Rollback Recovery14.6.3 Message Logging14.7 Concluding Remarks14.8 Bibliographic NotesExercises
15.1 Introduction15.2 Atomic Multicast15.3 IP Multicast15.3.1 Reverse Path Forwarding15.4 Application Layer Multicast15.5 Ordered Multicasts15.5.1 Implementing Total Order Multicast15.5.1.1 Implementation Using a Sequencer15.5.1.2 Distributed Implementation15.5.2 Implementing Causal Order Multicast15.6 Reliable Multicast15.6.1 Scalable Reliable Multicast15.6.2 Reliable Ordered Multicast15.7 Open Groups15.7.1 View-Synchronous Group Communication15.8 Overview of Transis15.9 Concluding Remarks15.10 Bibliographic NotesExercises
16.1 Introduction16.1.1 Reliability versus Availability16.2 Architecture of Replicated Data Management16.2.1 Passive versus Active Replication16.2.2 Fault-Tolerant State Machines16.3 Data-Centric Consistency Models16.3.1 Strict Consistency16.3.2 Linearizability16.3.3 Sequential Consistency16.3.4 Causal Consistency16.3.5 FIFO Consistency16.4 Client-Centric Consistency Protocols16.4.1 Eventual Consistency16.4.2 Consistency Models for Mobile Clients16.4.2.1 Read-After-Read Consistency16.4.2.2 Write-After-Write Consistency16.4.2.3 Read-After-Write Consistency16.4.2.4 Write-After-Read Consistency16.5 Implementation of Data-Centric Consistency Models16.6 Quorum-Based Protocols16.7 Replica Placement16.8 Brewer’s CAP Theorem16.9 Case Studies16.9.1 Replication Management in Coda16.9.2 Replication Management in Bayou16.9.3 Amazon Dynamo16.10 Concluding Remarks16.11 Bibliographic NotesExercises
17.1 Introduction17.2 Theoretical Foundations17.3 Stabilizing Mutual Exclusion17.3.1 Mutual Exclusion on a Unidirectional Ring17.3.2 Mutual Exclusion on a Bidirectional Array17.4 Stabilizing Graph Coloring17.5 Stabilizing Spanning Tree Protocol17.6 Stabilizing Maximal Matching17.7 Distributed Reset17.8 Stabilizing Clock Phase Synchronization17.9 Concluding Remarks17.10 Bibliographic NotesExercises
18.1 Introduction18.1.1 Event-Driven Simulation18.2 Distributed Simulation18.2.1 Challenges18.2.2 Correctness Issues18.3 Conservative Simulation18.4 Optimistic Simulation and Time Warp18.4.1 Global Virtual Time18.5 Concluding Remarks18.6 Bibliographic NotesExercises
19.1 Introduction19.2 Security Mechanisms19.3 Common Security Attacks19.3.1 Eavesdropping19.3.2 Denial of Service19.3.3 Data Tampering19.3.4 Masquerading19.3.5 Man in the Middle19.3.6 Malicious Software19.3.6.1 Virus19.3.6.2 Worms19.3.6.3 Spyware19.4 Encryption19.5 Secret Key Cryptosystem19.5.1 Confusion and Diffusion19.5.2 DES19.5.3 3DES19.5.4 AES19.5.5 One-Time Pad19.5.6 Stream Ciphers19.5.7 Steganography19.6 Public Key Cryptosystems19.6.1 Rivest–Shamir–Adleman Cryptosystem19.6.2 ElGamal Cryptosystem19.7 Digital Signatures19.7.1 Signatures in Secret-Key Cryptosystems19.7.2 Signatures in Public-Key Cryptosystems19.8 Hashing Algorithms19.8.1 Birthday Attack19.9 Elliptic Curve Cryptography19.10 Authentication Server19.10.1 Authentication Service for Secret-Key Cryptosystems19.10.2 Authentication Server for Public-Key Systems19.11 Digital Certificates19.12 Case Studies19.12.1 Kerberos19.12.2 Pretty Good Privacy19.12.3 Secure Socket Layer19.13 Virtual Private Networks and Firewalls19.13.1 Virtual Private Network19.13.2 Firewall19.14 Sharing a Secret19.15 Concluding Remarks19.16 Bibliographic NotesExercisesProgramming Exercises
20.1 Vision20.2 Architecture of Sensor Nodes20.2.1 MICA Mote20.2.2 ZigBee-Enabled Sensor Nodes20.2.3 TinyOS® Operating System20.3 Challenges in Wireless Sensor Networks20.3.1 Energy Conservation20.3.2 Fault Tolerance20.3.3 Routing20.3.4 Time Synchronization20.3.5 Location Management20.3.6 Middleware Design20.3.7 Security20.4 Routing Algorithms20.4.1 Directed Diffusion20.4.2 Cluster-Based Routing20.4.2.1 LEACH20.4.2.2 PEGASIS20.4.3 Metadata-Based Routing: SPIN20.5 Time Synchronization Using Reference Broadcast20.5.1 Reference Broadcast20.6 Localization Algorithms20.6.1 RSSI-Based Ranging20.6.2 Ranging Using Time Difference of Arrival20.6.3 Anchor-Based Ranging20.7 Security in Sensor Networks20.7.1 SPIN for Data Security20.7.1.1 Overview of SNEP20.7.1.2 Overview of μTESLA20.7.2 Attacks on Routing20.7.2.1 Hello Flood20.8 Applications20.8.1 Health-Care Applications20.8.2 Environment Monitoring and Control20.8.3 Citizen Sensing20.8.4 Pursuer–Evader Game20.9 Concluding Remarks20.10 Bibliographic NotesExercisesProgramming Exercises
21.1 Introduction to Social Networks21.1.1 Milgram’s Experiment21.2 Metrics of Social Networks21.2.1 Clustering Coefficient21.2.2 Diameter21.3 Modeling Social Networks21.3.1 Erdös–Rényi Model21.3.2 Small-World Model21.3.3 Power-Law Graphs21.4 Centrality Measures in Social Networks21.4.1 Degree Centrality21.4.2 Closeness Centrality21.4.3 Betweenness Centrality21.5 Community Detection21.5.1 Girvan–Newman Algorithm21.6 Introduction to Peer-to-Peer Networks21.7 First-Generation P2P Systems21.7.1 Napster21.7.2 Gnutella21.8 Second-Generation P2P Systems21.8.1 KaZaA21.8.2 Chord21.8.3 Content-Addressable Network21.8.4 Pastry21.9 Koorde and De Bruijn Graph21.10 Skip Graph21.11 Replication Management21.12 BitTorrent and Free Riding21.13 Censorship Resistance, Anonymity21.14 Concluding Remarks21.15 Bibliographic NotesExercises

Content preview from Distributed Systems, 2nd Edition

Chapter 10

Graph Algorithms

10.1 Introduction

The topology of a distributed system is represented by a graph where the nodes represent processes and the links represent communication channels. Distributed algorithms for various graph theoretic problems have numerous applications in communication and networking. Here are some motivating examples.

The first example deals with routing in a communication network. When a message is sent from node i to a nonneighboring node j, the intermediate nodes route the message based on the information stored in the local routing table. This is called hop-by-hop or destination-based routing. An important problem is to compute these routing tables and maintain them, so that messages reach their destinations in ...