Distributed Computing


Spring-Summer 2017

Lecturer: Prof. Yehuda Afek


HomeWork1 Due April 2

Limor's class notes (from 2008/9). Week 1-7, week 8-13.

(in some of the weeks we will study different material than in Limor's notes)

Administrative Information

       Lectures: Sunday 16:10-19:00, Dan David 201

       Office Hours, by appointment (email)

Course Topics and Schedule (Tentative, subject to change !! )



March 19

Models, and Introduction.

March 26

Broadcast and Echo Termination Detection, Snapshots, Synchronizers Snapshot paper pdf

April 2

Leader Election, ring networks, unidirectional case

** Pesah **

April 23

Leader Election Algorithms and Spanning tree algorithms (general topology networks)

April 30

Computing the maximal independent set, rings and general graphs, upper and lower bounds

May 7

Data link protocols, the sequence transmition problem and

End-to-End protocols and another pdf, Eventually connected end-to-end STP,

The consensus problem. Algorithms and lower bounds,

May 14

The phase king protocol of Berman and Garay, The shared memory model, Safe, Regular and Atomic Registers,

May 21

Impossibility of Consensus in Wait-free shared memory. Impossibility with one faulty processor.

the shared memory hierarchy and universal constructions. Atomic Snapshots of shared memories, Immediate snap-shots,

May 28

The consensus problem, and its impossibility in asynchronous networks with one faulty processor.

Simulating Shared memory in message passing,

June 4

Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper

Moir Anderson, Lamport-87

June 11

Randomized Consensus.

June 18

Renaming, Concurrent Time Stamps,

June 25

Concurrent programming, the link list case

Time permitting




The grade weighting for the semester will be:

Home Works: 


Final Project: 


These weights are subject to change.