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.