Relativistic hash tables use the RCU wait-for-readers operation to enforce the ordering and visibility of write operations, without requiring synchronization operations in
the reader. This novel use of wait-for-readers evolved
through a series of increasingly sophisticated write-side
barriers. Paul McKenney originally proposed the elimination of read memory barriers by introducing a new
write memory barrier primitive that forced a barrier on all
CPUs via inter-processor interrupts [14]. McKenney’s
later work on Sleepable Read-Copy Update (SRCU) [15]
used the RCU wait-for-readers operation to manage the
order in which write operations became visible to readers, providing the first example of using wait-for-readers
to order non-reclamation operations; this use served the
same function as a write memory barrier, but without requiring a corresponding read memory barrier in every
RCU reader. Philip Howard further refined this approach
in his work on relativistic red-black trees [9], using the
wait-for-readers operation to order the visibility of tree
rotation and balancing operations and prevent readers
from observing inconsistent states. Howard’s work used
wait-for-readers as a stronger barrier than a write memory barrier, enforcing the order of write operations regardless of the order a reader encounters them in the
data structure. Relativistic programming builds on this
stronger barrier.