randomized algorithms, Byzantine agreement, choice coordination, the see-saw puzzle, the two lovers problem, the two generals problem, the too much bread problem, deadlock, dining philosophers, mutual exclusion, barrier synchronization, crash failures, Byzantine failures
To Miki,the love of my life.
Contents
1.3 Computers with Multiple Processors
1.5 Why is Synchronization Difficult?
1.7 Concurrent and Distributed Algorithms
2.1 The Too Much Bread Problem
2.6 Fourth Attempt: A Correct Solution
2.7 Communicating by Reading and Writing of Notes
3.3 A Surprising Impossibility Result
3.4 Further Explanations
3.5 Chapter Notes
3.6 Self Review
4.1 The Movie Agreement Problem
4.2 Applications
4.3 A Surprising Impossibility Result
4.4 A More General Result
4.5 An Algorithm
4.6 Further Explanations
4.7 How Many Rounds are Needed?
4.8 Chapter Notes
4.9 Self Review
5 The Fall of the Byzantine Empire
5.1 The Byzantine Generals Problem
5.2 Applications
5.3 A Surprising Result
5.4 An Algorithm
5.5 Further Explanations
5.6 Chapter Notes
5.7 Self Review
6.1 The Choice Coordination Problem
6.2 Applications
6.3 A Randomized Algorithm
6.4 Further Explanations
6.5 A Simple Deterministic Algorithm
6.6 Perfectionism, It Seems, Does Not Pay!
6.7 Chapter Notes
6.8 Self Review
7.1 The Dining Philosophers Problem
7.2 Applications
7.3 Deadlock Prevention: The Total Order Technique
7.4 Hold and Wait Strategy: The LR Algorithm
