Distributed Computing


Spring-Summer 2016

Lecturer: Prof. Yehuda Afek

Homework 1 due April/3rd


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, Shenkar 222

       Office Hours, by appointment (email)

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



Feb 28

Models, and Introduction.

March 6

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

March 13

Leader Election, ring networks, unidirectional case

March 20

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

March 27

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

April 3

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,

April 10

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

April 17, 24

*** Pesach ***

May 1

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 8

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

Simulating Shared memory in message passing,

May 15

Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper

Moir Anderson, Lamport-87

May 22

Randomized Consensus.

May 29

Renaming, Concurrent Time Stamps,

June 5

Concurrent programming, the link list case

Time permitting











The grade weighting for the semester will be:

Home Works 


Take home exam: 


These weights are subject to change.