2020/03/04 by Bryan Ford, Ford, Bryan, Philipp Jovanovic +3
Computer Science · #Advanced Data Storage Technologies #Cooperative Communication and Network Coding #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Interconnection Networks and Systems #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2003.02291
openalex publication_date 2020/03/04 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
It is commonly held that asynchronous consensus is much more complex,\ndifficult, and costly than partially-synchronous algorithms, especially without\nusing common coins. This paper challenges that conventional wisdom with que\nsera consensus QSC, an approach to consensus that cleanly decomposes the\nagreement problem from that of network asynchrony. QSC uses only private coins\nand reaches consensus in O(1) expected communication rounds. It relies on\n"lock-step" synchronous broadcast, but can run atop a threshold logical clock\n(TLC) algorithm to time and pace partially-reliable communication atop an\nunderlying asynchronous network. This combination is arguably simpler than\npartially-synchronous consensus approaches like (Multi-)Paxos or Raft with\nleader election, and is more robust to slow leaders or targeted network\ndenial-of-service attacks. The simplest formulations of QSC atop TLC incur\nexpected O(n2) messages and O(n4) bits per agreement, or O(n3) bits\nwith straightforward optimizations. An on-demand implementation, in which\nclients act as "natural leaders" to execute the protocol atop stateful servers\nthat merely implement passive key-value stores, can achieve O(n2) expected\ncommunication bits per client-driven agreement.\n