4.1 Conservative Simulation

Conservative simulation engines prevent lcc violations by ensuring that all events are processed in order and all messages are sent and received in order. Computer scientists have developed a variety of techniques that implement conservative simulations, the most widely used is the Chandy-Misra (CM) algorithm.

The CM algorithm provides each LP with an event list, input buffers and output buffers. The event list is a time ordered list of future events that were create by the LP associated with the event list. Each LP has an input and an output buffer for each of the other LPs. The input buffers store messages incomming messages from other LPs in a time ordered list and the output buffers store outgoing messages. The system guarantees that all messages are sent and received in the correct time sequence. This in turn guarantees that no LP will send a message with a lower time stamp than any event in the associated input buffer.

The smallest time stamp on all of the input buffers represents the time for which the LP is guaranteed to have no messages from other LPs. This means that the LP can process its own events without an lcc violation. Hence, the CM algorithm prevents lcc violations.

The drawback to conservative simulations is that when any of the input buffers are empty, the LP has to wait until that buffer receives a message. The time spend waiting is wasted time which degrades the performance of the system.