Fast Asynchronous Consensus with Optimal Resilience

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.

disc-camera-ready.pdf
PDF file

In  24th International Symposium on Distributed Computing (DISC 2010)

Publisher  Springer Verlag
All copyrights reserved by Springer 2007.

Details

TypeInproceedings
> Publications > Fast Asynchronous Consensus with Optimal Resilience