CS Talk - Bryan Ford
Swiss Federal Institute of Technology in Lausanne (EPFL)
Host: Zhong Shao
QuePaxa: Escaping the Tyranny of Timeouts in Consensus
Leader-based consensus algorithms are fast and efficient under normal conditions, but lack robustness to adverse conditions due to their reliance on timeouts for liveness. We present QuePaxa, the first protocol offering state-of-the-art normal-case efficiency without depending on timeouts. QuePaxa uses a novel randomized asynchronous consensus core to tolerate adverse conditions such as denial-of-service (DoS) attacks, while a one-round-trip fast path preserves the normal-case efficiency of Multi-Paxos or Raft. By allowing simultaneous proposers without destructive interference, and using short hedging delays instead of conservative timeouts to limit redundant effort, QuePaxa permits rapid recovery after leader failure without risking costly view changes due to false timeouts. By treating leader choice and hedging delay as a multi-armed-bandit optimization, QuePaxa achieves responsiveness to prevalent conditions, and can choose the best leader even if the current one has not failed. Experiments with a prototype confirm that QuePaxa achieves normal-case LAN and WAN performance of 600k and 250k cmd/sec in throughput, respectively, comparable to Multi-Paxos. Under conditions such as DoS attacks, misconfigurations, or slow leaders that severely impact existing protocols, we find that QuePaxa remains live with median latency under 380ms in WAN experiments.
Prof. Bryan Ford leads the Decentralized/Distributed Systems (DEDIS) research laboratory at the Swiss Federal Institute of Technology in Lausanne (EPFL). Ford’s research focuses on decentralized systems, security and privacy, digital democracy, and blockchain technology. Since earning his Ph.D. at MIT, Ford has held faculty positions at Yale University and EPFL. His awards include the Jay Lepreau Best Paper Award, the NSF CAREER award, and the AXA Research Chair. Inventions he is known for include parsing expression grammars, delegative or liquid democracy, and scalable sharded blockchains. He has advised numerous companies and governments, including serving on the US DARPA Information Science and Technology (ISAT) Study Group and on the Swiss Federal E-voting Experts Dialog.