Distributed Systems: An Algorithmic Approach

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