Theory on Consensus

Theory on Consensus

We will study a selection of key results on the fundamental consensus problem. In consensus, each of n parties receives an input, and the goal is to compute an output that (i) is the same for each party and (ii) satisfies a validity constraint (the most basic one would be: if all honest parties have the same input, this must be the output). The challenge is the an unknown subset of the parties may be faulty, to the point of maliciously trying to prevent consensus.

In this proseminar, you will be assigned a groundbreaking result to present to the other participants. The quality of your presentation matters most (75%), but you will also be expected to follow your fellow students' presentations and participate in the discussion (25%). There will be a test run of your presentation with me, to help you prepare the best presentation possible. Presentations should be 40-45 minutes, with a hard cap of 60 minutes. Note that this extra time is there to account for questions during the talk, not as slack for the presentation time! This is followed by questions from the audience.

Requirements: There are no specific requirements. However, be aware that this course will put significant focus on proofs, so I recommend to pick it only if you are inclined towards and proficient in mathematical reasoning.

Sessions: Wednesday, 12 - 14 ct, Bernd Therre lecture hall (CISPA main building, ground floor, left hand side, C0 - 0.05), except for June 7, when we meet in C0 - 0.01 (same building and floor, right hand side)

Test runs: Wednesday, 10 - 11.30 (as close to st as possible for you), in the week before the presentation, at MPI for Informatics (building E1.4), 3rd floor, room 314. A different time can be agreed on in case of a collision.

19.04.: Organization and topic assignment (see materials for possible choices), will end at 1 pm - Christoph

26.04.: "What is Consensus and Why Do We Care?" - Introduction that also serves as an example of what is expected from a talk. - Christoph

03.05.: Synchronous Consensus for n>3f

10.05.: Impossibility for n <= 3f

17.05.: Round Lower Bound

24.05.: Message/Signatures Lower Bound

31.05.: Impossibility of Deterministic Consensus in Asynchronous Systems

07.06.: Randomized Consenus in Asynchronous Systems

14.06.: Consensus Numbers

21.06.: Shared Memory Consensus with Optimal Step Complexity

28.06.: Consensus with Signatures

05.07.: Fast Randomized Consensus with Signatures

12.07.: backup slot

19.07.: backup slot