Chandy - Lamport

Question 1

What is the purpose of Chandy and Lamport’s algorithm?

Answer 1

Snapshot’ algorithm for determining global states of a distribued system:

Records a set of process and channel states (a snapshot) such that the recorded global state of each snapshot is consistent

Question 2

What is the essential idea of the algorithm?

Answer 2

Each process records (a) its state and (b) for each incoming channel a set of messages sent to it.

Question 3

If pi has sent message m to pj before recording its state, but pj has not received it, what does m account to?

Answer 3

we account for m as belonging to the state of the channel between them

Question 4

How does the algorithm start?

Answer 4

Algorithm kicks-off by a process acting as though it has received a marker
over a non-existent channel (invoke marker receiving rule)

Question 5

Name the two algorithm rules.

Answer 5

receiving and sending

Question 6

State the receiving part of the algorithm

Answer 6

Marker receiving rule for process pi

1. On pi’s receipt of a marker message over channel c:
   
   1. 1 if (pi has not yet recorded its state) it :
2. 1.1 records its process state;
3. 1.2 records the state of c as the empty set;
4. 1.3 turns on recording of messages arriving over other incoming channels;
5. 2 else
6. 2.1 pi records the state of c as the set of messages it has received over c since it saved its state.
7. 3 end if

Question 7

State the sending part of the algorithm

Answer 7

After pi has recorded its state, for each outgoing channel c:

pi sends one marker message over c
(before it sends any other message over c).

Question 8

What assertions does the Snapshot algorithm allow?

Answer 8

Snapshot algorithm captures consistent global state and allows assertions about whether stable predicates hold in the actual execution