책 이미지
책 정보
· 분류 : 외국도서 > 컴퓨터 > 컴퓨터 엔지니어링
· ISBN : 9781466552975
· 쪽수 : 560쪽
목차
Preface
Acknowledgments
Author
Section I: Background Materials
Introduction
What Is a Distributed System?
Why Distributed Systems
Examples of Distributed Systems
Important Issues in Distributed Systems
Common Subproblems
Implementing a Distributed System
Parallel versus Distributed Systems
Bibliographic Notes
Exercises
Interprocess Communication: An Overview
Introduction
Processes and Threads
Client?Server Model
Middleware
Network Protocols
Ethernet
Wireless Networks
OSI Model
IP
Transport Layer Protocols
Interprocess Communication Using Sockets
Naming
Domain Name Service
Naming Service for Mobile Clients
Remote Procedure Call
Implementing RPC
Sun ONC/RPC
Remote Method Invocation
Messages
Transient and Persistent Messages
Streams
Web Services
Event Notification
Virtualization: Cloud Computing
Classification of Cloud Services
MapReduce
Hadoop
Mobile Agents
Basic Group Communication Services
Concluding Remarks
Bibliographic Notes
Exercises
Section II: Foundational Topics
Models for Communication
Need for a Model
Message-Passing Model for Interprocess Communication
Process Actions
Channels
Synchronous versus Asynchronous Systems
Real-Time Systems
Shared Variables
Linda
Modeling Mobile Agents
Relationship among Models
Strong and Weak Models
Implementing a FIFO Channel Using a Non-FIFO Channel
Implementing Message Passing Using Shared Memory
Implementing Shared Memory Using Message Passing
Impossibility Result with Channels
Classification Based on Special Properties
Reactive versus Transformational Systems
Named versus Anonymous Systems
Complexity Measures
Concluding Remarks
Bibliographic Notes
Exercises
Representing Distributed Algorithms: Syntax and Semantics
Introduction
Guarded Actions
Nondeterminism
Atomic Operations
Fairness
Central versus Distributed Schedulers
Concluding Remarks
Bibliographic Notes
Exercises
Program Correctness
Introduction
Correctness Criteria
Safety Properties
Liveness Properties
Correctness Proofs
Quick Review of Propositional Logic
Brief Overview of Predicate Logic
Assertional Reasoning: Proving Safety Properties
Proving Liveness Properties Using Well-Founded Sets
Programming Logic
Predicate Transformers
Concluding Remarks
Bibliographic Notes
Exercises
Time in a Distributed System
Introduction
Physical Time
Sequential and Concurrent Events
Logical Clocks
Vector Clocks
Physical Clock Synchronization
Preliminary Definitions
Clock Reading Error
Algorithms for Internal Synchronization
Algorithms for External Synchronization
Concluding Remarks
Bibliographic Notes
Exercises
Section III: Important Paradigms
Mutual Exclusion
Introduction
Solutions on Message-Passing Systems
Lamport’s Solution
Ricart?Agrawala’s Solution
Maekawa’s Solution
Token-Passing Algorithms
Suzuki?Kasami Algorithm
Raymond’s Algorithm
Solutions on the Shared-Memory Model
Peterson’s Algorithm
Mutual Exclusion Using Special Instructions
Solution Using Test-and-Set
Solution Using Load-Linked and Store-Conditional
Group Mutual Exclusion
Concluding Remarks
Bibliographic Notes
Exercises
Distributed Snapshot
Introduction
Properties of Consistent Snapshots
Cuts and Consistent Cuts
Chandy?Lamport Algorithm
Two Examples
Lai?Yang Algorithm
Distributed Debugging
Constructing the State Lattice
Evaluating Predicates
Concluding Remarks
Bibliographic Notes
Exercises
Global State Collection
Introduction
Elementary Algorithm for All-to-All Broadcasting
Termination-Detection Algorithms
Dijkstra?Scholten Algorithm
Termination Detection on a Unidirectional Ring
Credit-Recovery Algorithm for Termination Detection
Wave Algorithms
Propagation of Information with Feedback
Distributed Deadlock Detection
Resource Deadlock and Communication Deadlock
Detection of Resource Deadlock
Detection of Communication Deadlock
Concluding Remarks
Bibliographic Notes
Exercises
Graph Algorithms
Introduction
Routing Algorithms
Computation of Shortest Path
Distance-Vector Routing
Link-State Routing
Interval Routing
Prefix Routing
Graph Traversal
Spanning Tree Construction
Tarry’s Graph Traversal Algorithm
Minimum Spanning Tree Construction
Graph Coloring
(D + 1)-Coloring Algorithm
Cole?Vishkin Reduction Algorithm for Tree Coloring
Maximal Independent Set: Luby’s Algorithm
Concluding Remarks
Bibliographic Notes
Exercises
Coordination Algorithms
Introduction
Leader Election
Bully Algorithm
Maxima Finding on a Ring
Election in Arbitrary Networks
Election in Anonymous Networks
Synchronizers
ABD Synchronizer
Awerbuch’s Synchronizers
Concluding Remarks
Bibliographic Notes
Exercises
Section IV: Faults and Fault-Tolerant Systems
Fault-Tolerant Systems
Introduction
Classification of Faults
Specification of Faults
Fault-Tolerant Systems
Masking Tolerance
Nonmasking Tolerance
Fail-Safe Tolerance
Graceful Degradation
Detection of Failures in Synchronous Systems
Tolerating Crash Failures
Double and Triple Modular Redundancy
Tolerating Omission Failures
Stenning’s Protocol
Sliding Window Protocol
Alternating Bit Protocol
How TCP Works
Concluding Remarks
Bibliographic Notes
Exercises
Distributed Consensus
Introduction
Consensus in Asynchronous Systems
Bivalent and Univalent States
Consensus in Synchronous Systems: Byzantine Generals Problem
Solution with No Traitor
Solution with Traitors: Interactive Consistency Criteria
Consensus with Oral Messages
Consensus Using Signed Messages
Paxos Algorithm
Safety Properties
Liveness Properties
Failure Detectors
Solving Consensus Using Failure Detectors
Concluding Remarks
Bibliographic Notes
Exercises
Distributed Transactions
Introduction
Classification of Transactions
Flat Transactions
Nested Transactions
Distributed Transactions
Implementing Transactions
Concurrency Control and Serializability
Testing for Serializability
Two-Phase Locking
Concurrency Control via Time Stamp Ordering
Atomic Commit Protocols
One-Phase Commit
Two-Phase Commit
Three-Phase Commit
Recovery from Failures
Stable Storage
Checkpointing and Rollback Recovery
Message Logging
Concluding Remarks
Bibliographic Notes
Exercises
Group Communication
Introduction
Atomic Multicast
IP Multicast
Reverse Path Forwarding
Application Layer Multicast
Ordered Multicasts
Implementing Total Order Multicast
Implementing Causal Order Multicast
Reliable Multicast
Scalable Reliable Multicast
Reliable Ordered Multicast
Open Groups
View-Synchronous Group Communication
Overview of Transis
Concluding Remarks
Bibliographic Notes
Exercises
Replicated Data Management
Introduction
Reliability versus Availability
Architecture of Replicated Data Management
Passive versus Active Replication
Fault-Tolerant State Machines
Data-Centric Consistency Models
Strict Consistency
Linearizability
Sequential Consistency
Causal Consistency
FIFO Consistency
Client-Centric Consistency Protocols
Eventual Consistency
Consistency Models for Mobile Clients
Implementation of Data-Centric Consistency Models
Quorum-Based Protocols
Replica Placement
Brewer’s CA P Theorem
Case Studies
Replication Management in Coda
Replication Management in Bayou
Amazon Dynamo
Concluding Remarks
Bibliographic Notes
Exercises
Self-Stabilizing Systems
Introduction
Theoretical Foundations
Stabilizing Mutual Exclusion
Mutual Exclusion on a Unidirectional Ring
Mutual Exclusion on a Bidirectional Array
Stabilizing Graph Coloring
Stabilizing Spanning Tree Protocol
Stabilizing Maximal Matching 377
Distributed Reset
Stabilizing Clock Phase Synchronization
Concluding Remarks
Bibliographic Notes
Exercises
Section V: Real-World Issues
Distributed Discrete-Event Simulation
Introduction
Event-Driven Simulation
Distributed Simulation
Challenges
Correctness Issues
Conservative Simulation
Optimistic Simulation and Time Warp
Global Virtual Time
Concluding Remarks
Bibliographic Notes
Exercises
Security in Distributed Systems
Introduction
Security Mechanisms
Common Security Attacks
Eavesdropping
Denial of Service
Data Tampering
Masquerading
Man in the Middle
Malicious Software
Encryption
Secret Key Cryptosystem
Confusion and Diffusion
DES
AES
One-Time Pad
Stream Ciphers
Steganography
Public Key Cryptosystems
Rivest?Shamir?Adleman Cryptosystem
ElGamal Cryptosystem
Digital Signatures
Signatures in Secret-Key Cryptosystems
Signatures in Public-Key Cryptosystems
Hashing Algorithms
Birthday Attack
Elliptic Curve Cryptography
Authentication Server
Authentication Service for Secret-Key Cryptosystems
Authentication Server for Public-Key Systems
Digital Certificates
Case Studies
Kerberos
Pretty Good Privacy
Secure Socket Layer
Virtual Private Networks and Firewalls
Virtual Private Network
Firewall
Sharing a Secret
Concluding Remarks
Bibliographic Notes
Exercises
Sensor Networks
Vision
Architecture of Sensor Nodes
MICA Mote
ZigBee-Enabled Sensor Nodes
TinyOS® Operating System
Challenges in Wireless Sensor Networks
Energy Conservation
Fault Tolerance
Routing
Time Synchronization
Location Management
Middleware Design
Security
Routing Algorithms
Directed Diffusion
Cluster-Based Routing
Metadata-Based Routing: SPIN
Time Synchronization Using Reference Broadcast
Reference Broadcast
Localization Algorithms
RSSI-Based Ranging
Ranging Using Time Difference of Arrival
Anchor-Based Ranging
Security in Sensor Networks
SPIN for Data Security
Attacks on Routing
Applications
Health-Care Applications
Environment Monitoring and Control
Citizen Sensing
Pursuer?Evader Game
Concluding Remarks
Bibliographic Notes
Exercises
Social and Peer-to-Peer Networks
Introduction to Social Networks
Milgram’s Experiment
Metrics of Social Networks
Clustering Coefficient
Diameter
Modeling Social Networks
Erdos?Renyi Model
Small-World Model
Power-Law Graphs
Centrality Measures in Social Networks
Degree Centrality
Closeness Centrality
Betweenness Centrality
Community Detection
Girvan?Newman Algorithm
Introduction to Peer-to-Peer Networks
First -Generation P2P Systems
Napster
Gnutella
Second-Generation P2P Systems
KaZaA
Chord
Content-Addressable Network
Pastry
Koorde and De Bruijn Graph
Skip Graph
Replication Management
BitTorrent and Free Riding
Censorship Resistance, Anonymity
Concluding Remarks
Bibliographic Notes
Exercises
References
Index
