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.
In 24th International Symposium on Distributed Computing (DISC 2010)
Publisher Springer Verlag
All copyrights reserved by Springer 2007.