Consensus protocols for asynchronous networks are usually complex and
inefficient, leading practical systems to rely on synchronous protocols. This
paper attempts to simplify asynchronous consensus by building atop a novel
threshold logical clock abstraction, which enables upper layers to operate as
if on a synchronous network. This approach yields an asynchronous consensus
protocol for fail-stop nodes that may be simpler and more robust than Paxos and
its leader-based variants, requiring no common coins and achieving consensus in
a constant expected number of rounds. The same approach can be strengthened
against Byzantine failures by building on well-established techniques such as
tamper-evident logging and gossip, accountable state machines, threshold
signatures and witness cosigning, and verifiable secret sharing. This
combination of existing abstractions and threshold logical clocks yields a
modular, cleanly-layered approach to building practical and efficient Byzantine
consensus, distributed key generation, time, timestamping, and randomness
beacons, and other critical services.