CloudComputing

1.Suppose Chandy and Lamport’s distributed snapshot algorithm is initiated by process p1 just after event e1 in the following computation

• • Sketch how markers would be
  • Which events are included in the set H?
  • Which state components are noted down in the various processes, as the execution of the algorithm proceeds?
  • Which global state S is discovered by the algorithm in exchanged during the execution of the algorithm in this case.

Chandy-Lamport algo. determines a consistent cut

Let e_i & e_j be events occurring at p_i & p_j, respectively such that e_i à e_j

The snapshot algorithm ensures that

• if e_j is in the cut then e_i is also in the cut.
• if e_j à “p_j records its state”, then it must be true that e_i à “p_i records its state”.

Why?