The Time Complexity of Consensus Under Oblivious Message Adversaries
summary
Establishes the first time complexity lower bounds for consensus under oblivious message adversaries and rephrases Coulouma et al.’s solvability criterion as a decision procedure whose runtime lower-bounds consensus. Builds explicit graph families GI with exponentially many allowed rounds using a binary-encoding gadget B and indistinguishability graphs, proving the decision procedure can take exponential time. Also constructs families where the decision procedure halts in constant rounds while consensus itself requires exponential rounds, so the two runtimes are not equivalent.
AI-written summary · about
chapters (5)
- 0:00Start
- 2:57OBLIVIOUS MESSAGE ADVERSARIES
- 7:12THE DECISION PROCEDURE - EXAMPLES
- 9:59EXPONENTIAL TIME FOR DECISION PROCEDURE
- 14:01EXPONENTIAL CONSENSUS TIME (CONSTANT DEC. PROC.)
related talks
56mConsensus Through Herding
34mConsensus with Adaptive Adversaries in the Synchronous and Partially Synchronous Models...
32mAnalysis of Nakamoto Consensus
30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain Model
18mAdoB: Bridging Benign and Byzantine Consensus with Atomic Distributed Objects
58mThe Communication Complexity Landscape of Information-theoretic MPC
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
45mOn Analyzing Blockchain Consistency