MESSAGE SLOTTING:

Ensuring Replica Determinism in Preemptive Real-Time Systems

Luís Rodrigues and Paulo Veríssimo

INESC Technical Report (RT/58-93)

Abstract

The state-machine approach is a general paradigm to implement fault-tolerant distributed applications. In real-time systems, preemption of state-machine commands becomes a necessity, when their execution may exhibit a large duration. This assumes a special relevance in dynamic systems, where commands may have different priorities or urgencies. When the state-machine is replicated, consistent preemption of the replicas becomes a problem. This paper describes a general solution to cope with preemption in applications using distributed replicated state-machines. An appropriate design technique is proposed to avoid FIFO queue delays and arbitrarily long commands. The slotted-message facility of a multipoint communication suite (xAMp) is presented. To our knowledge this is the first real-time atomic protocol to support totally ordered preemption of state-machine commands.

Also available as INESC TR/58-93 (gzip postscript).