Exercise 3: Show that every consistent global state can be reached by some run.

[dag7dev]

Exercise 3: Show that every consistent global state can be reached by some run.

[dag7dev]

From "Consistent Global States of Distributed Systems" by Ozalp Babaoglu and Keith Marzullo

A run $R$ is said to be consistent if for all events, $e \rightarrow e'$ implies that $e$ appears before $e'$ in R.

A run $R = e^1 e^2...$ results in a sequence of global states $\Sigma^0 \Sigma^1\Sigma^2...$ where $\Sigma^0$ denotes the initial global state $\sigma^0_1...\sigma^0_n$

If the run is consistent, then the global states in the sequence will all be consistent as well.

We will use the term "run" to refer to both the sequence of events and the sequence of resulting global states.

Each (consistent) global state $\Sigma^i$ of the run is obtained from the previous state $\Sigma^i$ by some process executing the single event $e^i$ .

For two such (consistent) global states of run R, we say that $\Sigma^{i-1}$ leads to $\Sigma^i$ in $R$.

Let $\rightsquigarrow R$ denote the transitive closure of the leads-to relation in a given run R.

We say that $\Sigma'$ is reachable from $\Sigma$ in run $R$ if and only if $\Sigma \rightsquigarrow_{R} \Sigma'$ .

We drop the run subscript if there exists some run in which $\Sigma'$ is reachable from $\Sigma$ .

[susannacifani]

Let’s assume we have a consistent global state $S$, that means that $S$ respects all the rules of the system.
If we start from the initial state and follow a run that respects the system's rules, we will eventually reach a consistent global state $S$ because the initial state is consistent, and the system's rules are consistent.
Therefore, every consistent global state can be reached by some run in the system.

[rotiroti]

Solution (Proof by Induction)

To show that every consistent global state can be reached by some run, we can use induction on the number of events in the global state.

• Base case: If the global state has no events, then the empty run is a run that reaches this state.

• Inductive step: Assume that every consistent global state with $n$ events can be reached by some run. Let $S$ be a consistent global state with $n+1$ events. Let $e$ be the last event in $S$. Let $S'$ be the consistent global state obtained by removing $e$ from $S$. By the induction hypothesis, there is a run $R$ that reaches $S'$. We can extend $R$ to a run that reaches $S$ by adding $e$ to the end of $R$. Since $e$ is the last event in $S$, it does not violate the happened-before relation with any other events in $S$. Therefore, the extended run is a valid run that reaches $S$.

[susannacifani]

Solution (Proof by Induction)

To show that every consistent global state can be reached by some run, we can use induction on the number of events in the global state.

• Base case: If the global state has no events, then the empty run is a run that reaches this state.
• Inductive step: Assume that every consistent global state with $n$ events can be reached by some run. Let $S$ be a consistent global state with $n+1$ events. Let $e$ be the last event in $S$. Let $S'$ be the consistent global state obtained by removing $e$ from $S$. By the induction hypothesis, there is a run $R$ that reaches $S'$. We can extend $R$ to a run that reaches $S$ by adding $e$ to the end of $R$. Since $e$ is the last event in $S$, it does not violate the happened-before relation with any other events in $S$. Therefore, the extended run is a valid run that reaches $S$.

ChatGPT says that this solution is correct. In my opinion, it is also correct