It is commonly held that asynchronous consensus is much more complex,
difficult, and costly than partially-synchronous algorithms, especially without
using common coins. This paper challenges that conventional wisdom with que
sera consensus QSC, an approach to consensus that cleanly decomposes the
agreement problem from that of network asynchrony. QSC uses only private coins
and reaches consensus in O(1) expected communication rounds. It relies on
"lock-step" synchronous broadcast, but can run atop a threshold logical clock
(TLC) algorithm to time and pace partially-reliable communication atop an
underlying asynchronous network. This combination is arguably simpler than
partially-synchronous consensus approaches like (Multi-)Paxos or Raft with
leader election, and is more robust to slow leaders or targeted network
denial-of-service attacks. The simplest formulations of QSC atop TLC incur
expected O(n2) messages and O(n4) bits per agreement, or O(n3) bits with
straightforward optimizations. An on-demand implementation, in which clients
act as "natural leaders" to execute the protocol atop stateful servers that
merely implement passive key-value stores, can achieve O(n2) expected
communication bits per client-driven agreement.