Class notes and slides

for

Distributed Algorithms

Lecturer: Hagit Attiya

Teaching assistant: Arie (Leonid) Fouren

Supplement to Distributed Computing: Fundamentals, Simulations and Advanced Topics
by Attiya and Welch

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 pdf.


Lecture 1

note page 1
note page 2
note page 3
note page 4
note page 5
note page 6

Lecture 2

note page 7
note page 8
note page 9
note page 10
note page 11
note page 12
note page 13
note page 14

Lecture 3

note page 15
note page 16
note page 17
note page 18
note page 19
note page 20
note page 21
note page 22
note page 23

Lecture 4

note page 24
note page 25
note page 26
note page 27
note page 28
note page 29
note page 30
note page 31
note page 32

Lecture 5

note page 33
note page 34
note page 35
note page 36
note page 37
note page 38
note page 39

Lecture 6

note page 40
note page 41
note page 42
note page 43
note page 44
note page 45
note page 46
note page 47

Lecture 7

note page 48
note page 49
note page 50
note page 51
note page 52

Lecture 8

note page 53
note page 54
note page 55
note page 56
note page 57

Lecture 9

note page 58
note page 59
note page 60
note page 61
note page 62

Lecture 10

note page 63
note page 64
note page 65
note page 66

Lecture 11

note page 67
note page 68

Lecture 12

note page 69
note page 70

Lecture 13

note page 71