Optimal Asynchronous Garbage Collection for RDT Checkpointing Protocols
Communication-induced checkpointing protocols that ensure rollback-dependency trackability (RDT) guarantee important properties to the recovery system without explicit coordination. However, to the best of our knowledge, there was no garbage collection algorithm for them which did not use some type of process synchronization, like time assumptions or reliable control message exchanges. This paper addresses the problem of garbage collection for RDT checkpointing protocols and presents an optimal solution for the case where coordination is done only by means of timestamps piggybacked in application messages. Our algorithm uses the same timestamps as off-the-shelf RDT protocols and ensures the tight upper bound on the number of uncollected checkpoints for each process during all the system execution.
- View record in Web of Science
Also published as a Brief Announcement in the Proceedings of the 23rd Symposium on Principles of Distributed Computing (PODC'2004).
Record created on 2006-05-10, modified on 2016-08-08