|
|
|
|
Distributed
Computing 0368-4429-01 Spring-Summer 2016 Lecturer: Prof. Yehuda Afek |
|
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, Shenkar
222
· Office Hours, by appointment
(email)
Course Topics and Schedule (Tentative,
subject to change !! )
|
DATE |
TOPIC |
|
Feb 28 |
Models, and Introduction. |
|
March 6 |
Broadcast
and Echo Termination Detection, Snapshots, Synchronizers Snapshot
paper pdf |
|
March 13 |
Leader
Election, ring networks, unidirectional case |
|
March 20 |
Leader Election Algorithms and Spanning tree algorithms
(general topology networks) |
|
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, Eventually connected end-to-end STP, The
consensus problem. Algorithms and
lower bounds, |
|
April 10 |
The phase
king protocol of Berman and Garay, The shared
memory model, Safe, Regular and Atomic Registers, |
|
April 17,
24 |
*** Pesach *** |
|
May 1 |
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 8 |
The
consensus problem, and its impossibility in
asynchronous networks with one faulty processor. Simulating
Shared memory in message passing, |
|
May 15 |
Mutual exclusion,
Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper Moir Anderson,
Lamport-87 |
|
May 22 |
Randomized
Consensus. |
|
May 29 |
Renaming,
Concurrent Time Stamps, |
|
June 5 |
Concurrent
programming, the link list case |
|
Time
permitting |
Paxos |
The grade weighting for the semester
will be:
These weights
are subject to change.