Description
Book Synopsisto Distributed Systems.- Distributed Systems versus Parallel Systems.- Partial Orders.- Notation.- Overview of the book.- Exercises.- Bibliographic Remarks.- 1 Time.- 1.1 Introduction.- 1.2 Model of a distributed system.- 1.3 Logical Clocks.- 1.4 Vector Clocks.- 1.5 Direct Dependency Clocks.- 1.6 Higher Dimensional Clocks.- 1.7 Exercises.- 1.8 Bibliographic Remarks.- 2 Mutual Exclusion.- 2.1 Introduction.- 2.2 Problem.- 2.3 Lamport's Algorithm.- 2.4 Ricart and Agrawala's Algorithm.- 2.5 Centralized Algorithm.- 2.6 Dijkstra's Self-stabilizing Algorithm.- 2.7 Exercises.- 2.8 Bibliographic Remarks.- 3 Global State.- 3.1 Introduction.- 3.2 Consistent Cuts.- 3.3 Global Snapshots of Processes.- 3.4 Global Snapshots of Processes and Channels.- 3.5 Global Snapshots for non-FIFO channels.- 3.6 Applications of Global Snapshot Algorithms.- 3.7 Exercises.- 3.8 Bibliographic Remarks.- 4 Possible Global Predicates.- 4.1 Introduction.- 4.2 Possibility of a Global Predicate.- 4.3 NP-Completeness of Global Predicate Detection.- 4.4 Linear Predicates.- 4.5 Semi-Linear Predicates.- 4.6 Exercises.- 4.7 Bibliographic Remarks.- 5 Conjunctive Possible Global Predicates.- 5.1 Introduction.- 5.2 Weak Conjunctive Predicates.- 5.3 A Vector Clock based Centralized Algorithm for WCP.- 5.4 A Direct Dependence based Centralized Algorithm for WCP.- 5.5 A Vector Clock based Distributed Algorithm for WCP.- 5.6 A Centralized Algorithm for Generalized Conjunctive Predicates.- 5.7 A Vector Clock based Distributed GCP Detection Algorithm.- 5.8 Exercises.- 5.9 Bibliographic Remarks.- 6 Relational Possible Global Predicates.- 6.1 Introduction.- 6.2 Relational Predicate with Two Integer Variables.- 6.3 Relational predicates with N Boolean Variables.- 6.4 Bounded Sum Predicates.- 6.5 Exercises.- 6.6Bibliographic Remarks.- 7 Inevitable Global Predicates.- 7.1 Introduction.- 7.2 Global Sequence.- 7.3 Logic for Global Predicates.- 7.4 Strong Conjunctive Predicates.- 7.5 Algorithms for Detecting SCP.- 7.6 Exercises.- 7.7 Bibliographic Remarks.- 8 Control Flow Predicates.- 8.1 Introduction.- 8.2 LRDAG Logic.- 8.3 Examples.- 8.4 Decentralized Detection Algorithm.- 8.5 Exercises.- 8.6 Bibliographic Remarks.- 9 Order.- 9.1 Introduction.- 9.2 Relationship among Message Orderings.- 9.3 FIFO Ordering of Messages.- 9.4 Causal Ordering Of Messages.- 9.5 Synchronous Ordering of Messages.- 9.6 Exercises.- 9.7 Bibliographic Remarks.- 10 Computation.- 10.1 Introduction.- 10.2 Global Functions.- 10.3 Repeated Computation.- 10.4 Exercises.- 10.5 Bibliographic Remarks.- References.
Table of ContentsList of Figures. Preface. 0. Introduction to Distributed Systems. 1. Time. 2. Mutual Exclusion. 3. Global State. 4. Possible Global Predicates. 5. Conjunctive Possible Global Predicates. 6. Relational Possible Global Predicates. 7. Inevitable Global Predicates. 8. Control Flow Predicates. 9. Order. 10. Computation. References. Index.
