What is the minimum state needed to support PRC?

We observe from the previous event flow example, that an LP must keep certain elements of state. At a first glance, an LP must keep a copy of the last ``output'' events for LPs it communicates or schedules events to as well as the last ``input'' events it has processed from each LP it receives from.

Using this approach, we observe that the static state requirements can become unwieldy based on this approach and could lead to higher state overheads than required for TiPRC based simulations. For example, consider the canonical broom brush network model example where you have $X$ network sources connected to $Y$ sinks via a single router LP. Suppose we want to run this model backwards or roll it back from a given state. Thus, we observe that the sinks effectively become sources and the sources become sinks. But how will the sinks know to which source to ``unsend'' messages to? The way to accomplish that is for each sink to keep the last message processed from each distinct source. Then using that last message and the random number generator seeds contained within it, the sink can re-produce the reverse message back to the original source as well as the timestamp and event data of the next outgoing message. So, if all sources communicate equally with the sinks through the router, the model would need record $X*Y$ messages. For models of size this amount of state could be quite large.

To reduce the amount of state, it may be possible to leverage the random number generators seeds used to determine the destination LP as well as other attributes of the message data sent. So, here instead of the sink LPs recording last processed event data, they would instead take the most resent seed set of the source LPs and effectively execute the generator events backwards. Note, the issue of reversible control flow is discussed next. More specifically, the $Y$ sinks would divide up the $X$ source random number seed sets and reproduce the events in backwards order. This however assumes that events processed by the router are done in FIFO order. If not, the routers queuing policy would have to be considered in the backwards path as well.

Clearly the necessary and sufficient static state required for supporting PRC in the context of parallel simulation is an open question. We propose to address this question in this research project.