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