Content deleted Content added
→Wait-freedom: Include reference to paper by Alistarh, Censor-Hillel, and Shavit that showed that under reasonable assumptions, lock-free algorithms are wait free. |
m Open access bot: arxiv updated in citation with #oabot. |
||
Line 77:
Wait-free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and [[Erez Petrank|Petrank]]<ref name=wf-queue>{{cite conference |last1=Kogan |first1=Alex |last2=Petrank |first2=Erez |conference=Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2011 |isbn=978-1-4503-0119-0 |pages=223–234 |doi=10.1145/1941553.1941585 |title=Wait-free queues with multiple enqueuers and dequeuers|url=http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf}}</ref> presented a wait-free queue building on the [[Compare-and-swap|CAS]] primitive, generally available on common hardware. Their construction expanded the lock-free queue of Michael and Scott,<ref name=lf-queue>{{cite conference |last1=Michael |first1=Maged |last2=Scott |first2=Michael |conference=Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC) |year=1996 |isbn=0-89791-800-2 |pages=267–275 |doi=10.1145/248052.248106 |title=Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms|doi-access=free }}</ref> which is an efficient queue often used in practice. A follow-up paper by Kogan and Petrank<ref name=wf-fpsp>{{cite conference |last1=Kogan |first1=Alex |last2=Petrank |first2=Erez |conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2012 |isbn=978-1-4503-1160-1 |pages=141–150 |doi=10.1145/2145816.2145835 |title=A method for creating fast wait-free data structures}}</ref> provided a method for making wait-free algorithms fast and used this method to make the wait-free queue practically as fast as its lock-free counterpart. A subsequent paper by Timnat and Petrank<ref name=wf-simulation>{{cite conference |last1=Timnat |first1=Shahar |last2=Petrank |first2=Erez |conference=Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP) |year=2014 | isbn=978-1-4503-2656-8 | pages = 357–368 | doi=10.1145/2692916.2555261 | title= A Practical Wait-Free Simulation for Lock-Free Data Structures}}</ref> provided an automatic mechanism for generating wait-free data structures from lock-free ones. Thus, wait-free implementations are now available for many data-structures.
Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free<ref name=lf-wf>{{cite conference |last1=Alistarh |first1=Dan |last2=Censor-Hillel |first2=Keren |last3=Shavit |first3=Nir |conference=Proc. 46th Annual ACM Symposium on Theory of Computing (STOC’14) | year=2014 | isbn=978-1-4503-2710-7 | pages = 714-723 | doi=10.1145/2591796.2591836 | title=Are Lock-Free Concurrent Algorithms Practically Wait-Free?|arxiv=1311.3200 }}</ref>. So the added algorithmic complexity of a wait-free algorithm might not be worth the effort, if there are not hard deadlines to be met.
== Lock-freedom ==
| |||