Rollback-dependency trackability
Roberto Baldoni, Jean-Michel Hélary, Michel Raynal · 1999
When we consider an asynchronous distributed computation on which local checkpoints have been defined (namely, a communication and checkpoint pattern -in brief, CCP), two types of dependencies between its local checkpoints can be observed.The first type is due to causal sequences of messages that establish on-line trackable dependencies.The second type is due to noncausal sequences of messages (called Z-paths) that establish "hidden" dependencies between local checkpoints (a dependency is "hidden" if it can not be tracked online).The Rollback Dependency Trackability (RDT) property, defined by Y.-M.Wang, has been introduced to study CCPs.A CCP satisfies the RDT property if every pair of local checkpoints that are connected by a "hidden" dependency are also connected by a causal sequence of messages.The RDT property has a great interest: CCPs that satisfy this property allow relatively simple solutions to a lot of practical problems.This paper first introduces the notion of RDT-compliant property.In a given CCP, an X-path is a Z-path that satisfies a property X.The property X is RDT-compliant if every CCP without X-paths satisfies the RDT property.Then, the paper presents a particular RDT-compliant property.This property enjoys several very interesting features.(1) It is "visible" (i.e., it can be tested on-line).(2) It is stronger than previously known RDT-compliant properties.Consequently, this property provides a characterization of RDT better than the previous ones.The question of the minimal characterization of the RDT property is finally investigated.1 Introduction Long running scientific applications and service providing facilities use rollback-recovery techniques to increase their fault tolerance and their availability.This is done by saving onto stable storage the state of processes (i.e., Permission to make digital or hard copies of all or part ofthis work for personal or c~assroon~ use is granted without fee provided that copies arc not made or distrihutcd for protit or commercial advantage and that copies bear this notice and the full citation 011 the first page.'I'0 copy other&c.to republish, to post on servers or to redistribute to lists.