Abstract

We give randomized agreement algorithms with constant expected
running time in asynchronous systems subject to process failures,
where up to a minority of processes may fail. We consider three types
of process failures: crash, omission, and Byzantine. For crash or omission
failures, we solve consensus assuming private channels or a publickey
infrastructure, respectively. For Byzantine failures, we solve weak
Byzantine agreement assuming a public-key infrastructure and a broadcast
primitive called weak sequenced broadcast. We show how to obtain
weak sequenced broadcast using a minimal trusted platform module.
The presented algorithms are simple, have optimal resilience, and have
optimal asymptotic running time. They work against a sophisticated adversary
that can adaptively schedule messages, processes, and failures
based on the messages seen by faulty processes.

‚Äč