What is Perfect Reverse Computation (PRC)?

As presented in Section 1, PRC is an extension of TiPRC which generates no entropy in the form of information loss. Recall, that TiPRC generates entropy in the form of control information (i.e., records which branch was taken or how many times through a loop plus incrementally state-saves any destructive assignments). This control information was stored in a bit field. PRC has no such bit field. PRC is able to execute forward or backward based solely on the current state of the system.

To support PRC in general, a program cannot produce any information loss. This means PRC should allow arbitrarily-long reversible computations through simulated time consuming only a constant amount of memory. This is the fundamental difference between PRC and TiPRC. TiPRC creates garbage in the form of control bits, and thus reverse execution can only be supported over a small range of simulated time. Once the garbage bits are collected, TiPRC cannot reverse beyond that point in the computation.

To illustrate how PRC would work in practice, consider the following timing diagram of a network model from [76] (see Figure 2). Suppose we have three LPs. The first two are Node LPs that are able to send and receive packets to each other and manage a finite amount of buffer space. Connecting these two Node LPs is a Link LP which is responsible for storing the current usage and availability on this link. Assume that LP $Node_0$ is at virtual time $VT=90$, LP $Link_0$ is at $VT=85$ and LP $Node_1$ is at $VT=90$. Now consider the following exchange of events:

1. LP $Node_0$, currently at $VT=90$, requests $B_0$ units of bandwidth at virtual time, $VT=100$ to LP $Link_0$.

2. LP $Link_0$ processes the request at $VT=100$ and responds to LP $Node_0$ with $B$ units of bandwidth and decrements its available bandwidth by $B$ units at $VT=101$.

3. LP $Node_1$ requests $B_1$ units of bandwidth at $VT=90$ to LP $Link_0$.

In a classic optimistic synchronization scheme, LP $Link_0$ would rollback to $VT=90$ because the request message from LP $Node_1$ is in the past and thus an error with respect to event causality. By rolling back, $Link_0$ would have scheduled an ``anti-message'' for LP $Node_0$. However, under PRC, rollback can be realized by running the simulation backwards. This is effectively accomplished by the following series of ``reverse'' events:

1. LP $Link_0$ detects the out-of-order event execution and issues a reverse event to LP $Node_0$ at $VT=101$. The reverse event here is used to find the leading edge of the incorrect event computation path. $Link_0$'s direction state is changed to reverse causing it to only process reverse events. Since it has no other reverse events to process, it waits until it receives one. Observe that the arriving forward event at $VT=110$ is ignored. When operating in reverse, an LP processes events in largest or highest timestamp order.

2. Assume the forward event at $VT=101$ has been processed. Upon receiving the reverse event, LP $Node_0$ immediately ``undoes'' the event at $VT=101$ using the event data and it's current state as input. As part of reverse processing this event, it schedules a ``reverse'' event at $VT=101$ to LP $Link_0$.

3. LP $Link_0$ receives the reverse event at $VT=101$ executes backward to $VT=85$ using the event and it current state as input. As part of reverse event processing, it schedules a reverse event to LP $Node_0$ at $VT=100$. Because its local clock is less than the rollback time of $VT=90$, $Link_0$ switches back to forward execution and processes the event at $VT=90$ sent by LP $Node_1$.

4. $Node_0$ reverse executes the reverse event at $VT=100$. It then observes its current local virtual time is $VT=90$, which is equal to the rollback time and so it to switches back to forward execution of events and re-processes the event at $VT=90$.

The above scenario is kept simple to illustrate how PRC would work. This example motivates the research thrust areas which are discussed below.