Distributed Computing


Spring-Summer 2013

Lecturer: Prof. Yehuda Afek

HW3 Due May 26

HW1 Due April 7

HW2 Due April 21


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

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

Administrative Information

       Lectures: Sunday 16:10-19:00, Multi-Disciplinary Center 315

       Office Hours, by appointment (email)

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



March 3

Models, and Introduction.

March 10

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

March 17

Leader Election, ring networks, unidirectional case

April 7

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

April 14

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

April 21

Data link protocols, the sequence transmition problem and

End-to-End protocols and another pdf

April 28

The consensus problem. Algorithms and lower bounds

May 5

The shared memory model, Wait-free synchronization, the shared memory hierarchy and universal constructions. Atomic Snapshots of shared memories, Immediate snap-shots,

May 12

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

May 19

Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper

Moir Anderson, Lamport-87

May 26

Simulating Shared memory in message passing, Randomized Consensus.

June 2

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

June 9

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

June 16

Concurrent programming, the link list case


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 2012 Course page

Winter 2011 Course page

Winter 2010 Course page

Winter 2009 Course page

Winter 2008 Course page

Winter 2007 Course page

Winter 2006 Course page