Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Friday, March 15, 2013, 12:15 pm
Duration: 30 minutes
Location: CAB G11
Speaker: Christoph Lenzen (Massachusetts Institute of Technology)
In the consensus problem, n nodes seek to agree on one of their input values despite up to t failing nodes. For this task, it is known that synchronous deterministic algorithms cannot guarantee that, in all executions with at most f faults, all correct nodes decide in round f or earlier on the output. This holds even if nodes may merely crash, i.e., in some round send a subset of the scheduled messages and then cease running the algorithm. For Byzantine, i.e., worst-case, behavior of faulty nodes, we prove that it is impossible to guarantee decision in f+2 rounds.
However, the main focus of the talk is the number of messages sent by algorithms achieving these bounds. We show that (f+2)-deciding algorithms that deal with Byzantine faults must send Omega(t2f) messages in some execution with f faults. In the case of crash faults, where (f+1)-decision is possible, matching this bound is even more expensive: Omega(n2f) messages must be sent, regardless of t. In contrast, one can easily achieve (f+1)-decision with O(nt) messages for so-called orderly crash faults, where algorithms specify an order on the messages of each round and crashing nodes successfully send a prefix of the message list according to this order.
The talk will address a general audience; no previous knowledge on consensus is assumed.
Automatic MiSe System Software Version 1.4803M | admin login