Application Properties

We can make some observations to understand some of the properties of the model that allowed us to reduce the state so dramatically.

• Property 1: The majority of the operations that modify the state variables are ``constructive'' in nature. That is, the undo operation for such operations requires no history. Only the most current values of the variables are required to undo the operation. For example, operators such as $++$, $-$, $+=$, $-=$, $*=$ and $/=$ belong to this category. The $*=$ and $/=$ operators require special treatment in the case of multiply or divide by zero, and overflow/underflow conditions. More complex operations such as circular shift (swap being a special case), and random number generation also belong here.

• Property 2: The complexity of the code is such that the ``control state'' of the code occupies less memory than the ``data state'' of the variables.

• Property 3: The non-reversibility of the individual steps that compose a computation do not necessarily imply that the computation, when taken as a whole, is not reversible.

If property 1 is not satisfied in the model because of the presence of non-constructive operations such as plain assignment or modulo computation, the reverse computation method can in fact degenerate to the conventional state-saving operations. We call such non-constructive operations destructive assignments. A straightforward method to reverse a destructive assignment is to save the old contents of the left-hand-side as a record of the ``control information'' for that assignment statement, which makes it degenerate to state-saving.

If property 2 is not satisfied because the code is ``too complex'' (i.e., the amount of control state is more than the data state), we can fall back to traditional state-saving techniques. We show later in Section 4 that using paired branches will enable a perfectly reversible flow of control [40]. Thus, we believe that in the future, no system will be ``too complex'' from the control flow prospective to preclude efficient reversibility.

Queuing network models are an excellent example of the domain of models in which the preceding two properties are satisfied to a large extent. Consequently, we have shown that TiPRC is well suited for the optimistic simulation of large-scale network models. We believe the same will be true of PRC.

Property 3 suggests that even if the individual steps of a computation are not efficiently reversible (i.e., either property 1 or 2 is violated), then one should look to a higher-level to see if the computation is not reversible. As example, L'Ecuyer's Combined Linear Congruential RNG [65] is perfectly reversible without resorting to any state-saving despite making use of individual operations such as integer division that result in bit loss [20,21].