http://www.cs.tau.ac.il/images/school-title.jpg

 

Distributed Computing

0368-4429-01

Spring-Summer 2010 (2009/2010)

Lecturer: Prof. Yehuda Afek

 

Question in preparation to the exam

Links to presentations of last lecture

http://www.cs.tau.ac.il/~multi/slides/chapter_04.pptx

http://www.cs.tau.ac.il/~multi/slides/chapter_03.pptx

Homework #1 Due March 21

Homework #2 Due April 18

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

Administrative Information

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

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

Course Topics and Schedule (tentative, subject to change)

DATE

TOPIC

Feb 21

Models, Broadcast & Echo

March 7

Termination Detection, Snapshots, Synchronizers Snapshot paper pdf

March 14

Leader Election, ring networks, unidirectional case

March 21

Leader Election Algorithms and Spanning tree algorithms

April 11

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

April 18

Data link protocols, the sequence transmition problem and

End-to-End protocols and another pdf

April 25

 

May 2

The consensus problem. Algorithms and lower bounds

May 9

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

May 16

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

May 23

Mutual exclusion, Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper

Moir Anderson, Lamport-87

May 30

Simulating Shared memory in message passing, Randomized Consensus.

June 6

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

Time permitting

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

 

See Course outline with references (pdf)


Grade

The grade weighting for the semester will be:

Home Works 

35%

Take home exam: 

65%

These weights are subject to change.


Winter 2009 Course page

Winter 2008 Course page

Winter 2007 Course page

Winter 2006 Course page