Exercise 12: Show that S is reachable from S0 and that S1 is reachable from S.

[dag7dev]

Exercise 12: Let $S_0$ be the global state when the Chandy-Lamport snapshot protocol starts, $S$ be the global state built by the protocol, and $S_1$ be the global state when the protocol ends. Show that $S$ is reachable from $S_0$ and that $S_1$ is reachable from $S$. Remember that $S$ might not have happened.

[susannacifani]

The solution on Drive doesn't include "Remember that S might not have happened.".
$S_0$: the first take snapshot message is sent
$S$: each process receives the "take snapshot" message and sends it to all other processes
$S_1$: the protocol ends
How can $S$ not happen and still reach $S_1$ from $S_0$? I didn't get it, it's not possible to directly reach $S_1$ from $S$

The solution on Drive:
$S_0$ is the state in which the first "take snapshot" message is sent.
From $S_0$ we reach $S$ when the "take snapshot" message is received by every process.
Then, we reach $S_1$ from $S$ when every process sends the "take snapshot" message to each
other.

[simonesestito]

I had the following idea. Maybe it's too complex, so improvements are welcome - of course.

We know that $S_0$ and $S_1$ really happened in that run.

Between them, a series of events happened, not necessarily passing through $S$ but we know it is consistent.

These events are in some order, and we may want to have them as follows: all events that are in $S$ followed by the remaining.

Whenever we see 2 events $e$ and $e'$ such that $e$ is before $e'$ (in the current run) and only the second one is $S$, we swap them.

Can we?
Yes, because under the assumption that $S$ is consistent, it cannot happen that $e \rightarrow e'$. So swapping them still keeps the run consistent.

After reordering, we pass through all of the 3 states we want.

[Lorenzoantonelli]

I had the following idea. Maybe it's too complex, so improvements are welcome - of course.

We know that S0 and S1 really happened in that run.

Between them, a series of events happened, not necessarily passing through S but we know it is consistent.

These events are in some order, and we may want to have them as follows: all events that are in S followed by the remaining.

Whenever we see 2 events e and e′ such that e is before e′ (in the current run) and only the second one is S, we swap them.

Can we? Yes, because under the assumption that S is consistent, it cannot happen that e→e′. So swapping them still keeps the run consistent.

After reordering, we pass through all of the 3 states we want.

In my opinion, this is perfectly fine: the idea is clear, and it's the correct answer to this exercise, not the one in Drive.

[rotiroti]

I believe the solution provided by @simonesestito is a good start, but it lacks an explanation on some crucial points, for example:

• Order of the events
• How the events are swapped?
• How the consistency is guaranteed after the reordering of the events?

Here you can find a solution based on "Reachability between States in the Snapshot Algorithm" (pages 618-619) [1]

Assume the system went through the sequence of events $Sys = e_0, e_1, \dots$ in transitioning from the initial global state $S_0$ to the final global state $S_1$. Our objective is to find a permutation of $Sys$ called $Sys'$ that satisfies the following criteria:

• Contains all three global states: $S_0$, $S$, and $S_1$.
• Preserves the happens-before relationship among the events in $Sys$.

Let's categorize the events in $Sys$ as follows:

• Pre-snapshot events: These events occurred before the respective process, in which the event occurred, recorded its state.
• Post-snapshot events: All other events.

Consider the following scenario: $e_j$ is a post-snapshot event at one process, and $e_{j+1}$ is a pre-snapshot event at another process. It cannot be the case that $e_j \to e_{j+1}$, as otherwise they would represent the send and receive of the same message, and in such a case, they would either both be post-snapshot events or both be pre-snapshot events.

Thus, there is no causal relation between these two events, and they can be swapped without violating the happens-before relationship.

By swapping such pairs of events, we can reorganize the sequence so that all pre-snapshot events appear at the beginning, and all post-snapshot events appear at the end. Consequently, the pre-snapshot events are denoted as $e_0',e_1',\dots, e_{R-1}'$, and the post-snapshot events are represented as $e_R', e_{R+1}', \dots, e_N'$.

Since this rearrangement does not affect the initial state $S_0$ or the final state $S_1$, we have successfully established the reachability relationship. The permutation $Sys'$ ensures that we can reach the intermediate global state $S$ from $S_0$ and that we can further reach the final state $S_1$ from $S$ while preserving the happens-before relationship.

References:

[1] Coulouris, G. F., Dollimore, J., Kindberg, T., Blair G. (2012). Distributed systems: concepts and design. Pearson Education.
[2] Chandy, K. M., & Lamport, L.. (1985). Distributed snapshots: determining global states of distributed systems. 3(1), 71–73. https://doi.org/10.1145/214451.214456
[3] Babaoglu, O., & Marzullo, K. (1993). Consistent global states of distributed systems: Fundamental concepts and mechanisms. Distributed systems, 53.

[lor3ny]

The previous solution is good and related to the question of consistent cut reachability, but it doesn't mention the last sentence of the exercise "Remember that $S$ might not have happened". I can't understand why $S$ might not happen.