A Stale Read is a type of Real-Time phenomenon in which a read fails to observe the consequences of a completed write. The read need not observe the specific value written; it may observe any later state. The write must complete before the read begins: if the two are concurrent, Stale Read does not apply.

For example, imagine you post a photo to a social media service, and when the upload is complete, call your parents to tell them about it. They load your profile page, but the photo is not yet visible. Their read is stale.

Stale Read is prohibited by Linearizability and Strict Serializability, but is permitted by Sequential and Serializability.

Literature

Stale Reads have a long history in hardware design. The problem of keeping multiple memory caches up-to-date is known as cache coherence, and protocols for addressing it were actively developed in the 1970s (see, for instance, Censier & Feautrier’s A New Solution to Coherence Problems in Multicache Systems. By 1988 Cheong & Veidenbaum’s A Cache Coherence Scheme with Fast Selective Invalidation used the term “stale” to describe cache-lines that had been invalidated by a newer write.

In 1992 Kistler & Satyanarayanan’s Disconnected Operation in the Code File System discussed stale cache entries in the context of distributed systems. By the mid-1990s “stale read” was well-established in the literature; see, for instance, Heidemann, Goel, & Popek’s Defining and Measuring Conflicts in Optimistic Replication.

See Also

Stale Read is one type of Real-Time phenomenon.

For many systems, Stale Read is acceptable, so long as results are not too stale. These systems may opt for k-staleness or t-visibility: two measures of probabilistically bounded staleness.