Algorithms for fault-tolerant distributed systems. Final technical report, February 1985-February 1988
Leslie Lamport, Peter Michael Melliar-Smith, L.E. Moser, I. Greenberg, John Rushby · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1989
The research described is presented in six parts: (1) Interprocess Communication studies interprocess communication without assuming any lower-level communication primitives. A formalism is developed for reasoning about concurrent systems that does not assume an atomic grain of action; (2) The Intersecting Broadcast Machine is a novel array processor architecture, capable of processing efficiently programs whose arbitrary or complex structure would make them difficult to map onto conventional array processors. The architecture also supports fault-tolerant operation: (3) Broadcast Protocols for Distributed Systems considers how the broadcast character of communications media such as Ethernet and packet radio can be exploited to yield reliable communication with very little overhead; (4) Extending Interval Logic to Real Time Systems presents a technique for the formal expression of the real-time constraints that are critical to the specification of fault-tolerant distributed systems; (5) Consistency of Replicated Information in Multichannel Fault Tolerant Systems considers the possibility of using similar, but not identical, processing in the replicas of a fault-tolerant system. Conventional fault-tolerant systems using replicate processing require the replicas to be identical, so that they can be compared by exact match algorithms. This exact replication increases the risk that a common fault will affect all replicas and causemore » system failure; and (6) Experimental Implementation and Evaluation of the TRANS Broadcast Protocol describes an implementation and evaluation of the broadcast protocol outlined in Part III.« less