We consider the Byzantine agreement problem in a fully asynchronous network, where some participants may be actively malicious. This is an important building block for fault-tolerant applications in an hostile environment, and a non-trivial problem: An early result by Fischer, Lynch and Paterson shows that there is no deterministic solution in a fully asynchronous network subject to even a single crash failure.

We introduce an optimistic protocol that combines the two best known techniques to solve agreement, randomization and timing. The timing information is used only to increase performance; safety and liveness of the protocol are guaranteed independently of timing.

Under certain "normal" conditions, the protocol decides quickly and deterministically without using public-key cryptography, approximately as fast as a timed protocol subject to crash failures does.

Otherwise, a randomized fallback protocol ensures safety and liveness. For this, we present an optimized version of the randomized Byzantine agreement protocol of Cachin, Kursawe and Shoup (PODC 2000), which is computationally less expensive and not only tolerates malicious parties, but also some loss of messages; it might therefore be of independent interest.