Class notes and slides

See also a course given by Jennifer Welch in Texas A&M, Spring 1999.

This semester-long course meets once a week for a two-hours lecture; in addition, there is a weekly one-hour recitation. The notes contain 13 lectures; the last lecture included a presentation of the projects written by the students (see below). The class had approximately 30 students, approximately half of them seniors, and the rest graduate students.

The course followed a fairly aggressive schedule, and assumes that students read details in the book (after class). The description of the material in class is fairly informal, at most times; however, their written assignments were supposed to be quite formal.

In some cases, the recitations covered material not in the book. In these cases, we point to the paper(s) on which the recitation was based.

Evaluation of the students was (approximately) equally based on four homework assignments handed out during the semester, and on a written project.

Additional material can be found through the book homepage:

Also, look at the course's homepage, for project ideas and guidelines:

Order of lectures:

1. Introduction and basic message passing algorithms (notes and slides).
2. Algorithms and lower bounds for leader election in rings (notes and slides).
3. Complete last lecture, and start mutual exclusion (using Test&Set) (notes and slides).
4. Mutual exclusion using read/write registers (notes and slides).
5. Consensus in the presence of crash failures (synchronous) (notes and slides).
6. Consensus in the presence of Byzantine failures (synchronous) (notes and slides).
7. Simulations between failure types (notes and slides).
8. Impossiblility of wait-free consensus (notes and slides).
9. Wait-free simulation of fault-tolerant algorithms (notes and slides).
10. Wait-free simulations of shared-memory objects (notes and slides).
11. Wait-free atomic snapshots (notes).
12. Randomized consensus (notes).
13. Synchronizers (notes).

Notes and slides in postscript.

Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6

Lecture 7

Lecture 8

Lecture 9

Lecture 10

Lecture 11

Lecture 12

Lecture 13