Global Snapshots: Review
Answer these questions to review the webpage on the global snapshot
algorithm.
-
What can agents in a distributed operating system do?
-
The global snapshot algorithm uses messages called markers. Are
these messages visible to clients of the distributed OS?
-
What is a global snapshot? How is it different from a local
snapshot?
-
Show how the global snapshot rule follows from properties of cuts.
-
Consider a system consisting of two agents \(x\) and \(y\) and
channels in both directions between them. What is the sequence of
actions of the global snapshot algorithm if (i) only \(x\)
initiates the algorithm and (ii) both \(x\) and \(y\) initiate the
algorithm? Are the snapshots necessarily identical? Necessarily
different?
-
Let's look at the system in the previous question.
Suppose an invariant of the system is that there is always a
message in the channel \((x, y)\).
If \(x\) initiates the algorithm and
\(y\) takes its local snapshot when it receives a marker from
\(x\) then the state of channel \((x, y)\) recorded by the
algorithm is the empty sequence.
Isn't that an error because the invariant tells us that the state
of the channel cannot be the empty sequence?
Next
Next,
strategies for developing
algorithms that use global snapshots and examples of
applications of global snapshots and cuts.
A code skeleton of the algorithm and examples of the global snapshot
algorithm
are provided here.
Frequently Asked Questions
Review
K. Mani Chandy,
Emeritus Simon Ramo Professor,
California Institute of Technology