Phenomenon G2-item (Item Anti-dependency Cycle) is a specific kind of G2 cycle where the read-write edges between transactions involve reads of a single object, rather than predicate reads. Specifically, G2-item is a dependency cycle made up of any number of write-write and write-read edges, and at least one item read-write edge—also known as an item anti-dependency. G2-item is legal under Read Committed, but proscribed by Repeatable Read and stronger models.
For example, imagine a history of two transactions over integer registers. Transaction T1 reads x, finds it does not yet exist, and writes y = 1. Transaction T2 reads y, also finds that it does not exist, and writes x = 1. T2 item read-write depends on T1 because it observed the unborn state of x just prior to T2’s write; symmetrically, T1 read-write depends on T2. Each transaction failed to observe the other’s effects. This history is illegal under Repeatable Read.
G2-item was motivated by a desire to characterize ANSI SQL’s version of Repeatable Read, which used long locks for all operations except predicate-based reads.
Formally
G2-item is defined in Adya’s thesis, section 3.2.4, in terms of a Direct Serialization Graph, or DSG:
G2-item: item Anti-dependency Cycles. A history H exhibits phenomenon G2-item if DSG(H) contains a directed cycle having one or more item anti-dependency edges.
This definition is a bit confusing: it appears to allow a cycle which involves not only an item anti-dependency, but also a predicate anti-dependency. This seems contrary to the surrounding text, which seems to imply that no predicate-based reads should count towards G2-item. Adya level PL-2.99 (Repeatable Read) disallows G1 and G2-item, and is described as allowing transaction Ti to commit only if:
Ti is completely isolated from other transactions with respect to data items and has PL-2 guarantees for predicate-based reads
Jepsen suspects that G2-item was intended to rule out predicate anti-dependency edges. If you have insight into this question, please email aphyr@jepsen.io.
See Also
G2 is a more general form of G2-item, which allows predicate read-write dependencies.