Given a scenario of some sites exchanging operations there is an associated **state transition diagram**.
In the case of two sites exchanging two concurrent operations the state transition diagram is a diamond.

In the following diagram there are two sites A and B that are initially in the same state S_{0}. Site A
generates and applies operation O_{1} and transitions to state S_{1}. Site B concurrently generates and
applies operation O_{2} and transitions to state S_{2}. Each site sends its operation to the other site.
The received operation is transformed and applied and both sites enter state S_{3}.

Each **state** can be labelled with the **set of operations** producing that state, so there is a one to one
correspondence between states and sets of operations in the state transition diagram.

A **list of operations** corresponds to a **path** through the state transaction diagram. In the diamond there
are two paths (along the top and along the bottom), corresponding to the two permutations of a list with
two elements.

It has already been pointed out that there is a one to one correspondence between states and sets of operations. The subset operation on the sets of operations gives a partial order on the states (see partially ordered set).

The Hasse diagram of the subset relation corresponds to what we have previously described as the state transition diagram.

When there are three concurrent operations we get a cube.

Note that the powerset (set of all subsets) of {O_{1} O_{2} O_{3}} has 8 elements:

P =
{
{}
{O_{1}}
{O_{2}}
{O_{3}}
{O_{1} O_{2}}
{O_{1} O_{3}}
{O_{2} O_{3}}
{O_{1} O_{2} O_{3}}
}

A **vector time** identifies a database state by identifying the **set of operations** producing that state. In the
following diagram the vector time (2,1,1) identifies the set of operations { a_{1} a_{2} b_{1} c_{1} }.
If we think of the operations as events then a vector time is like a time stamp in the way it separates past and future events

A vector time is a multi-dimensional notion of time and is only partially ordered. Let i be a site identifier.

v[i] = i^{th} component of vector time v
= number of operations generated by site i in the state associated with v

Let v_{1}, v_{2} be vector times. We define a partial order (≤) on vector times as follows:

v_{1} ≤ v_{2} ⇔ ∀i v_{1}[i] ≤ v_{2}[i]
⇔ (set of operations of v_{1}) ⊆ (set of operations of v_{2})

For more information see the Vector clock Wikipedia article.

The intersection of two states means the operations in common (shown here in green) and corresponds to a green dotted line which "cuts" down through the left of the "cuts" of the two given states.

Similarly the union of two states corresponds to a cut down through the right of the cuts of the two states.

There are corresponding operations on vector times involving taking the minimum/maximum over the components.

There is a concept of an operation happening before another operation. We say O_{1} precedes O_{2} (and
write this as O_{1}→O_{2}) if O_{1} had been applied on the site where O_{2} was generated.

In the following diagram operations a_{1} and b_{1} precede a_{2} because both
a_{1} and b_{1} had been applied on site A at the time a_{2} was generated on site A.

The precedes relation is a strict partial order on the operations:

- → is irreflexive
- → is asymmetric
- Causality preservation implies → is transitive

The precedes relation is not a total order, in fact we write O_{1}||O_{2} when O_{1} and O_{2} are concurrent,
meaning neither O_{1}→O_{2} nor O_{2}→O_{1}.

For more information see the Happened-before Wikipedia article.

If one considers operations to be events that occur in space and time, then the precedes relation is
analogous to the partial order on events in special relativity. In relativity events can only affect
events on or inside its future light cone. Events that are not in each other’s light cone are
**space like** and are not comparable.

[Image by K. Aainsqatsi CC BY-SA 3.0, Link]

Consider the following example where there are two sites:

There are two different posets which are being discussed. On the left are the operations partially ordered by the precedes relation and on the right are the states/vector times/sets of operations partially ordered by the subset relation. The Hasse diagram on the right is the state transition diagram.

This is a more complicated example.

The state transition diagram for this example is shown below.

Causality preservation requires the following condition to be met:

If O_{1}→O_{2} then O_{1} is applied before O_{2} at all sites

In this diagram a_{1} and b_{1} both precede a_{2}.
Causality preservation requires that both a_{1} and b_{1}
be applied before a_{2} at all sites. So there is no point sending a_{2} to site C before sending a_{1} and b_{1}.

There's a corresponding definition of the states which preserve causality:

S preserves causality ⇔ (O_{2}∈S ∧ (O_{1}→O_{2} ⇒ O_{1}∈S))

The vector time shown in red doesn't preserve causality because there's an operation in its future
b_{2} which precedes an operation a_{3} in its past

It can be proven that the states which preserve causality are closed over intersection and union.
In other words, let S_{1} and S_{2} be states then

(S_{1} and S_{2} preserve causality)
⇒
(S_{1}∪S_{2} and S_{1}∩S_{2} preserve causality)

S_{1}∪S_{2} is the smallest set which contains both S_{1} and S_{2} so it's the supremum.
S_{1}∩S_{2} is the largest set contained by both S_{1} and S_{2} so it's the infimum.

The existence of the infimum and supremum means the states that preserve causality form a mathematical structure called a lattice. This is shown in the lower part of the picture below having 5 cubes plus a flat face for this particular scenario with three sites.

This lattice has 24 vertices (i.e. vector times or states or sets of operations) which correspond to 24 different cuts in the top picture (only three are shown with green dotted lines). The red vector time doesn't preserve causality and therefore doesn't correspond to a point on the lattice in the picture below.

Site A is applying operations in a particular order and this corresponds to one of the paths (the one drawn in orange) which is zig-zagging its way though the lattice, starting at (0,0,0).

A path through the lattice is defined by an ordered list of operations. In the following diagram two alternative paths are shown in red and green.

Causality preservation implies the total order respects the partial order defined by the precedes relation.

i.e. (O_{1}→O_{2}) ⇒ (O_{1} appears before O_{2} in every list)

Even though there are 7 operations in this example, there are not 7!=5040 paths through the lattice because the great majority of them break causality. There are 12+40+40+6+12+4 = 114 paths which can be taken by a site, depending on the order in which it receives the operations. These are the permutations of the 7 operations which respect the partial order given by the precedes relation.

Note as well that there are not 2^{7} = 128 states, there are only 24 states.