|
|
|
|
Distributed
Computing 0368-4429-01 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 !! )
|
DATE |
TOPIC |
|
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:
These weights are subject to change.