Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with [[Resource starvation|starvation]]-freedom. An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes. This property is critical for real-time systems and is always nice to have as long as the performance cost is not too high.
It was shown in the 1980s<ref name=imp>{{cite bookconference |last=Herlihy |first=Maurice P. |titleconference=Proceedings of theProc. Seventh7th Annual ACM SymposiumSymp. on Principles of Distributed Computing : Toronto, Ontario, Canada|year=1988|publisher=Association for Computing Machinery|___location=New York, N.Y.|isbn=0-89791-277-2 |pages=276–290 |urldoi=http://doi.acm.org/10.1145/62546.62593 |chaptertitle=Impossibility and universality results for wait-free synchronization |dateyear=August 15–171988}}</ref> that all algorithms can be implemented wait-free, and many transformations from serial code, called ''universal constructions'', have been demonstrated. However, the resulting performance does not in general match even naïve blocking designs. Several papers have since improved the performance of universal constructions, but still, their performance is far below blocking designs.
Several papers have investigated the difficulty of creating wait-free algorithms. For example, it has been shown<ref name=cond-sync>{{cite bookconference |last=Fich |first=Faith|author1-link=Faith Ellen |last2=Hendler |first2=Danny |last3=Shavit |first3=Nir |titleconference=Proceedings of theProc. 23rd Annual ACM Symposium Symp.on Principles of Distributed Computing, (PODC) 2004 : St. John's, Newfoundland, Canada|year=2004|publisher=ACM Press|___location=New York, NY|isbn=1-58113-802-4 |pages=80–87 |urldoi=http://doi.acm.org/10.1145/1011767.1011780 |chaptertitle=On the inherent weakness of conditional synchronization primitives|date=July 25–28}}</ref> that the widely available atomic ''conditional'' primitives, [[Compare-and-swap|CAS]] and [[Load-link/store-conditional|LL/SC]], cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads.
But in practice these lower bounds do not present a real barrier as spending a cache line or exclusive reservation granule (up to 2kb on ARM) of store per thread in the shared memory is not considered too costly for practical systems (typically the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required{{citation needed|date=June 2014}} is greater).
Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and Petrank<ref name=wf-queue>{{cite bookconference |lastlast1=Kogan |firstfirst1=Alex |last2=Petrank |first2=Erez |titleconference=Proceedings of theProc. 16th ACM SIGPLAN SymposiumSymp. on Principles and Practice of Parallel Programming (PPOPP) 2011)|year=2011|publisher=ACM Press|___location=San Antonio, TX|isbn=978-1-4503-0119-0 |pages=223–234 |urldoi=http://doi.acm.org/10.1145/1941553.1941585 |chaptertitle=Wait-free queues with multiple enqueuers and dequeuers|date=February 12–16}}</ref> presented a wait-free queue building on the [[Compare-and-swap|CAS]] primitive, generally available on common hardware. Their construction expands the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite bookconference |lastlast1=Michael |firstfirst1=Maged |last2=Scott |first2=Michael |titleconference=ProceedingsProc. of the Fifteenth15th Annual ACM SymposiumSymp. on Principles of Distributed Computing (PODC) 1996)|year=1996|publisher=ACM Press|___location=Philadelphia, Pennsylvania, USA|isbn=0-89791-800-2 |pages=267–275 |urldoi=http://doi.acm.org/10.1145/248052.248106 |chaptertitle=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms|date=May 23–26}}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite bookconference |lastlast1=Kogan |firstfirst1=Alex |last2=Petrank |first2=Erez |titleconference=ProceedingsProc. of17th the 17ACMACM SIGPLAN SymposiumSymp. on Principles and Practice of Parallel Programming (PPOPP) 2012)|year=2012|publisher=ACM Press|___location=New Orleans, LA|isbn=978-1-4503-1160-1 |pages=141–150 |urldoi=http://doi.acm.org/10.1145/2145816.2145835 |chaptertitle=A methodology for creating fast wait-free data structures|date=February 25–29}}</ref> provided a methodology for making wait-free algorithms fast and used this methodology to make the wait-free queue practically as fast as its lock-free counterpart.
== Lock-freedom ==
|