|
|
|
||||||||||||||||||||||||||||||||||||||||
|
Distributed
Computing 0368-4429-01 Spring-Summer 2020 Lecturer: Prof. Yehuda Afek ציונים:
|
|
פרויקט (הדף
עשוי להתעדכן
מדי פעם)
Administrative Information
· Lectures: Sunday 16:10-19:00, Kaploon 118
· Office Hours, by appointment (email
me)
Course Topics and Schedule (Tentative,
subject to change !! )
|
DATE |
TOPIC |
|
March 8 |
Broadcast
and Echo |
|
March 15 |
Termination Detection, Snapshots, Synchronizers,
Snapshot paper pdf
Leader Election, ring networks, lower
bound |
|
March 22 |
Leader Election Algorithms and Spanning tree algorithms
(general topology networks) |
|
March 29 |
The
consensus problem. Berman Garay phase king protocol, Algorithms and lower bounds,
f<n/4 and f<n/3 in 2f and 3f rounds |
|
April 19 |
Impossibility of
Consensus in shared memory 2 processors 1 fault. Impossibility n processors 1 fault (BG simulation). |
|
April 26 |
Waitfree.
The shared memory hierarchy and universal constructions. Common2.
Level 1? Atomic Snapshots of shared memories, Immediate snap-shots, |
|
May 3 |
The consensus problem,
and its impossibility in asynchronous networks with one faulty processor. Simulating
Shared memory in message passing, Randomized Consensus. |
|
** Pesah ** |
|
|
May 10 |
Fault
tolerant Byzantine Agreement, Miguel Castro, Barbara Liskov,
OSDI 1999 |
|
May 17 |
Paxos, Raft, State Machine replication |
|
May 24 |
Bitcoin protocol, Satoshi Nakamoto |
|
May 31 |
From Paxos to Byzantine SMR* to Blockchains
(*State Machine Replication) |
|
June 7 |
Overview,
Discussion of projects, Homeworks, Blockchain applications, Game Theory (hw3), log*n upper
and lower bound for maximal independent set. |
|
June 14 |
|
|
June 21 |
|
|
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% (10% - writing and
presentation, 90% creativity, innovation and
technical depth) |
|
Class participation: |
5% |
These weights are subject to change.