Read Copy Update

ReadCopyUpdate, or RCU, is a LockFreeSynchronization pattern to model simple transactions by use of an atomic CompareAndSwap? (CAS) operation. Basically, we read the bits we need, make a copy with the modifications we need, then update to the copy with a CAS on the pointer to the starting value. In case of concurrent writers, one will 'win' the race (thus assuring progress) while the others will need to restart their modifications.

This pattern can easily leverage PersistentDataStructure, such as immutable trees, because they allow reuse of nodes between updates. This allows RCU to scale a fair degree, i.e. supporting O(lg(N)) updates on an N-sized structure.

RCU's weakness is that you cannot easily share update access to just 'part' of a structure. Every update must go back through the root.

Also, it does not scale easily to multiple writers, since conflict probability increases and every writer must do rework after a conflict - which means work is proportional to O(W^2) for W writers. LiveLock and starvation are possible, and are even probable when some writers have a 'bigger' write task than others (i.e. a short write will usually win, causing the expensive write to redo over and over). RCU is most useful when the number of reads or readers vastly outnumber the writes and writers, in which case we'll only pay a bit to keep a copy of memory around for the readers.

LazyEvaluation can help with some of these weaknesses. E.g. an expensive write can be a lot cheaper if instead of computing the new value, we write 'the new value is function F of the current value', then eventually reduce these as needed.

see http://en.wikipedia.org/wiki/Read_copy_update