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).