Reverse computation

[7][8] Based on the successful application of Reverse Computation concepts in other software domains, Chris Carothers, Kalyan Perumalla and Richard Fujimoto[9] suggest the application of reverse computation to reduce state saving overheads in parallel discrete event simulation (PDES).

The key property that reverse computation exploits is that a majority of the operations that modify the state variables are “constructive” in nature.

More complex operations such as circular shift (swap being a special case), and certain classes of random number generation also belong here.

In 1985 Jefferson introduced the optimistic synchronization protocol, which was utilized in parallel discrete event simulations, known as Time Warp.

[11] To date, the technique known as Reverse Computation has only been applied in software for optimistically synchronized, parallel discrete event simulation.

[12] [notes 1] In 1998 Carothers and Perumalla published a paper for the Principles of Advanced and Distributed Simulation workshop[13] as part of their graduate studies under Richard Fujimoto, introducing technique of Reverse Computation as an alternative rollback mechanism in optimistically synchronized parallel discrete event simulations (Time Warp).

Working with graduate students David Bauer and Shawn Pearce, Carothers integrated the Georgia Tech Time Warp design into Rensselaer’s Optimistic Simulation System (ROSS), which supported only reverse computation as the rollback mechanism.

Carothers also constructed RC models for BitTorrent at General Electric, as well as numerous network protocols with students (BGP4, TCP Tahoe, Multicast).

Page at Mitre Corporation, and in collaboration with Carothers and Pearce pushed the ROSS simulator to the 131,072 processor Blue Gene/P (Intrepid).

Bauer also created an RC variant of SEIR that generates enormous improvement over continuous models in the area of infectious disease spread.