NewsAktuell gibt es keine Neuigkeiten
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