6 - Checkpointing

Question 1

Explain what a cut is

Answer 1

A cut C is a set consisting of one internal event for every process:
C = {c 1,c 2,…,c n} with c i an internal event in P i, i = 1,2,…,n

Question 2

How can you calculate wethere a cut is consistent?

Answer 2

Calculate V(C) as the maximum values for i in n. The cut C is consistent iff V(C) = ( V(c1)[1], V(c 2)[2], …,V(c n)[n] ) (the current value of each processor’s cut)

Question 3

Why is tracking the state of a channel important?

Answer 3

There could be value inside messages currently in channels, that is not accounted for by only checking the state of the nodes. For instance, making a screenshot of your bank account before salary gets deposited is not a fair depiction.

Question 4

Please explain how the state of the channel can be composed.

Answer 4

If we assume FIFO channel, and that P1 sends to P2. If k > 0 messages has been send before P1 records its state, and P2 receives 0 < l <= k messages, then all the messages between #l and #k are unaccounted for. So the state of the channel is [mk, … , m l+1]

Question 5

What are the assumptions for recording the state of a channel?

Answer 5

• Channels are unidirectional, fault-free and FIFO
• Channels have infinite capacity
• State of a channel is a sequence of consecutive messages
• Every process may spontaneously start the algorithm for
  recording the global state
• The directed graph of processors and unidirectional channels must be strongly connected

Question 6

Explain how Chandy and Lamport’s Algorithm works.

Answer 6

procedure record_local_state:
1. record local state
2. for every outgoing channel c : send marker along c
3. for every incoming channel c create message queue Q(c)

Upon receiving a marker:
If not already local state recorded: regard c as empty and record local state.
Else record state of Q(c)

Question 7

What does Chandy and Lamports algorithm solve?

Answer 7

It tries to save the state of a system (nodes and channels)

Question 8

What is the use of the recorded state?

Answer 8

It is a state that might have occurred if the sequence of events would have been different