Distributed Algorithms
Lecture Notes
Lectures 15, 21, and 22 were given by guest lecturer Dr. Victor Luchangco of Sun Microsystems, and are used with permission.
SES # |
TOPICS |
LECTURE NOTES |
1 |
Course overview. Synchronous networks. Leader election in synchronous ring networks. |
(PDF) |
2 |
Leader election in rings. Basic computational tasks in general synchronous networks: leader election. Breadth-first search. Broadcast and convergecast. Shortest paths. |
(PDF) |
3 |
Spanning trees. Minimum spanning trees. |
(PDF) |
4 |
Fault-tolerant consensus. Link failures: the two generals problem. Process failures (stopping, Byzantine). Algorithms for agreement with stopping and Byzantine failures. Exponential information gathering. |
(PDF) |
5 |
Number-of-processor bounds for Byzantine agreement. Weak Byzantine agreement. Time bounds for consensus problems. |
(PDF) |
6 |
k-set-agreement. Approximate agreement. Distributed commit. |
(PDF) |
7 |
Asynchronous distributed computing. Formal modeling of asynchronous systems using interacting state machines (I/O automata). Proving correctness of distributed algorithms. |
(PDF) |
8 |
Non-fault-tolerant algorithms for asynchronous networks. Leader election, breadth-first search, shortest paths, broadcast and convergecast. |
(PDF) |
9 |
Spanning trees. Gallager et al. minimum spanning trees. |
(PDF) |
10 |
Synchronizers. Synchronizer applications. Synchronous vs. asynchronous distributed systems. |
(PDF) |
11 |
Time, clocks, and the ordering of events. State-machine simulation. Vector timestamps. |
(PDF) |
12 |
Stable property detection. Distributed termination. Global snapshots. Deadlock detection. |
(PDF) |
13 |
Asynchronous shared-memory systems. The mutual exclusion problem. Mutual exclusion algorithms. |
(PDF) |
14 |
More mutual exclusion algorithms. Bounds on shared memory for mutual exclusion. Resource allocation. The Dining Philosophers problem. |
(PDF) |
15 |
Shared-memory multiprocessors. Contention, caching, locality. Practical mutual exclusion algorithms. Reading/writing locks. |
(PDF) |
16 |
Impossibility of consensus in asynchronous, fault-prone, shared-memory systems. |
(PDF) |
17 |
Atomic objects |
(PDF) |
18 |
Atomic snapshot algorithms. Atomic read/write register algorithms. |
(PDF) |
19 |
List algorithms: locking algorithms, optimistic algorithms, lock-free algorithms, lazy algorithms. |
(PDF) |
20 |
Transactional memory: obstruction-free and lock-based implementations. |
(PDF) |
21 |
Wait-free computability. The wait-free consensus hierarchy. |
(PDF) |
22 |
Wait-free vs. f-fault-tolerant atomic objects. Boosting fault-tolerance. |
(PDF) |
23 |
Asynchronous network model vs. asynchronous shared-memory model. Impossibility of consensus in asynchronous networks. Failure detectors and consensus. Paxos consensus algorithm. |
(PDF) |
24 |
Self-stabilizing algorithms |
(PDF) |
25 |
Timing-based systems. Modeling and verification. Timing-based algorithms for mutual exclusion and consensus. Clock synchronization. |
(PDF) |
Assignments
ASSN # |
ASSIGNMENTS |
NOTES |
1 |
Part A (PDF) Part B (PDF) |
|
2 |
Part A (PDF) Part B (PDF) |
|
3 |
Part A (PDF) Part B (PDF) |
Part B, Problem 4: The question asks for a description of the best algorithm you can devise that solves the k-pseudo-session problem and its worst case time complexity. The time complexity is measured according to T(A) as defined on p. 557 of the textbook. |
4 |
Part A (PDF) Part B (PDF) |
|
5 |
Part A (PDF) Part B (PDF) |
|
6 |
Part A (PDF) Part B (PDF) |
Part A: In an invisible read, the transaction does not write any control information into the shared memory to inform the other transactions on possible read/write conflicts. Hence note that in the context of obstruction-free STM (software transactional memory), invisible reads require a read validation step. |
7 |
(PDF) |
|
Tools
The Tempo Language User Guide and Reference Manual (PDF - 1.0MB) (Courtesy of Nancy Lynch, Stephen J. Garland, Dilsun Kaynar, Laurent Michel, and Alex Shvartsman. Used with permission.) Section 3 provides some toy examples of TIOA algorithms implemented in Tempo.