Distributed Computing


Spring-Summer 2015

Lecturer: Prof. Yehuda Afek


Homework 1.

Homework 2. Due April 26 2015

Homework 3. Due May 31st 2015

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, Schreiber 007

       Office Hours, by appointment (email)

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



March 8

Models, and Introduction.

March 15

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

March 22

Leader Election, ring networks, unidirectional case

March 29

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

April 5

*** Pesach ***

April 12

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

April 19

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 26

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

May 3

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 10

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

Simulating Shared memory in message passing,

May 17

Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper

Moir Anderson, Lamport-87

May 24

*** Shavuot ***

May 31

Randomized Consensus.

June 7

Renaming, Concurrent Time Stamps,

June 14

To be announced

June 21

Time permitting

Concurrent programming, the link list case







The grade weighting for the semester will be:

Home Works 


Take home exam: 


These weights are subject to change.





2014 Course page


2013 Course page