The Implementation of Reliable Distributed Multiprocess Systems
In , 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  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 . With its use of real-time, this paper presaged the ideas in .