Distributed Systems: An Algorithmic Approach(Chapman & Hall/CRC Computer and Information Science Series)

Most applications in distributed computing center around a set of common subproblems. Distributed Systems: An Algorithmic Approach presents the algorithmic issues and necessary background theory that are needed to properly understand these challenges.

Achieving a balance between theory and practice, this book bridges the gap between theoreticians and practitioners. With a set of exercises featured in each chapter, the book begins with background information that contains various interprocess communication techniques and middleware services, followed by foundational topics that cover system models, correctness criteria, and proof techniques. The book also presents numerous important paradigms in distributed systems, including logical clocks, distributed snapshots, deadlock detection, termination detection, election, and several graph algorithms. The author then addresses failures and fault-tolerance techniques in diverse applications, such as consensus, transactions, group communication, replicated data management, and self-stabilization. He concludes with an exploration of real-world issues, including distributed discrete-event simulation and security, sensor networks, and peer-to-peer networks.
By covering foundational matters of distributed systems and their relationships to real-world applications, Distributed Systems provides insight into common distributed computing subproblems,

Table of Contents:
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 vs. Distributed Systems
Bibliographic Notes
INTERPROCESS COMMUNICATION: AN OVERVIEW Introduction
Network Protocols
Naming
Remote Procedure Call
Remote Method Invocation
Web Services
Messages
Event Notification
CORBA
Mobile Agents
Basic Group Communication Services
Concluding Remarks
Bibliographic Notes
Exercises
FOUNDATIONAL TOPICS
MODELS OF COMMUNICATION
The Need for a Model
A Message-Passing Model for Interprocess Communication
Shared Variables
Modeling Mobile Agents
Relationship among Models
Classification Based on Special Properties
Complexity Measures
Concluding Remarks
Bibliographic Notes
REPRESENTING DISTRIBUTED ALGORITHMS: SYNTAX AND SEMANTICS
Introduction
Guarded Actions
Nondeterminism
Atomic Operations
Fairness
Central vs. Distributed Schedulers
Concluding Remarks
Bibliographic Notes
PROGRAM CORRECTNESS
Introduction
Correctness Criteria
Correctness Proofs
Predicate Logic
Assertional Reasoning: Proving Safety Properties
Proving Liveness Properties Using Well-Founded Sets
Programming Logic
Predicate Transformers
Concluding Remarks
Bibliographic Notes
TIME IN A DISTRIBUTED SYSTEM
Introduction
Logical Clocks
Vector Clocks
Physical Clock Synchronization
Concluding Remarks
Bibliographic Notes
IMPORTANT PARADIGMS
MUTUAL EXCLUSION
Introduction
Solution Using Message Passing
Token-Passing Algorithms
Solutions on the Shared-Memory Model
Mutual Exclusion Using Special Instructions
The Group Mutual Exclusion Problem
Concluding Remarks
Bibliographic Notes
DISTRIBUTED SNAPSHOT
Introduction
Properties of Consistent Snapshots
The Chandy–Lamport Algorithm
The Lai–Yang Algorithm
Concluding Remarks
Bibliographic Notes
GLOBAL STATE COLLECTION
Introduction
An Elementary Algorithm for Broadcasting
Termination Detection Algorithms
Distributed Deadlock Detection
Concluding Remarks
Bibliographic Notes
GRAPH ALGORITHMS
Introduction
Routing Algorithms
Graph Traversal
Graph Coloring
Concluding Remarks
Bibliographic Notes
COORDINATION ALGORITHMS
Introduction
Leader Election
Synchronizers
Concluding Remarks
Bibliographic Notes
Exercises
FAULTS AND FAULT-TOLERANT SYSTEMS
FAULT=TOLERANT SYSTEMS
Introduction
Classification of Faults
Specification of Faults
Fault-Tolerant Systems
Tolerating Crash Failures
Tolerating Omission Failures
Concluding Remarks
Bibliographic Notes
Exercises
DISTRIBUTED CONSENSUS
Introduction
Consensus in Asynchronous Systems
Consensus in Synchronous Systems: Byzantine Generals Problem
Failure Detectors
Concluding Remarks
Bibliographic Notes
Exercises
DISTRIBUTED TRANSACTIONS
Introduction
Classification of Transactions
Implementing Transactions
Concurrency Control and Serializability
Atomic Commit Protocols
Recovery from Failures
Concluding Remarks
Bibliographic Notes
Exercises
GROUP COMMUNICATION
Introduction
Atomic Multicast
IP Multicast
Application Layer Multicast
Ordered Multicast
Reliable Ordered Multicast
Open Groups
An Overview of Transis
Concluding Remarks
Bibliographic Notes
Exercises
REPLICATED DATA MANAGEMENT
Introduction
Architecture of Replicated Data Management
Data-Centric Consistency Models
Client-Centric Consistency Models
Implementation of Data-Centric Consistency Models
Replica Placement
Case Studies
Concluding Remarks
Bibliographic Notes
Exercises
SELF-STABILIZING SYSTEMS
Introduction
Theoretical Foundations
Stabilizing Mutual Exclusion
Stabilizing Graph Coloring
Stabilizing Spanning Tree Protocol
Distributed Reset
Stabilizing Clock Synchronization
Concluding Remarks
Bibliographic Notes
Exercises
REAL WORLD ISSUES
DISTRIBUTED DISCRETE-EVENT SIMULATION
Introduction
Distribution Simulation
Conservative Simulation
Optimistic Simulation and Time Warp
Concluding Remarks
Bibliographic Notes
Exercises
SECURITY IN DISTRIBUTED SYSTEMS
Introduction
Security Mechanisms
Common Security Attacks
Encryption
Secret-Key Cryptosystem
Public-Key Cryptosystems
Digital Signatures
Hashing Algorithms
Elliptic Curve Cryptography
Authentication Server
Digital Certificates
Case Studies
Virtual Private Networks (VPN) and Firewalls
Sharing a Secret
Concluding Remarks
Bibliographic Notes
Exercises
SENSOR NETWORKS
The Vision
The Architecture of a Sensor Node
The Challenges in Wireless Sensor Networks
Routing Algorithms
Time Synchronization Using Reference Broadcast
Localization Algorithms
Security in Sensor Networks
Sample Application: Pursuer–Evader Games
Concluding Remarks
Bibliographic Notes
Exercises
PEER-TO-PEER NETWORKS
Introduction
The First-Generation P2P Systems
The Second-Generation P2P Systems
Koorde and De Bruijn Graph
The Small-World Phenomemon
Skip Graph
Replication Management
Free Riders and Bit Torrent
Censorship Resistance, Anonymity, and Ethical Issues
Concluding Remarks
Bibliographic Notes
BIBLIOGRAPHY
INDEX