Distributed Systems, 2nd Edition

Distributed Systems, 2nd Edition

by Sukumar Ghosh
Released July 2014
Publisher(s): Chapman and Hall/CRC
ISBN: 9781498760058

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

This pivotal book provides a highly accessible, balanced treatment of the underlying theory and practical applications of distributed computing. As in the previous version, the language of the Second Edition is kept as unobscured as possible-clarity is given priority over mathematical formalism. Containing significant updates that mirror the phenomenal growth of distributed systems, this easily digestible text includes fresh exercises, examples, and case studies and explores new topics related to peer-to-peer and social networks. A solutions manual is available with qualifying course adoption.

Table of contents

  1. Preface
  2. Acknowledgments
  3. Author
  4. Section I - Background Materials
    1. Chapter 1 - Introduction
      1. 1.1 What Is a Distributed System?
      2. 1.2 Why Distributed Systems
      3. 1.3 Examples of Distributed Systems
      4. 1.4 Important Issues in Distributed Systems
      5. 1.5 Common Subproblems
      6. 1.6 Implementing a Distributed System
      7. 1.7 Parallel versus Distributed Systems
      8. 1.8 Bibliographic Notes
      9. Exercises
    2. Chapter 2 - Interprocess Communication: An Overview
      1. 2.1 Introduction
        1. 2.1.1 Processes and Threads
        2. 2.1.2 Client–Server Model
        3. 2.1.3 Middleware
      2. 2.2 Network Protocols
        1. 2.2.1 Ethernet
        2. 2.2.2 Wireless Networks
        3. 2.2.3 OSI Model
        4. 2.2.4 IP
        5. 2.2.5 Transport Layer Protocols
        6. 2.2.6 Interprocess Communication Using Sockets
      3. 2.3 Naming
        1. 2.3.1 Domain Name Service
        2. 2.3.2 Naming Service for Mobile Clients
      4. 2.4 Remote Procedure Call
        1. 2.4.1 Implementing RPC
        2. 2.4.2 Sun ONC/RPC
      5. 2.5 Remote Method Invocation
      6. 2.6 Messages
        1. 2.6.1 Transient and Persistent Messages
        2. 2.6.2 Streams
      7. 2.7 Web Services
      8. 2.8 Event Notification
      9. 2.9 Virtualization: Cloud Computing
        1. 2.9.1 Classification of Cloud Services
        2. 2.9.2 MapReduce
        3. 2.9.3 Hadoop
      10. 2.10 Mobile Agents
      11. 2.11 Basic Group Communication Services
      12. 2.12 Concluding Remarks
      13. 2.13 Bibliographic Notes
      14. Exercises
  5. Section II - Foundational Topics
    1. Chapter 3 - Models for Communication
      1. 3.1 Need for a Model
      2. 3.2 Message-Passing Model for Interprocess Communication
        1. 3.2.1 Process Actions
        2. 3.2.2 Channels
        3. 3.2.3 Synchronous versus Asynchronous Systems
        4. 3.2.4 Real-Time Systems
      3. 3.3 Shared Variables
        1. 3.3.1 Linda
      4. 3.4 Modeling Mobile Agents
      5. 3.5 Relationship among Models
        1. 3.5.1 Strong and Weak Models
        2. 3.5.2 Implementing a FIFO Channel Using a Non-FIFO Channel
        3. 3.5.3 Implementing Message Passing Using Shared Memory
        4. 3.5.4 Implementing Shared Memory Using Message Passing
        5. 3.5.5 Impossibility Result with Channels
      6. 3.6 Classification Based on Special Properties
        1. 3.6.1 Reactive versus Transformational Systems
        2. 3.6.2 Named versus Anonymous Systems
      7. 3.7 Complexity Measures
      8. 3.8 Concluding Remarks
      9. 3.9 Bibliographic Notes
      10. Exercises
    2. Chapter 4 - Representing Distributed Algorithms: Syntax and Semantics
      1. 4.1 Introduction
      2. 4.2 Guarded Actions
      3. 4.3 Nondeterminism
      4. 4.4 Atomic Operations
      5. 4.5 Fairness
      6. 4.6 Central versus Distributed Schedulers
      7. 4.7 Concluding Remarks
      8. 4.8 Bibliographic Notes
      9. Exercises
    3. Chapter 5 - Program Correctness
      1. 5.1 Introduction
      2. 5.2 Correctness Criteria
        1. 5.2.1 Safety Properties
        2. 5.2.2 Liveness Properties
      3. 5.3 Correctness Proofs
        1. 5.3.1 Quick Review of Propositional Logic
        2. 5.3.2 Brief Overview of Predicate Logic
      4. 5.4 Assertional Reasoning: Proving Safety Properties
      5. 5.5 Proving Liveness Properties Using Well-Founded Sets
      6. 5.6 Programming Logic
      7. 5.7 Predicate Transformers
      8. 5.8 Concluding Remarks
      9. 5.9 Bibliographic Notes
      10. Exercises
    4. Chapter 6 - Time in a Distributed System
      1. 6.1 Introduction
        1. 6.1.1 Physical Time
        2. 6.1.2 Sequential and Concurrent Events
      2. 6.2 Logical Clocks
      3. 6.3 Vector Clocks
      4. 6.4 Physical Clock Synchronization
        1. 6.4.1 Preliminary Definitions
        2. 6.4.2 Clock Reading Error
        3. 6.4.3 Algorithms for Internal Synchronization
        4. 6.4.4 Algorithms for External Synchronization
      5. 6.5 Concluding Remarks
      6. 6.6 Bibliographic Notes
      7. Exercises
  6. Section III - Important Paradigms
    1. Chapter 7 - Mutual Exclusion
      1. 7.1 Introduction
      2. 7.2 Solutions on Message-Passing Systems
        1. 7.2.1 Lamport’s Solution
        2. 7.2.2 Ricart–Agrawala’s Solution
        3. 7.2.3 Maekawa’s Solution
      3. 7.3 Token-Passing Algorithms
        1. 7.3.1 Suzuki–Kasami Algorithm
        2. 7.3.2 Raymond’s Algorithm
      4. 7.4 Solutions on the Shared-Memory Model
        1. 7.4.1 Peterson’s Algorithm
      5. 7.5 Mutual Exclusion Using Special Instructions
        1. 7.5.1 Solution Using Test-and-Set
        2. 7.5.2 Solution Using Load-Linked and Store-Conditional
      6. 7.6 Group Mutual Exclusion
      7. 7.7 Concluding Remarks
      8. 7.8 Bibliographic Notes
      9. Exercises
    2. Chapter 8 - Distributed Snapshot
      1. 8.1 Introduction
      2. 8.2 Properties of Consistent Snapshots
        1. 8.2.1 Cuts and Consistent Cuts
      3. 8.3 Chandy–Lamport Algorithm
        1. 8.3.1 Two Examples
          1. 8.3.1.1 Example 1: Counting of Tokens
          2. 8.3.1.2 Example 2: Communicating State Machines
      4. 8.4 Lai–Yang Algorithm
      5. 8.5 Distributed Debugging
        1. 8.5.1 Constructing the State Lattice
        2. 8.5.2 Evaluating Predicates
      6. 8.6 Concluding Remarks
      7. 8.7 Bibliographic Notes
      8. Exercises
    3. Chapter 9 - Global State Collection
      1. 9.1 Introduction
      2. 9.2 Elementary Algorithm for All-to-All Broadcasting
      3. 9.3 Termination-Detection Algorithms
        1. 9.3.1 Dijkstra–Scholten Algorithm
        2. 9.3.2 Termination Detection on a Unidirectional Ring
        3. 9.3.3 Credit-Recovery Algorithm for Termination Detection
      4. 9.4 Wave Algorithms
        1. 9.4.1 Propagation of Information with Feedback
      5. 9.5 Distributed Deadlock Detection
        1. 9.5.1 Resource Deadlock and Communication Deadlock
        2. 9.5.2 Detection of Resource Deadlock
        3. 9.5.3 Detection of Communication Deadlock
      6. 9.6 Concluding Remarks
      7. 9.7 Bibliographic Notes
      8. Exercises
    4. Chapter 10 - Graph Algorithms
      1. 10.1 Introduction
      2. 10.2 Routing Algorithms
        1. 10.2.1 Computation of Shortest Path
          1. 10.2.1.1 Complexity Analysis
          2. 10.2.1.2 Chandy–Misra Modification of the Shortest Path Algorithm
        2. 10.2.2 Distance-Vector Routing
        3. 10.2.3 Link-State Routing
        4. 10.2.4 Interval Routing
          1. 10.2.4.1 Interval Routing Rule
        5. 10.2.5 Prefix Routing
      3. 10.3 Graph Traversal
        1. 10.3.1 Spanning Tree Construction
        2. 10.3.2 Tarry’s Graph Traversal Algorithm
        3. 10.3.3 Minimum Spanning Tree Construction
          1. 10.3.3.1 Overall Strategy
          2. 10.3.3.2 Detecting the Least Weight Outgoing Edge
          3. 10.3.3.3 Message Complexity
      4. 10.4 Graph Coloring
        1. 10.4.1 (D + 1)-Coloring Algorithm
        2. 10.4.2 6-Coloring of Planar Graphs
      5. 10.5 Cole–Vishkin Reduction Algorithm for Tree Coloring
      6. 10.6 Maximal Independent Set: Luby’s Algorithm
      7. 10.7 Concluding Remarks
      8. 10.8 Bibliographic Notes
      9. Exercises
    5. Chapter 11 - Coordination Algorithms
      1. 11.1 Introduction
      2. 11.2 Leader Election
        1. 11.2.1 Bully Algorithm
        2. 11.2.2 Maxima Finding on a Ring
          1. 11.2.2.1 Chang–Roberts Algorithm
          2. 11.2.2.2 Franklin’s Algorithm
          3. 11.2.2.3 Peterson’s Algorithm
        3. 11.2.3 Election in Arbitrary Networks
        4. 11.2.4 Election in Anonymous Networks
      3. 11.3 Synchronizers
        1. 11.3.1 ABD Synchronizer
        2. 11.3.2 Awerbuch’s Synchronizers
          1. 11.3.2.1 α-Synchronizer
          2. 11.3.2.2 β-Synchronizer
          3. 11.3.2.3 γ-Synchronizer
          4. 11.3.2.4 Performance of Synchronizer-Based Algorithms
      4. 11.4 Concluding Remarks
      5. 11.5 Bibliographic Notes
      6. Exercises
  7. Section IV - Faults and Fault-Tolerant Systems
    1. Chapter 12 - Fault-Tolerant Systems
      1. 12.1 Introduction
      2. 12.2 Classification of Faults
      3. 12.3 Specification of Faults
      4. 12.4 Fault-Tolerant Systems
        1. 12.4.1 Masking Tolerance
        2. 12.4.2 Nonmasking Tolerance
        3. 12.4.3 Fail-Safe Tolerance
        4. 12.4.4 Graceful Degradation
        5. 12.4.5 Detection of Failures in Synchronous Systems
      5. 12.5 Tolerating Crash Failures
        1. 12.5.1 Double and Triple Modular Redundancy
      6. 12.6 Tolerating Omission Failures
        1. 12.6.1 Stenning’s Protocol
        2. 12.6.2 Sliding Window Protocol
        3. 12.6.3 Alternating Bit Protocol
        4. 12.6.4 How TCP Works
      7. 12.7 Concluding Remarks
      8. 12.8 Bibliographic Notes
      9. Exercises
    2. Chapter 13 - Distributed Consensus
      1. 13.1 Introduction
      2. 13.2 Consensus in Asynchronous Systems
        1. 13.2.1 Bivalent and Univalent States
      3. 13.3 Consensus in Synchronous Systems: Byzantine Generals Problem
        1. 13.3.1 Solution with No Traitor
        2. 13.3.2 Solution with Traitors: Interactive Consistency Criteria
        3. 13.3.3 Consensus with Oral Messages
          1. 13.3.3.1 Impossibility Result
          2. 13.3.3.2 OM(m) Algorithm
        4. 13.3.4 Consensus Using Signed Messages
      4. 13.4 Paxos Algorithm
        1. 13.4.1 Safety Properties
        2. 13.4.2 Liveness Properties
      5. 13.5 Failure Detectors
        1. 13.5.1 Solving Consensus Using Failure Detectors
          1. 13.5.1.1 Consensus Using P
          2. 13.5.1.2 Consensus Using S
          3. 13.5.1.3 Rationale
          4. 13.5.1.4 Implementing a Failure Detector
      6. 13.6 Concluding Remarks
      7. 13.7 Bibliographic Notes
      8. Exercises
    3. Chapter 14 - Distributed Transactions
      1. 14.1 Introduction
      2. 14.2 Classification of Transactions
        1. 14.2.1 Flat Transactions
        2. 14.2.2 Nested Transactions
        3. 14.2.3 Distributed Transactions
      3. 14.3 Implementing Transactions
      4. 14.4 Concurrency Control and Serializability
        1. 14.4.1 Testing for Serializability
        2. 14.4.2 Two-Phase Locking
        3. 14.4.3 Concurrency Control via Time Stamp Ordering
      5. 14.5 Atomic Commit Protocols
        1. 14.5.1 One-Phase Commit
        2. 14.5.2 Two-Phase Commit
        3. 14.5.3 Three-Phase Commit
      6. 14.6 Recovery from Failures
        1. 14.6.1 Stable Storage
        2. 14.6.2 Checkpointing and Rollback Recovery
        3. 14.6.3 Message Logging
      7. 14.7 Concluding Remarks
      8. 14.8 Bibliographic Notes
      9. Exercises
    4. Chapter 15 - Group Communication
      1. 15.1 Introduction
      2. 15.2 Atomic Multicast
      3. 15.3 IP Multicast
        1. 15.3.1 Reverse Path Forwarding
      4. 15.4 Application Layer Multicast
      5. 15.5 Ordered Multicasts
        1. 15.5.1 Implementing Total Order Multicast
          1. 15.5.1.1 Implementation Using a Sequencer
          2. 15.5.1.2 Distributed Implementation
        2. 15.5.2 Implementing Causal Order Multicast
      6. 15.6 Reliable Multicast
        1. 15.6.1 Scalable Reliable Multicast
        2. 15.6.2 Reliable Ordered Multicast
      7. 15.7 Open Groups
        1. 15.7.1 View-Synchronous Group Communication
      8. 15.8 Overview of Transis
      9. 15.9 Concluding Remarks
      10. 15.10 Bibliographic Notes
      11. Exercises
    5. Chapter 16 - Replicated Data Management
      1. 16.1 Introduction
        1. 16.1.1 Reliability versus Availability
      2. 16.2 Architecture of Replicated Data Management
        1. 16.2.1 Passive versus Active Replication
        2. 16.2.2 Fault-Tolerant State Machines
      3. 16.3 Data-Centric Consistency Models
        1. 16.3.1 Strict Consistency
        2. 16.3.2 Linearizability
        3. 16.3.3 Sequential Consistency
        4. 16.3.4 Causal Consistency
        5. 16.3.5 FIFO Consistency
      4. 16.4 Client-Centric Consistency Protocols
        1. 16.4.1 Eventual Consistency
        2. 16.4.2 Consistency Models for Mobile Clients
          1. 16.4.2.1 Read-After-Read Consistency
          2. 16.4.2.2 Write-After-Write Consistency
          3. 16.4.2.3 Read-After-Write Consistency
          4. 16.4.2.4 Write-After-Read Consistency
      5. 16.5 Implementation of Data-Centric Consistency Models
      6. 16.6 Quorum-Based Protocols
      7. 16.7 Replica Placement
      8. 16.8 Brewer’s CAP Theorem
      9. 16.9 Case Studies
        1. 16.9.1 Replication Management in Coda
        2. 16.9.2 Replication Management in Bayou
        3. 16.9.3 Amazon Dynamo
      10. 16.10 Concluding Remarks
      11. 16.11 Bibliographic Notes
      12. Exercises
    6. Chapter 17 - Self-Stabilizing Systems
      1. 17.1 Introduction
      2. 17.2 Theoretical Foundations
      3. 17.3 Stabilizing Mutual Exclusion
        1. 17.3.1 Mutual Exclusion on a Unidirectional Ring
        2. 17.3.2 Mutual Exclusion on a Bidirectional Array
      4. 17.4 Stabilizing Graph Coloring
      5. 17.5 Stabilizing Spanning Tree Protocol
      6. 17.6 Stabilizing Maximal Matching
      7. 17.7 Distributed Reset
      8. 17.8 Stabilizing Clock Phase Synchronization
      9. 17.9 Concluding Remarks
      10. 17.10 Bibliographic Notes
      11. Exercises
  8. Section V - Real-World Issues
    1. Chapter 18 - Distributed Discrete-Event Simulation
      1. 18.1 Introduction
        1. 18.1.1 Event-Driven Simulation
      2. 18.2 Distributed Simulation
        1. 18.2.1 Challenges
        2. 18.2.2 Correctness Issues
      3. 18.3 Conservative Simulation
      4. 18.4 Optimistic Simulation and Time Warp
        1. 18.4.1 Global Virtual Time
      5. 18.5 Concluding Remarks
      6. 18.6 Bibliographic Notes
      7. Exercises
    2. Chapter 19 - Security in Distributed Systems
      1. 19.1 Introduction
      2. 19.2 Security Mechanisms
      3. 19.3 Common Security Attacks
        1. 19.3.1 Eavesdropping
        2. 19.3.2 Denial of Service
        3. 19.3.3 Data Tampering
        4. 19.3.4 Masquerading
        5. 19.3.5 Man in the Middle
        6. 19.3.6 Malicious Software
          1. 19.3.6.1 Virus
          2. 19.3.6.2 Worms
          3. 19.3.6.3 Spyware
      4. 19.4 Encryption
      5. 19.5 Secret Key Cryptosystem
        1. 19.5.1 Confusion and Diffusion
        2. 19.5.2 DES
        3. 19.5.3 3DES
        4. 19.5.4 AES
        5. 19.5.5 One-Time Pad
        6. 19.5.6 Stream Ciphers
        7. 19.5.7 Steganography
      6. 19.6 Public Key Cryptosystems
        1. 19.6.1 Rivest–Shamir–Adleman Cryptosystem
        2. 19.6.2 ElGamal Cryptosystem
      7. 19.7 Digital Signatures
        1. 19.7.1 Signatures in Secret-Key Cryptosystems
        2. 19.7.2 Signatures in Public-Key Cryptosystems
      8. 19.8 Hashing Algorithms
        1. 19.8.1 Birthday Attack
      9. 19.9 Elliptic Curve Cryptography
      10. 19.10 Authentication Server
        1. 19.10.1 Authentication Service for Secret-Key Cryptosystems
        2. 19.10.2 Authentication Server for Public-Key Systems
      11. 19.11 Digital Certificates
      12. 19.12 Case Studies
        1. 19.12.1 Kerberos
        2. 19.12.2 Pretty Good Privacy
        3. 19.12.3 Secure Socket Layer
      13. 19.13 Virtual Private Networks and Firewalls
        1. 19.13.1 Virtual Private Network
        2. 19.13.2 Firewall
      14. 19.14 Sharing a Secret
      15. 19.15 Concluding Remarks
      16. 19.16 Bibliographic Notes
      17. Exercises
        1. Programming Exercises
    3. Chapter 20 - Sensor Networks
      1. 20.1 Vision
      2. 20.2 Architecture of Sensor Nodes
        1. 20.2.1 MICA Mote
        2. 20.2.2 ZigBee-Enabled Sensor Nodes
        3. 20.2.3 TinyOS® Operating System
      3. 20.3 Challenges in Wireless Sensor Networks
        1. 20.3.1 Energy Conservation
        2. 20.3.2 Fault Tolerance
        3. 20.3.3 Routing
        4. 20.3.4 Time Synchronization
        5. 20.3.5 Location Management
        6. 20.3.6 Middleware Design
        7. 20.3.7 Security
      4. 20.4 Routing Algorithms
        1. 20.4.1 Directed Diffusion
        2. 20.4.2 Cluster-Based Routing
          1. 20.4.2.1 LEACH
          2. 20.4.2.2 PEGASIS
        3. 20.4.3 Metadata-Based Routing: SPIN
      5. 20.5 Time Synchronization Using Reference Broadcast
        1. 20.5.1 Reference Broadcast
      6. 20.6 Localization Algorithms
        1. 20.6.1 RSSI-Based Ranging
        2. 20.6.2 Ranging Using Time Difference of Arrival
        3. 20.6.3 Anchor-Based Ranging
      7. 20.7 Security in Sensor Networks
        1. 20.7.1 SPIN for Data Security
          1. 20.7.1.1 Overview of SNEP
          2. 20.7.1.2 Overview of μTESLA
        2. 20.7.2 Attacks on Routing
          1. 20.7.2.1 Hello Flood
      8. 20.8 Applications
        1. 20.8.1 Health-Care Applications
        2. 20.8.2 Environment Monitoring and Control
        3. 20.8.3 Citizen Sensing
        4. 20.8.4 Pursuer–Evader Game
      9. 20.9 Concluding Remarks
      10. 20.10 Bibliographic Notes
      11. Exercises
        1. Programming Exercises
    4. Chapter 21 - Social and Peer-to-Peer Networks
      1. 21.1 Introduction to Social Networks
        1. 21.1.1 Milgram’s Experiment
      2. 21.2 Metrics of Social Networks
        1. 21.2.1 Clustering Coefficient
        2. 21.2.2 Diameter
      3. 21.3 Modeling Social Networks
        1. 21.3.1 Erdös–Rényi Model
        2. 21.3.2 Small-World Model
        3. 21.3.3 Power-Law Graphs
      4. 21.4 Centrality Measures in Social Networks
        1. 21.4.1 Degree Centrality
        2. 21.4.2 Closeness Centrality
        3. 21.4.3 Betweenness Centrality
      5. 21.5 Community Detection
        1. 21.5.1 Girvan–Newman Algorithm
      6. 21.6 Introduction to Peer-to-Peer Networks
      7. 21.7 First-Generation P2P Systems
        1. 21.7.1 Napster
        2. 21.7.2 Gnutella
      8. 21.8 Second-Generation P2P Systems
        1. 21.8.1 KaZaA
        2. 21.8.2 Chord
        3. 21.8.3 Content-Addressable Network
        4. 21.8.4 Pastry
      9. 21.9 Koorde and De Bruijn Graph
      10. 21.10 Skip Graph
      11. 21.11 Replication Management
      12. 21.12 BitTorrent and Free Riding
      13. 21.13 Censorship Resistance, Anonymity
      14. 21.14 Concluding Remarks
      15. 21.15 Bibliographic Notes
      16. Exercises
  9. References

Product information

  • Title: Distributed Systems, 2nd Edition
  • Author(s): Sukumar Ghosh
  • Release date: July 2014
  • Publisher(s): Chapman and Hall/CRC
  • ISBN: 9781498760058