Distributed Computing


Fall 2021/2022 תשפ"ב

Administrative Information

       Lectures: Wednesday 16:10-19:00, TBA

       Office Hours, by appointment (email me)

Course Topics and Schedule (Tentative, subject to change !! )

DATE 2020


October 13

Broadcast and Echo

October 20

Termination Detection, Snapshots, Synchronizers, Snapshot paper pdf Leader Election, ring networks, lower bound

October 27

Leader Election Algorithms and Spanning tree algorithms (general topology networks)

November 3

The consensus problem. Berman Garay phase king protocol, Algorithms and lower bounds, f<n/4 and f<n/3 in 2f and 3f rounds

November 10

Impossibility of Consensus in shared memory 2 processors 1 fault. Impossibility n processors 1 fault (BG simulation).

November 17

Waitfree. The shared memory hierarchy and universal constructions. Common2. Level 1? Atomic Snapshots of shared memories, Immediate snap-shots,

November 24

The consensus problem, and its impossibility in asynchronous networks with one faulty processor.

Simulating Shared memory in message passing, Randomized Consensus.

December 1

Fault tolerant Byzantine Agreement, Miguel Castro, Barbara Liskov, OSDI 1999

December 8

Paxos, Raft, State Machine replication

December 15

From Paxos to Byzantine SMR* to Blockchains (*State Machine Replication)

December 22

Rafael Pass: Bitcoin protocol, Satoshi Nakamoto

December 29

Algorand protocol, Proof of Stake

January 5, 2022

Tal Moran: Proof of Space/Time blockchain

Time permitting

Computing the maximal independent set, rings and general graphs, upper and lower bounds



The grade weighting for the semester will be:

Home Works:


Final Project:

55% (10% - writing and presentation, 90% creativity, innovation and technical depth)

Class participation:


These weights are subject to change.






עמוד הקורס משנה שעברה 2020