Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
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