40 Years of Computing at Newcastle

Department Technical Report Series No. 582

Time-out Based Message Ordering Protocols for Software Implementation of TMR Systems

P.D. Ezhilchelvan, F.V. Brasileiro and N.A. Speirs

University of Newcastle upon Tyne. 1997.

Abstract

Replicated processing with majority voting is a well known method for achieving reliability and availability - two key attributes of dependability. Triple Modular Redundant (TMR) processing is the most commonly used version of that method. Replicated processing requires that the replicas reach agreement on the order in which messages are to be processed. Almost all synchronous and deterministic ordering protocols published in the literature are time based in the sense that they require replicas' clocks to be kept synchronise within some known bound. We present a protocol for TMR systems that is based on timeouts and consequently does not require clocks to be kept in bounded synchronism. We analyse the protocol performance and show that this protocol is as fast as any time based ordering protocol when clocks cannot be synchronised using low-level processes with fast access to communication hardware. We also derive a faster protocol that has an improved performance in the absence of processor failures. We then build a TMR node and measure its performance to illustrate that the protocols developed here are useful for fast message ordering and are easy to implement.

Department Technical Report Series - 1997
Department Technical Report Series Index
Contents Page - 40 Years of Computing at Newcastle

Technical Report Abstract No. 582, 30 June 1997