Wait Free Synchronization

A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps of finite time, regardless of the execution speeds of the other processes.

Wait-free algorithms are always lock-free algorithms. Whenever one process locks an object, other objects are forced to wait an unbounded amount of time until the first process releases that object. This causes many well-known problems (indeterministic DeadLock and LiveLock) that are completely avoided by wait-free algorithms.

http://portal.acm.org/citation.cfm?doid=114005.102808

(stuff that was really merely lock-free, not quite wait-free, moved to LockFreeSynchronization)

Someone changed "DeadLock" to "indeterministic DeadLock". What's the difference ? -- DavidCary

: Deterministic deadlock/livelock will happen consistently and predictably (i.e., you could program it to happen if you wanted to, although I'm not quite sure why you would).
: Indeterministic deadlock/livelock is unpredictable. Even if you wanted to you could only cause it to occur probabilistically (i.e., run a couple hundred threads together knowing that the odd's of them escaping deadlock are about the same as you winning the lottery).
: The reason for the distinction is that you can in theory program your way back into deadlocks; wait-free synchronization demonstrates that it is never necessary.
: -- WilliamUnderwood

Are there any ACID database with WaitFree? reads and reasonable updates ? The closest I can get is:

:read - open("cur"); read(); close("cur")

:write - lock("lock"); copy("cur", "tmp"); modify("tmp"); rename("tmp", "cur"); unlock("lock");

Reads are fine and virtually waitfree this way, but writes are not.

See LockFreeSynchronization SynchronizationStrategies http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms

CategoryConcurrencyPatterns