Phenomenon G-nonadjacent, or Non-adjacent Anti-dependency Cycle, is Jepsen’s term for one type of G2: a dependency cycle involving read-write edges. Specifically, G-nonadjacent is a dependency cycle made up of any number of write-write and write-read edges, and at least one read-write edge (also known as an anti-dependency) and no two read-write edges are adjacent to one another.

For example, imagine a history of four transactions over integer registers: T₁, T₂, T₃, and T₄.

• T₁ writes x = 1.
• T₂ reads x = 1. It reads y, and finds that y does not yet exist.
• T₃ inserts y = 3.
• T₄ performs a predicate read of all objects, and observes just y = 3.

T₂ write-read depends on T₁ because it observed T_1’s write of x = 1. T₃ read-write depends on T₂, because T₂ observed the unborn version of y just prior to T₃’s write. T₄ write-read depends on T₃, because it observed T₃’s write of y = 3. Finally, T₄’s predicate read did not observe T₁’s write of x = 1, so T₁ read-write depends on T4. We have a cycle: write-read, read-write, write-read, read-write. No two read-write edges are adjacent, making this G-nonadjacent.¹

G-nonadjacent is somewhat unintuitive, but it is of key importance because it is the defining characteristic of Snapshot Isolation. Both Snapshot Isolation and Read Committed proscribe G1a, G1b, and G1c. However, Snapshot Isolation also proscribes G-nonadjacent.

Formally

G-nonadjacent’s roots start in Adya’s 1999 thesis, which defined G-single, and showed it to be illegal under Snapshot Isolation. This meant that any history legal under Snapshot Isolation but not Serializable must contain a cycle with at least two read-write edges.

Fekete, Liarokapis, O’Neil, & O’Neil’s 2005 paper Making Snapshot Isolation Serializable showed that those two edges must be adjacent to one another:

Lemma 2.3. In a history executed under SI, if we know that there is some T_M → T_n dependency, and that T_m and T_n are concurrent, we can conclude that T_m -rw→ T_n.

Theorem 2.1. Suppose H is a multiversion history produced under Snapshot Isolation that is not serializable. Then there is at least one cycle in the serialization graph DSG(H), and we claim that in every cycle there are three consecutive transactions T_i.1, T_i.2, T_i.3 (where it is possible that T_i.1 and T_i.3 are the same transaction) such that T_i.1 and T_i.2 are concurrent, with an edge T_i.1 → T_i.2, and T_i.2 and T_i.3 are concurrent with an edge T_i.2 → T_i.3.

This is somewhat indirect, but as Ports & Grittner summarized in their 2012 Serializable Snapshot Isolation in PostgreSQL:

Theorem 1 (Fekete et al.). Every cycle in the serialization history graph contains a sequence of edges T₁ -rw→ T₂ -rw→ T₃ where each edge is an rw-antidependency.

Ports & Grittner called these adjacent read-write edges dangerous structures.

A more rigorous, (and perhaps more challenging) formalization comes from Cerone & Gotsman’s Analysing Snapshot Isolation, whose main theorem states that Strong Session Snapshot Isolation allows only cycles with adjacent read-write dependencies:

Theorem 9. Let

GraphSI = {G | (T_G ⊧ INT) ∧ (((SO_G ∪ WR_G ∪ WW_G) ; RW_G?) is acyclic) }

This defines a dependency graph G in terms of a set of transactions T_G, each of which is internally consistent, and states that the graph composed of session order (SO), write-read (WR), and write-write (WW) dependencies, extended by up to one hop through read-write (RW) dependencies, must be acyclic. If one drops the session order, this characterizes Snapshot Isolation.

These adjacent read-write edges are the cycles which Snapshot Isolation allows. However, Jepsen is not aware of an extant name for their inverse—those cycles which Snapshot Isolation prevents. Based on the literature and communications with Peter Alvaro & Alexey Gotsman, Jepsen calls this inverse phenomenon G-nonadjacent.

See Also

G-single is a special case of G-nonadjacent with exactly one read-write edge.

G-nonadjacent is a special case of G2, which has any arrangement of read-write edges.