|
|
|
|
Distributed
Computing 0368-4429-01 Spring-Summer 2017 Lecturer: Prof. Yehuda Afek |
|
HomeWork1 Due April 2
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, Dan
David 201
· Office Hours, by appointment
(email)
Course Topics and Schedule (Tentative,
subject to change !! )
|
DATE |
TOPIC |
|
March 19 |
Models, and Introduction. |
|
March 26 |
Broadcast
and Echo Termination Detection, Snapshots, Synchronizers Snapshot
paper pdf |
|
April 2 |
Leader
Election, ring networks, unidirectional case |
|
** Pesah ** |
|
|
April 23 |
Leader Election Algorithms and Spanning tree algorithms
(general topology networks) |
|
April 30 |
Computing the maximal independent set, rings and
general graphs, upper and lower bounds |
|
May 7 |
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, |
|
May 14 |
The phase king
protocol of Berman and Garay, The shared memory
model, Safe, Regular and Atomic Registers, |
|
May 21 |
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 28 |
The
consensus problem, and its impossibility in
asynchronous networks with one faulty processor. Simulating
Shared memory in message passing, |
|
June 4 |
Mutual exclusion,
Fast Mutual Exclusion, Adaptive Algorithms Taubenfeld Paper Moir Anderson,
Lamport-87 |
|
June 11 |
Randomized
Consensus. |
|
June 18 |
Renaming,
Concurrent Time Stamps, |
|
June 25 |
Concurrent
programming, the link list case |
|
Time
permitting |
Paxos |
Grade
The grade
weighting for the semester will be:
|
Home Works: |
40% |
|
Final Project: |
60% |
These weights are subject to change.