Distributed Computing


Fall 2022/2023 תשפ"ג

Administrative Information

     Lectures: Tuesday 15:10-18:00,

Orenshtein 102

     Office Hours, by appointment (email me)

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

Compulsory attendance

DATE 2022/23


October 25

Broadcast and Echo

November 1

Election day. Go To Vote !

November 8

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

November 15

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

November 22

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 29

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

December 6

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

December 13

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

Simulating Shared memory in message passing, Randomized Consensus.

December 20

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

December 27

Paxos, Raft, State Machine replication

January 3

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

January 10

Bitcoin protocol, Satoshi Nakamoto

January 17

Algorand protocol, Proof of Stake

January *, 2023

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