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.


Published in:
Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS 2005), 167-176
Presented at:
25th International Conference on Distributed Computing Systems (ICDCS'2005), Columbus, Ohio, USA, June 2005
Year:
2005
Keywords:
Note:
Also published as a Brief Announcement in the Proceedings of the 23rd Symposium on Principles of Distributed Computing (PODC'2004).
Laboratories:




 Record created 2006-05-10, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)