Ren Ling: Efficient Synchronous Byzantine Consensus

Friday, May 4, 2018 - 1:00pm to 2:30pm
Location: 
32-G631
Speaker: 
Ren Ling
Seminar group: 
Theory of Distributed Computing (TDS)
We present new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. We present a synchronous state machine replication protocol that tolerates f Byzantine faults with 2f+1 replicas and commits a decision every 3 rounds in the common case. Our protocol also solves synchronous authenticated Byzantine agreement in expected 8 rounds. The best previous solution (Katz and Koo, 2006) requires expected 24 rounds. The key challenge is to ensure quorum intersection at one honest replica. Our solution is to rely on synchrony to form a post-commit quorum of size 2f+1, which intersects at f+1 replicas with any pre-commit quorums of size f+1.