Portal de Periódicos da CAPES

OFC: A distributed fossil-collection algorithm for Time-Warp

1998; Springer Science+Business Media; Linguagem: Inglês

10.1007/bfb0056498

1611-3349

Christopher H. Young, Nael Abu‐Ghazaleh, Philip A. Wilsey,

Data Management and Algorithms

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 fossil-collection 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 lightweight is used. We show that, in addition to eliminating the overhead for GVT estimation, OFC has several desireable memory-management properties.