A Real-Time phenomenon involves two operations ordered in real time, as measured by imaginary, perfectly synchronized wall clocks. One event must complete before the other begins: a real-time dependency.
Real-Time phenomena always involve some other relationship between the operations. For instance, a Stale Read occurs when a read begins after a write completes, but fails to observe the write’s effects (e.g. the write rw-depends on the read)). Jepsen calls this G2-item-realtime, by analogy with G2-item. You could also imagine a system which ensures that if one write begins after another ends, those writes will logically take effect in that order. Such a system would prevent G0-realtime: a cycle composed of write-write and real-time edges.
For example, imagine an artist paints a mural on the side of a building. Two weeks later, a graffiti artist tags it. However, owing to mysterious properties of the brick and ink, the graffiti artist’s paint is laid down under the mural, as if the mural had been painted after. A logically consistent order of events exists: the mural transaction executed after the graffiti transaction. However, this order contradicts the real-time order of events. This history is Serializable, even Strong Session Serializable, but not Strong Serializable.
More formally, we say that given some phenomenon P defined in terms of a cycle in a dependency graph G, the phenomenon P-realtime is the corresponding cycle in the graph (G ∪ R), where R is the graph of real-time dependencies between transactions in G.
Linearizable systems proscribe Real-Time phenomena. The “Strong” variants of transactional consistency models generally differ from their non-strong counterparts by ruling out Real-Time phenomena as well. For instance, Serializable proscribes G1c and G2: cycles involving write-write, write-read, and read-write dependencies. Strong Serializable goes further by proscribing G1c-realtime and G2-realtime: cycles involving write-write, write-read, read-write, and real-time dependencies. Similarly, Strong Snapshot Isolation strengthens Snapshot Isolation by ruling out G-nonadjacent-realtime.
Literature
This concept is adapted directly from Adya’s Weak Consistency, section 4.9, which defines Strict Serializability in terms of an extension to the Direct Serialization Graph used to define Serializability:
Consider a graph called the Real-time Serialization Graph or RSG which is the same as the DSG except that there are some extra edges to capture the order of non-overlapping transactions: If a transaction Ti commits before Tj executes its first event in real-time, we add a real-order edge from Ti to Tj; these extra edges force non-overlapping transactions to be serialized in the order in which they executed in real-time. Strict serializability or PL-SS is defined as the level that disallows G1 and G2 when these phenomena are defined on the RSG instead of the DSG.
See Also
A Stale Read is a Real-Time phenomenon where a later read fails to observe the effects of an earlier write.
Process phenomena are like Real-Time phenomena, except operations are only related when they happen on the same process.