Upon executing a receive statement, if an LP simply selects the matching
message from its queue that has the earliest receive timestamp among all
matching messages, it
is not guaranteed that subsequently, a matching message with an
earlier receive timestamp will not arrive, invalidating the original
selection. A simulation protocol
is a protocol used by an LP to synchronize with other LPs to establish
which message selections are safe, i.e. which
selections will not get invalidated
eventually. Some simulation protocols are always correct i.e. they
allow only safe selections. We term these
protocols safe protocols, and the
target traces they produce, safe target traces.
Other simulation protocols allow
some unsafe selections to be made, and are consequently
called unsafe protocols, and the
target traces they produce are called unsafe target traces.
Unsafe target program traces are always valid:
a program P with input I, simulated using an unsafe protocol,
will always produce a target program trace that is in 
.
However, an unsafe target execution trace may or may not be valid
(i.e. the target execution trace may not be in 
).
In general, given an unsafe target trace, it is hard
to reconstruct the corresponding safe target trace,
and consequently it is hard to predict the error in the
execution time estimate of the unsafe target trace.
In what follows, we first describe the most commonly used simulation protocol, a synchronous protocol which we term the quantum protocol. We present the quantum protocol and its shortcomings in the context of our simulation model. We then present our approach, in which we optimize two existing asynchronous protocols, called the null message[Cha81] and the conditional event[Cha89a] protocols, for use in our simulation model. To the best of our knowledge, neither protocol has been directly applied to the problem of parallel program simulation.
In all protocols, we assume FIFO communication between LPs.