The lattice of database states

State transition diagram

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 S0. Site A generates and applies operation O1 and transitions to state S1. Site B concurrently generates and applies operation O2 and transitions to state S2. Each site sends its operation to the other site. The received operation is transformed and applied and both sites enter state S3.

State Transition Diagram

Correspondence between states and sets of operations

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.

States Are Sets Of Operations

Correspondence between paths and lists of operations

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.

Paths Are Lists Of Operations

State transition diagram is the Hasse diagram of subset

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.

State Transition Diagram Is The Hasse Diagram

When there are three concurrent operations we get a cube.

Hasse Diagram Of Three Concurrent Operations

Note that the powerset (set of all subsets) of {O1 O2 O3} has 8 elements:

P = { {} {O1} {O2} {O3} {O1 O2} {O1 O3} {O2 O3} {O1 O2 O3} }

Vector time

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 { a1 a2 b1 c1 }. 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

Vector Time

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

v[i] = ith component of vector time v = number of operations generated by site i in the state associated with v

Let v1, v2 be vector times. We define a partial order (≤) on vector times as follows:

v1 ≤ v2 ⇔ ∀i v1[i] ≤ v2[i] ⇔ (set of operations of v1) ⊆ (set of operations of v2)

For more information see the Vector clock Wikipedia article.

Intersection of two states

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.

Intersection Of States

Union of two states

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

Union Of States

Meet and join of vector times

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

Join And Meet Of Vector Times

Precedes relation

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

In the following diagram operations a1 and b1 precede a2 because both a1 and b1 had been applied on site A at the time a2 was generated on site A.

Precedes

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

The precedes relation is not a total order, in fact we write O1||O2 when O1 and O2 are concurrent, meaning neither O1→O2 nor O2→O1.

For more information see the Happened-before Wikipedia article.

Analogy to special relativity

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.

Special Relativity Light Cone

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

Don’t confuse the two posets

Consider the following example where there are two sites:

Precedes

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.

Two Posets

More complicated example

This is a more complicated example.

More Complex Example

The state transition diagram for this example is shown below.

Causality Preservation

Causality preservation requires the following condition to be met:

If O1→O2 then O1 is applied before O2 at all sites

In this diagram a1 and b1 both precede a2. Causality preservation requires that both a1 and b1 be applied before a2 at all sites. So there is no point sending a2 to site C before sending a1 and b1.

Causality Preservation

States that preserve causality

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

S preserves causality ⇔ (O2∈S ∧ (O1→O2 ⇒ O1∈S))

The vector time shown in red doesn't preserve causality because there's an operation in its future b2 which precedes an operation a3 in its past

States That Preserve Causality

The states that preserve causality form a bounded lattice

It can be proven that the states which preserve causality are closed over intersection and union. In other words, let S1 and S2 be states then

(S1 and S2 preserve causality) ⇒ (S1∪S2 and S1∩S2 preserve causality)

S1∪S2 is the smallest set which contains both S1 and S2 so it's the supremum. S1∩S2 is the largest set contained by both S1 and S2 so it's the infimum.

Sup And Inf Of States

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.

Lattice Of States

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).

Paths through the lattice

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.

Paths Through Lattice

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

i.e. (O1→O2) ⇒ (O1 appears before O2 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 27 = 128 states, there are only 24 states.