Distributed Computing Course

לוגו אוניברסיטת תל אביב

Distributed Computing

0368-4429-01

Winter 2024 תשפ"ד

DATE 2024	TOPIC
January 2	Broadcast and Echo
January 9	Termination Detection, Snapshots, Synchronizers, Snapshot paper pdf Leader Election, ring networks, lower bound
January 16	Leader Election Algorithms and Spanning tree algorithms (general topology networks)
January 23	* * סגירת פערים השלמות
Januray 30	The consensus problem. Berman Garay phase king protocol, Algorithms and lower bounds, f<n/4 and f<n/3 in 2f and 3f rounds
February 6	Impossibility of Consensus in shared memory 2 processors 1 fault. Impossibility n processors 1 fault (BG simulation).
February 13	Waitfree. The shared memory hierarchy and universal constructions. Common2. Level 1? Atomic Snapshots of shared memories, Immediate snap-shots,
February 20	The consensus problem, and its impossibility in asynchronous networks with one faulty processor. Simulating Shared memory in message passing, Randomized Consensus.
February 27	* Municipal Election Day *
March 5	Paxos, Raft, State Machine replication
March 12	Bitcoin protocol, Satoshi Nakamoto
Time permitting	Algorand protocol, Proof of Stake, Proof of Space
Time permitting	From Paxos to Byzantine SMR* to Blockchains (*State Machine Replication)
Time permitting	Fault tolerant Byzantine Agreement, Miguel Castro, Barbara Liskov, OSDI 1999

Time permitting	Proof of Space/Time blockchain
Time permitting	Computing the maximal independent set, rings and general graphs, upper and lower bounds

Administrative Information

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:

In person or Zoom

These weights are subject to change.

עמוד הקורס משנה שעברה 2022-23