next up previous
Next: Protocol Implementation Up: Quantum Protocol Previous: Quantum Protocol

Protocol Description

In this protocol, all LPs synchronize after every Q simulation time instants, where Q is termed the simulation quantum. This periodic global synchronization affects only the semantics of receive statements in the simulation model: upon executing a receive statement, an LP accepts the earliest matching message only if it has a receive timestamp less than the simulation time instant at which the current quantum terminates. Otherwise, the LP remains blocked, and its simulation time is updated to the time instant at which the current quantum terminates. The receive statement is re-executed in the following quantum.

The quantum protocol is safe only if the simulation quantum, Q, is less than the minimum communication latency, L, of the target machine. The proof of this statement is as follows: Messages sent from one LP to another in one quantum are guaranteed to have been deposited in the recipient's message queue before the next quantum starts, because the periodic global synchronization flushes messages in transit. In the pth quantum, which covers the simulation interval , an LP can select only messages which have a receive timestamp less than . Consequently, an upper bound on the send timestamp of a selected message is . If Q<L, . Consequently, in the pth quantum, only messages that have been sent in the previous or earlier quantum can be selected for acceptance. Because of the global synchronization, all such messages must already be present in the LP's queue. Consequently, the message selection cannot be invalidated eventually.



next up previous
Next: Protocol Implementation Up: Quantum Protocol Previous: Quantum Protocol



Andy Kahn
Wed Jun 25 20:28:02 PDT 1997