Week 2 (August 5th to August 9th)

• Cole Vishkin on general graphs (section 6.3.2)

• Crash Course on Probability (Appendix D)

• Luby's Algorithm for MIS (section 6.1.2)

    Week 4 (August 19th to August 23rd)

• Network Decompositions and the proof of existence of (log n, log n)-network decompositions (Section 2)

• Tree based Algorithms (Chapter 3)

• MST Algorithms: GHS (section 7.1) and Distributed Kruskals (section 7.2)

    Week 6 (September 2nd to September 6th)

• Garay-Kutten-Peleg (GKP) algorithm (section 7.3)

• Hardness of Distributed MST

    Week 8 (September 16th to September 20th)

• PAXOS Continued

• Impossiblity of Consensus with crash faults

    Week 10 (September 30th to October 4th)

• Byzantine Agreement

• Algorithm 17.9 in the notes fails to achieve all-same validity in the case where all nodes have input 1 and the byzantine node pretends that its input is 0. Therefore all nodes agree on the minimum which is 0, but fail to achieve validity because the input of all correct nodes is 1. 

• One way to achieve all-same validity is: node u adds a tuple (v,w,y) to S_u if and only if the value y is received from two different nodes v,w, such that ID(v) < ID(w). This way we are sure that at least one correct node has input y. The proof that set T is the same across all nodes remains unchanged, and implies that the minimum value is an input of some correct node.

    Week 12 (October 14th to October 18th)

• SLOCAL model and approximate maximum independent set (Sections 2.3 and 7.1)

• SLOCAL to LOCAL using Network Decompositions

• Network Decompositions in SLOCAL (Section 9)

    Week 14 (October 28th to November 1st)

• DISC 2024, no classes.