Optimistic fossil collection for time warp simulation

Optimistic fossil collection (OFC) is a fully-distributed mechanism to reclaim memory from the state and event histories of a time warp simulation. Each fossil collector executes with a logical process (LP) and operates independently of other fossil collectors. Each one examines event arrival times and creates a statistical model of the expected variance from local virtual time (LVT). From this, it is possible to determine the probability that the LP will, in the future, rollback a distance X from LVT. Thus, the fossil collector can examine the time-stamps of items in the state and event histories to find the probability that they will be needed in the future. Comparing this probability against a user-specified risk factor, the fossil collector decides if the item can be marked as a fossil and scavenged. OFC allows for the possibility for simulation failure, so it may be desirable to periodically have complete checkpoints taken and archived during the simulation for a possible restart with a smaller risk factor specified. This method of memory management assumes there is an underlying stationary distribution for the rollback lengths during a time interval t. This is reasonable, since rollback lengths in time warp are relatively constant in length. This assumption can be relaxed for models that operate without an underlying assumption about the distribution of rollback lengths. This paper reviews the design and implementation of two rollback models for OFC. One assumes a geometrically distributed rollback length; the other assumes an arbitrary distribution of rollback lengths with fixed mean and variance