Efnisyfirlit

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