Fast Asynchronous Consensus with Optimal Resilience

ittai abraham, marcos aguilera, and dahlia malkhi


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.


Publication typeInproceedings
Published in24th International Symposium on Distributed Computing (DISC 2010)
PublisherSpringer Verlag
> Publications > Fast Asynchronous Consensus with Optimal Resilience