Fast distributed agreement (preliminary version)
Sam Toueg, Kenneth J. Perry, T K Srikanth · 1985
We describe a non-authenticated Byzantine Generals algorithm, with early stopping, for systems with arbitrary process failures.The algorithm presented is simpler, terminates earlier and has a lower communication complexity than those previously known.Surprisingly, the earlystopping algorithm is as efficient as previously proposed algorithms that do not exhibit the early-stopping property.It was derived using a broadcast primitive that simulates authentication and thus restricts the visible failure behavior of faulty processes.This primitive is a general tool for deriving fault-tolerant algorithms in the presence of arbitrary failures.