In the Time-Warp synchronization model, the processes must occasionally interrupt execution in order to reclaim memory space used by state and event histories that are no longer needed (fossil-collection). Traditionally, fossil-collection techniques have required the processes to reach a consensus on the Global Virtual-Time (GVT) - the global progress time. Events with time-stamps less than GVT are guaranteed to have been processed correctly; their histories can be safely collected. This paper presents Optimistic Fossil-Collection (OFC), a new fossilcollection algorithm that is fully distributed. OFC uses a local decision function to estimate the fossilized portion of the histories (and optimistically collects them). Because a global property is estimated using local information only, an erroneous estimate is possible. Accordingly, OFC must also include a recovery mechanism to be feasible. An uncoordinated distributed checkpointing algorithm for Time-Warp that is domino-effect free and lighweight is used. We show that, in addition to eliminating the overhead for GVT estimation, OFC has several desireable memory-management properties.
展开▼