Terminology - History, Run, Local State, Global state, and Cut

• History of a certain process $P_1$: $h_1=e_1^1{e}_1^2{e}_1^3...$ the sequence of events that occur inside that process;
• Run or computation is a sequence of events $R=e_1^1{e}_2^2{e}_2^3{e}_1^3$.

A run can be legal or consistent if it can actually be run in the system, illegal or not consistent otherwise;

• Local state ${\sigma }_i^k$ is the state of the process $i$ after the execution of the first $k$ events. (first $k$ events are $h^k=e_h^1\dots e_h^k$);
• Global state: the execution of the first $n$ local states (${\sigma }_1^k,{\sigma }_2^k,\dots ,{\sigma }_n^k$). A global state is consistent if $e\to e^{\prime }\wedge e\in S\Rightarrow e^{\prime }\in S$;
• Cut: a subset of the history of the computation (subset of $h_1^{k_1},h_2^{k_2},\dots ,h_n^{k_n}$);

We say that an event “happened before” with the notation $\to$ (this operator is transitive)

• $e_i^l\to e_i^k$ if $l<k$ ($i$ is the same so we’re in the same process)
• $e_i\to e_j$ if $e_1$ is sending the message $m$ and $e_j$ is receiving the same message $m$

Consistent cut: a cut $C$ is consistent if and only if: $e\to e’\wedge e’\in C\Rightarrow e\in C$. If a cut is consistent, a consistent run surely exists.