Ninth Pacific Rim International Symposium on Dependable Computing (PRDC'02)
On Characteristics of DEF Communication-Induced Checkpointing Protocols
Tsukuba, Japan
December 16-December 18
ISBN: 0-7695-1852-4
Domino-Effect Freedom (DEF)is a property stating that unbounded, cascading rollback propagation will not occur during the process of ?nding a consistent global checkpoint. DEF checkpointing protocols can be classi?ed into two different categories: index-based and model-based. An index- based protocol timestamps local checkpoints with sequence numbers for achieving consistency,while a model-based one prohibits the formation of particular checkpoint and communication patterns in the execution. In this paper, we explore several characteristics of communication-induced checkpointing protocols with the DEF property. First, we will demonstrate that there is no optimal on-line scalar DEF protocol, in terms of the number of forced check- points.Then some techniques for comparing protocols are proposed. We will construct some patterns or give formal proofs to compare the performance of both index-based and model-based protocols.