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.
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.
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.
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.
When there are three concurrent operations we get a cube.
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
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 wikipedia article on vector clocks [
].
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.
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.
Meet and join of vector times
There are corresponding operations on vector times involving taking the minimum/maximum over the components.
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.
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 O1||O2 when O1 and O2 are concurrent, meaning neither O1→O2 nor O2→O1.
For more information see the wikipedia article on the happened before relation [].
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.
[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:
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.
More complicated example
This is a more complicated 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.
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
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.
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).
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.
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.