|
|
|
|
Distributed
Computing 0368-4429-01 Spring-Summer 2019 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,
Schreiber 007
· Office Hours, by appointment
(email me)
Course Topics and Schedule (Tentative,
subject to change !! )
|
DATE |
TOPIC |
|
March 3 Adam
Morrison |
Models,
Introduction, Shared memory Mutual Exclusion. |
|
March 10 |
Broadcast
and Echo Termination Detection, Snapshots, Synchronizers,
Snapshot paper pdf |
|
March 17 |
Leader
Election, ring networks, unidirectional case |
|
March 24 |
Leader Election Algorithms and Spanning tree algorithms
(general topology networks) |
|
March 31 |
The consensus problem. Algorithms and lower bounds, |
|
April 7 |
Berman Garay phase king
protocol, |
|
April 14 |
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, |
|
** Pesah ** |
|
|
April 28 |
The consensus problem, and its
impossibility in asynchronous networks with one faulty processor. Simulating Shared memory in
message passing, Randomized Consensus. |
|
May 5 |
Fault tolerant Byzantine
Agreement, Miguel Castro, Barbara Liskov, OSDI 1999 |
|
May 12 |
Paxos, Raft, State Machine
replication |
|
May 19 |
Bitcoin protocol, Satoshi
Nakamoto |
|
May 26 |
Alternative (to PoW) Blockchain
protocols, TBD (Stellar, or Filecoine,
or Ripple, …) |
|
June 2 |
Blockchain applications, e.g., An
empirical study of Namecoin and lessons for decentralized namespace design
|
|
Time permitting |
|
|
Computing the maximal independent set, rings and general
graphs, upper and lower bounds |
Grade
The grade weighting for the
semester will be:
|
Home Works: |
40% |
|
Final Project: |
55% |
|
Class participation: |
5% |
These weights are subject to change.