Rollback and Recovery:

Checkpoint Algorithm | Rollback Algorithm | Oral Message Algorithm

• Idea
  • have a consistent set of checkpoints for the entire system
  • decide on whether to take a checkpoint or not

• Questions ?
  • When to take a checkpoint ?
  • Who else should take a checkpoint ?

• Entities in the system
  • originator - the process which wants to take a checkpoint
  • cohort - the process which communicates with the originator

• Steps of the Algorithm
  • Originator sends a message to all its cohorts to take a tentative checkpoint
  • Role reversal: Cohort = Originator
    
    sends a message to each of its cohorts
  • cohort agrees(yes)/disagrees(no)
    
    • complete agreement: originator receives "yes" from all cohorts. Originator sends a new message to take final checkpoint
    • disagreement:originator receives "no" from some cohort(s). Originator sends a new message to ignore the tentative checkpoint

• Optimization
  • all processes need not have to take checkpoints
  • achieved by use of labels

To the top

• Similar to checkpoint algorithm

• Questions
  • when ?
  • who ?
  • who else ?

• Algorithm works similar to checkpoint algorithm

• Optimization is achieved by labels

To the top

• Discussed example: n = 7, m = 2

• Complexity!!!
  increases with n and m

• Order of the algorithm: n^m

• Each process will have to handle a lot of messages before a decision is reached

To the top | To Class Home

Rekha-Rukmini S. Kengeri

Comments?