Reading list: Everything in the notes Textbook: Chapter 1: all Chapter 2: 2.1 -- 2.4 Chapter 3: all Chapter 4: all Chapter 5: all except 5.7 Chapter 6: 6.1-6.6, 6.10, 6.11, 6.13 6.14 Chapter 7: 7.1 to 7.7 Chapter 8: 8.1 to 8.4 ---------------------------------------------------------- Overview: concepts, issues in distributed OS, communication model: message passing, RPC Theoretical Foundations: Logical clock, vector clock, happened before relation: what is it, how to maintain the clock, what is the major property of the clocks. Application of the clocks: causal ordering of messages two algorithms Global state: consistent global state, (chandy-lamport) algorithm to record consistent global state Huang's termination detection algorithm Mutual exclusion: What is it? How do we address this problem in a uniprocess system/shared memory system? distributed mutual exclusion: performance metrics: # of messages per CS invocation, sychronization delay response time, throughput Lamport's algorithm, Suzuki-Kasami Broadcast Algorithm Raymond's Tree-Based Algorithm Deadlock: What is it? How do we address this problem in a uniprocess system? request models, WFG, GRG, necessary and sufficient conditions methods to deal with deadlocks distributed deadlock detection: Why not prevention, avoidance? centralized deadlock detection: Ho-Ramamoorthy Algorithm: Two-Phase Ho-Ramamoorthy Algorithm: One-Phase distributed deadlock detection: path pushing edge chasing diffusion global state detection based. Agreement Protocols: What is it? Byzantine agreement, consensus, interactive consistency Lamport's algorithm, Dolev et alia Algorithm