The Implementation of Reliable Distributed Multiprocess Systems

In [27], I introduced the idea of implementing any distributed system by using an algorithm to implement an arbitrary state machine in a distributed system. However, the algorithm in [27] assumed that processors never fail and all messages are delivered. This paper gives a fault-tolerant algorithm. It’s a real-time algorithm, assuming upper bounds on message delays in the absence of faults, and that nonfaulty processes had clocks synchronized to within a known bound.

To my knowledge, this is the first published paper to discuss arbitrary failures (later called Byzantine failures). It actually considered malicious behavior, not using such behavior simply as a metaphor for completely unpredictable failures. Its algorithm was the inspiration for the digital signature algorithm of [41]. With its use of real-time, this paper presaged the ideas in [55].