Principles of Distributed Systems

to 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.