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.

PDF file

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

Publisher  Springer Verlag
All copyrights reserved by Springer 2007.

Details