JEPSEN

G2 (Anti-dependency Cycle)

Phenomenon G2 (Anti-dependency Cycle) occurs when a ring of transactions all depend on each other, and at least one transaction overwrote something a different transaction read. Specifically, G2 refers to 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. G2 is legal under Repeatable Read, but proscribed by Serializable and stronger models.

For example, imagine a history of two transactions over integer registers. Transaction T1 performs a predicate read of all objects, finds the database empty, and writes x = 1. Transaction T2 performs a predicate read of all objects, also finds the database empty, and writes y = 2. T2 read-write depends on T1 because it observed the unborn state of x just prior to T2; symmetrically, T1 read-write depends on T2. Each transaction failed to observe the other’s effects: this history cannot be Serializable.

Formally

G2 is defined in Adya’s thesis, section 3.2.3, in terms of a Direct Serialization Graph, or DSG:

G2: Anti-dependency Cycles. A history H exhibits phenomenon G2 if DSG(H) contains a directed cycle having one or more anti-dependency edges.

See Also

G2 has several subtypes:

  • G2-item is a G2 cycle where no dependencies involve predicates. G2-item is proscribed by Repeatable Read.
  • G-single is a G2 cycle with exactly one read-write dependency.
  • G-nonadjacent is a G2 cycle where no two read-write dependencies are adjacent to one another. G-nonadjacent is proscribed by Snapshot Isolation.