Performance benefits of optimism in fossil collection

Each process in a time-warp parallel simulation requires a time-varying set of state and event histories to be retained for recovering from erroneous computations. Erroneous computation is discovered when straggler messages arrive with time-stamps in the process´s past. The traditional method of determining the set of histories to retain has been through the estimation of a global virtual time (GVT) for the distributed simulation. A distributed GVT calculation requires an estimation of the global progress of the simulation during a real-time interval. Optimistic fossil collection (OFC) predicts a bound for the needed histories using local information, or previously collected information, that enables the process to continue. In most cases, OFC requires less communication overhead and less memory usage, and estimates the set of committed events faster. These benefits come at the cost of a possible penalty of having to recover from a state history that was incorrectly fossil-collected (an OFC fault). Sufficiently lightweight checkpointing and recovery techniques compensate for this possibility while yielding good performance. In this paper, the requirements of an OFC-based simulator (algorithm has been implemented in the WARPED time-warp parallel discrete-event simulator) are detailed along with a presentation of results from an OFC simulation. Performance statistics are given comparing the execution time and required memory usage of each logical process for different fossil collection methods.