Distributed systems: An algorithmic appr oach

Offering a balance of theory and practice, Distributed Systems shows how algorithmic aspects of distributed computing relate to the real world and addresses fundamental issues in distributed systems. This book provides coverage of new topics in the field, including sensor networks and peer-to-peer networks, and presents background and foundational material as well as important paradigms that play a pivotal role in the design of many distributed systems. The author introduces faults and various techniques for fault tolerance. With a set of exercises featured in each chapter, this text emphasizes underlying theory and real world issues to provide readers with a thorough understanding of this subject.

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 Bibliogra