Lesson

Question 1

What happens when Process P2 fails before logging the determinant for message m5?

Answer 1

Process P1 becomes an orphan because it had already processed m6 which depended on m5.

This leads to cascading rollbacks in P1 and P0.

Question 2

What is the role of causal dependencies in recovery from failures?

Answer 2

The system tracks causal dependencies to restore a globally consistent state.

Question 3

How does Communication-Induced Checkpointing work?

Answer 3

It piggybacks protocol-related information on each application message, allowing the receiver to decide if it needs a forced checkpoint.

Question 4

What are the two types of checkpoints in Communication-Induced Checkpointing?

Answer 4

• Autonomous Checkpoints
• Forced Checkpoints

Question 5

What are the advantages of Communication-Induced Checkpointing?

Answer 5

Avoids cascading rollbacks without requiring full coordination and balances overhead between uncoordinated and coordinated approaches.

Question 6

What is a disadvantage of Communication-Induced Checkpointing?

Answer 6

Can introduce unnecessary checkpoints, increasing storage and processing costs.

Question 7

What is the main difference between Blocking and Non-Blocking approaches in Coordinated Checkpointing?

Answer 7

Blocking: Processes pause execution during checkpointing. Non-blocking: Processes continue execution while coordination happens.

Question 8

What are the two types of Communication-Induced Checkpointing?

Answer 8

• Model-Based Checkpointing
• Index-Based Checkpointing

Question 9

What is Log-based rollback recovery?

Answer 9

A fault-tolerance mechanism where processes log events and messages during execution to replay them after a failure.

Question 10

What is Pessimistic Logging?

Answer 10

Logs every nondeterministic event before execution to ensure recovery is always possible.

Question 11

What are the pros and cons of Pessimistic Logging?

Answer 11

• Pros: Fast recovery, no dependency tracking
• Cons: High runtime overhead due to frequent logging.

Question 12

What is Optimistic Logging?

Answer 12

Logs events asynchronously, allowing execution to proceed without waiting for logs to be written.

Question 13

What are the pros and cons of Optimistic Logging?

Answer 13

• Pros: Low overhead during normal execution
• Cons: May require rollback of multiple processes due to dependency tracking.

Question 14

What is Causal Logging?

Answer 14

Logs events based on causality tracking between processes to ensure only dependent processes rollback together.

Question 15

What are the characteristics of a log-based rollback recovery system?

Answer 15

• Relies on Piecewise Deterministic (PWD) Assumption
• Logs nondeterministic events
• Recovery process restores a previous checkpoint and replays logged events.

Question 16

What are orphan messages?

Answer 16

Messages with receive recorded but message send not recorded, often due to rollbacks.

Question 17

What are duplicate messages?

Answer 17

Messages that arise due to logging and replaying during process recovery.

Question 18

What are lost messages?

Answer 18

Messages whose send is not undone but receive is undone due to rollback.

Question 19

What are delayed messages?

Answer 19

Messages whose receive is not recorded because the receiving process was either down or the message arrived after the rollback.

Question 20

What is the domino effect in uncoordinated checkpointing?

Answer 20

A failure may require rolling back multiple checkpoints, leading to inefficiency.

Question 21

What is the Koo-Toueg coordinated checkpointing algorithm?

Answer 21

A technique that takes a consistent set of checkpoints to avoid domino effect and livelock problems during recovery.

Question 22

What are the two kinds of checkpoints in the Koo-Toueg algorithm?

Answer 22

• Permanent checkpoint
• Tentative checkpoint

Question 23

What is the purpose of optimistic logging protocols?

Answer 23

To track causal dependencies during failure-free execution without synchronous access to stable storage.

Question 24

What is the always-no-orphans property in logging?

Answer 24

Ensures that no process becomes an orphan if another fails.

Question 25

What do pessimistic logging protocols require?

Answer 25

A non-trivial garbage collection scheme

Question 26

What do pessimistic protocols need to keep?

Answer 26

Only the most recent checkpoint of each process

Question 27

What do optimistic protocols need to keep?

Answer 27

Multiple checkpoints for each process

Question 28

What is a characteristic of pessimistic logging?

Answer 28

Assumes a failure can occur after any non-deterministic event

Question 29

True or False: In reality, failures are common.

Answer 29

False

Question 30

What does the predicate Stable(e) indicate?

Answer 30

True if e’s determinant is logged on stable storage

Question 31

What does the no-orphans consistency condition state?

Answer 31

If e is not stable, then Depend(e) must be a subset of Log(e)

Question 32

What is the Juang-Venkatesan algorithm used for?

Answer 32

Asynchronous checkpointing and recovery

Question 33

Describe the rollback recovery algorithm.

Answer 33

Restores the system state to a consistent state after a failure

Question 34

What are the two phases of the rollback recovery algorithm?

Answer 34

* Initiating process sends a message to all processes for preferences * Final decision sent to all processes to act accordingly

Question 35

What is an optimization in the rollback recovery protocol?

Answer 35

Not all processes need to roll back if they did not change anything

Question 36

What assumptions does the Juang-Venkatesan algorithm make?

Answer 36

* Communication channels are reliable * Messages delivered in FIFO order * Infinite buffers * Message transmission delay is arbitrary but finite

Question 37

What does the Piecewise Deterministic (PWD) assumption state?

Answer 37

Execution consists of deterministic state transitions interrupted by nondeterministic events

Question 38

What are the two types of log storage maintained in the Juang-Venkatesan algorithm?

Answer 38

* Volatile log * Stable log

Question 39

What is the domino effect in checkpointing and recovery?

Answer 39

A chain reaction of failures during recovery that leads to system inconsistency

Question 40

Define checkpoints in the context of rollback recovery.

Answer 40

The saved states of a process

Question 41

What does rollback propagation refer to?

Answer 41

Dependencies may force non-failed processes to roll back

Question 42

What are in-transit messages?

Answer 42

Messages that have been sent but not yet received

Question 43

What are orphan messages?

Answer 43

Messages with 'receive' recorded but 'send' not recorded

Question 44

What is a consistent global state?

Answer 44

A global state that may occur during a failure-free execution

Question 45

What is a global checkpoint?

Answer 45

A set of local checkpoints, one from each process

Question 46

What defines a consistent global checkpoint?

Answer 46

No message is sent by a process after taking its local point that is received by another process before taking its checkpoint

Question 47

What is an inconsistent global checkpoint?

Answer 47

Includes a message receipt event without the corresponding send event

Question 48

True or False: A consistent state occurs if every message received has a corresponding send event.

Answer 48

True