Distributed Computing


Spring-Summer 2011

Lecturer: Prof. Yehuda Afek

Pre exam questions, 4 or 3 of these questions will be part of the exam

Homework #4: Due Jan 5 (in my mail box, 2nd floor opposite the elevator)

Homework #3: Due May 22

Homework #2: Due April 13 (last day before Pesah)

Homework #1: Due March 13


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

Administrative Information

       Lectures: Sunday 17:10-20:00, Schreiber 007

       Office Hours, by appointment (email) Sunday 16:00-17:00

Course Topics and Schedule (tentative, subject to change)



Feb 20

Models, and Introduction. Guest teacher Prof. Gadi Taubenfeld: The mutual exclusion problem

Feb 27

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

March 6

Leader Election, ring networks, unidirectional case

March 13

Leader Election Algorithms and Spanning tree algorithms

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

April 10

The consensus problem. Algorithms and lower bounds

May 1

The shared memory model, Wait-free synchronization, 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

May 15

Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper

Moir Anderson, Lamport-87

May 22

Simulating Shared memory in message passing, Randomized Consensus.

May 29

Lower bound techniques (log * n for maximal independent set on ring of size n).

June 5

Renaming, Eventually connected end-to-end STP, Concurrent Time Stamps,


See Course outline with references (pdf






The grade weighting for the semester will be:

Home Works 


Take home exam: 


These weights are subject to change.









Winter 2010 Course page

Winter 2009 Course page

Winter 2008 Course page

Winter 2007 Course page

Winter 2006 Course page