List of Figures
1.3 A process with four threads
2.1 Interface for accessing the critical section
2.2 A program to test mutual exclusion
2.3 An attempt that violates mutual exclusion
2.4 An attempt that can deadlock
2.5 An attempt with strict alternation
2.6 Peterson’s algorithm for mutual exclusion
2.7 Lamport’s bakery algorithm
2.8 TestAndSet hardware instruction
2.9 Mutual exclusion using TestAndSet
2.10 Semantics of swap operation
3.3 A shared buffer implemented with a circular array
3.4 Bounded buffer using semaphores
3.5 Producer-consumer algorithm using semaphores
3.6 Reader-writer algorithm using semaphores
3.7 The dining philosopher problem
3.10 Dining philosopher using semaphores
3.11 A pictorial view of a Java monitor
3.13 Dining philosopher using monitors
4.1 Concurrent histories illustrating sequential consistency
4.2 Sequential consistency does not satisfy locality
4.3 Summary of consistency conditions
5.1 Safe and unsafe read-write registers
5.2 Concurrent histories illustrating regularity
5.3 Atomic and nonatomic registers
5.4 Construction of a regular boolean register
5.5 Construction of a multivalued register
5.6 Construction of a multireader register
5.7 Construction of a multiwriter register
5.8 Lock-free atomic snapshot algorithm
5.10 Impossibility of wait-free consensus with atomic read-write registers
5.12 Consensus using TestAndSet object
5.14 Consensus using CompSwap object
5.15 Load-Linked and Store-Conditional object
6.11 A name service implementation
7.1 An example of topology of a distributed system
7.2 A simple distributed program with two processes
7.3 A run in the happened-before model
7.6 The VCLinker class that extends the Linker class
7.7 A sample execution of the vector clock algorithm
7.8 A direct-dependency clock algorithm
7.9 A sample execution of the direct-dependency clock algorithm
7.10 The matrix clock algorithm
8.1 Testing a lock implementation
8.4 A centralized mutual exclusion algorithm
8.5 Lamport’s mutual exclusion algorithm
8.6 Ricart and Agrawala’s algorithm
8.8 An algorithm for dining philosopher problem
8.9 A token ring algorithm for the mutual exclusion problem
9.1 Consistent and inconsistent cuts
9.2 Classification of messages
9.3 Chandy and Lamport’s snapshot algorithm
9.4 Linker extended for use with SenderCamera
9.5 A global snapshot algorithm based on sender recording
9.6 Invocation of the global snapshot algorithm
10.1 WCP (weak conjunctive predicate) detection algorithm—checker process
10.2 Circulating token with vector clock
10.3 An application that runs circulating token with a sensor
10.4 Monitor process algorithm at Pi
10.5 Token-based WCP detection algorithm
11.1 A diffusing computation for the shortest path
11.2 Interface for a termination detection algorithm
11.3 Termination detection algorithm
11.4 A diffusing computation for the shortest path with termination
11.5 Termination detection by token traversal
12.1 A FIFO computation that is not causally ordered
12.2 An algorithm for causal ordering of messages at Pi
12.3 Structure of a causal message
12.4 CausalLinker for causal ordering of messages
12.6 A computation that is synchronously ordered
12.7 A computation that is not synchronously ordered
12.8 The algorithm at Pi for synchronous ordering of messages
12.9 The algorithm for synchronous ordering of messages
13.1 The leader election algorithm
13.2 Configurations for the worst case (a) and the best case (b)
13.3 A spanning tree construction algorithm
13.6 Algorithm for computing a global function
14.1 Algorithm for the simple synchronizer at Pj
14.2 Implementation of the simple synchronizer
14.3 An algorithm that generates a tree on an asynchronous network
14.4 BFS tree algorithm using a synchronizer
15.1 (a) Commutativity of disjoint events; (b) asynchrony of messages
15.2 (a) Case 1: proc(e) ≠ proc(f); (b) case 2: proc(e) = proc(f)
15.3 Algorithm at Pi for consensus under crash failures
15.4 Consensus in a synchronous environment
15.6 An algorithm for Byzantine General Agreement
16.1 Algorithm for the coordinator of the two-phase commit protocol
16.2 Algorithm for the participants in the two-phase commit protocol
17.1 An example of the domino effect
17.3 A distributed computation
17.4 Formal description of the fault-tolerant vector clock
17.5 Formal description of the version end-table mechanism
17.6 An optimistic protocol for asynchronous recovery
18.1 K-state self-stabilizing algorithm
18.2 A move by the bottom machine in the K-state algorithm
18.3 A move by a normal machine in the K-state algorithm
18.4 Self-stabilizing algorithm for mutual exclusion in a ring for the bottom machine
18.5 Self-stabilizing algorithm for mutual exclusion in a ring for a normal machine
18.6 Self-stabilizing algorithm for (BFS) spanning tree
18.7 Self-stabilizing spanning tree algorithm for the root
18.8 Self-stabilizing spanning tree algorithm for nonroot nodes