Phenomenon G1c (Cyclic Information Flow) occurs when a set of transactions all see each other, in the sense that they either read or modify each other’s writes. Specifically, G1c is defined as a dependency cycle consisting entirely of write-write or write-read edges. G1c is legal under Read Uncommitted, but proscribed by Read Committed and stronger models.

For example, imagine our objects are lists, and every write appends a unique integer to a list. Transaction T₁ appends 1 to x. Transaction T₂ appends 2 to x. T₁ then reads x = [1, 2]. Both transactions commit. T₂ overwrote T₁, but T₁ observed T₂. Information has flowed in a loop between the two transactions.

Note that G1c only constrains committed transactions. Writes performed by aborted transactions do not contribute to the dependency graph.

Formally

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

G1c: Circular Information Flow. A history H exhibits phenomenon G1c if DSG(H) contains a directed cycle consisting entirely of dependency edges.

Note that Adya calls write-write and write-read edges “dependencies”; read-write edges are “anti-dependencies”. Jepsen refers to all edges as “dependencies”, including read-write, real-time, etc.

See Also

Cyclic Information Flow is a (less obvious) aspect of the ANSI SQL anomaly P1 (Dirty Read). However, P1 has two interpretations: one allows non-Serializable histories, and the other rules out Serializable histories. Adya’s G1 captures the spirit of P1 in three general, precise phenomena: G1a (Aborted Read), G1b (Intermediate Read), and G1c (Cyclic Information Flow). Ruling out all three ensures Read Committed.

Since G0 (write cycle) is a cycle of write-write dependencies, any G0 is also G1c.