https://www.liblfds.org/mediawiki/index.php?title=White_Papers&feed=atom&action=history
White Papers - Revision history
2024-03-29T10:12:49Z
Revision history for this page on the wiki
MediaWiki 1.36.0
https://www.liblfds.org/mediawiki/index.php?title=White_Papers&diff=15&oldid=prev
Admin: /* Trees */
2016-06-04T15:24:18Z
<p><span dir="auto"><span class="autocomment">Trees</span></span></p>
<p><b>New page</b></p><div>==Introduction==<br />
White papers, ordered alphabetically by subject. The important paper is Drepper's (Miscellaneous section), for absolutely vital background knowledge.<br />
<br />
==Documents==<br />
<br />
===Counter===<br />
* [[Aspnes, Herlihy, Shavit - Counting Networks]] ([http://www.liblfds.org/downloads/white%20papers/%5BCounter%5D%20-%20%5BAspnes,%20Herlihy,%20Shavit%5D%20-%20Counting%20Networks.pdf download])<br />
<br />
===Hash===<br />
* [[Michael - High Performance Dynamic Lock-Free Hash Tables and List-Based Sets]] ([http://www.liblfds.org/downloads/white%20papers/%5BHash%5D%20-%20%5BMichael%5D%20-%20High%20Performance%20Dynamic%20Lock-Free%20Hash%20Tables%20and%20List-Based%20Sets.pdf download])<br />
<br />
===Linked List===<br />
* [[Harris - A Pragmatic Implementation of Non-Blocking Linked-Lists]] ([http://www.liblfds.org/downloads/white%20papers/%5BLinked%20List%5D%20-%20%5BHarris%5D%20-%20A%20Pragmatic%20Implementation%20of%20Non-Blocking%20Linked-Lists.pdf download])<br />
* [[Sundell, Tsigas - Lock-Free and Practical Deques and Doubly Linked Lists using Single-Word CAS]] ([http://www.liblfds.org/downloads/white%20papers/%5BLinked%20List%5D%20-%20%5BSundell,%20Tsigas%5D%20-%20Lock-Free%20and%20Practical%20Deques%20and%20Doubly%20Linked%20Lists%20using%20Single-Word%20CAS.pdf download])<br />
* [[Valois - Lock-Free Linked Lists Using Compare-and-Swap]] ([http://www.liblfds.org/downloads/white%20papers/%5BLinked%20List%5D%20-%20%5BValois%5D%20-%20Lock-Free%20Linked%20Lists%20Using%20Compare-and-Swap.pdf download]])<br />
<br />
===Miscellaneous===<br />
* [[Drepper - What Every Programmer Should Know About Memory]] ([http://www.liblfds.org/downloads/white%20papers/%5BMisc%5D%20-%20%5BDrepper%5D%20-%20What%20Every%20Programmer%20Should%20Know%20About%20Memory.pdf download])<br />
<br />
===Queue===<br />
* [[Evequoz - Non-Blocking Concurrent FIFO Queues With Single Word Synchroniation Primitives]] ([http://www.liblfds.org/downloads/white%20papers/%5BQueue%5D%20-%20%5BEvequoz%5D%20-%20Non-Blocking%20Concurrent%20FIFO%20Queues%20With%20Single%20Word%20Synchroniation%20Primitives.pdf download])<br />
* [[Fober, Orlarey, Letz - Optimised Lock-Free FIFO Queue]] ([http://www.liblfds.org/downloads/white%20papers/%5BQueue%5D%20-%20%5BFober,%20Orlarey,%20Letz%5D%20-%20Optimised%20Lock-Free%20FIFO%20Queue.pdf download])<br />
* [[Michael, Scott - Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms]] ([http://www.liblfds.org/downloads/white%20papers/%5BQueue%5D%20-%20%5BMichael,%20Scott%5D%20-%20Simple,%20Fast,%20and%20Practical%20Non-Blocking%20and%20Blocking%20Concurrent%20Queue%20Algorithms.pdf download])<br />
* [[Shann, Huang, Chen - A practical nonblocking queue algorithm using compare-and-swap]] ([http://www.liblfds.org/downloads/white%20papers/%5BQueue%5D%20-%20%5BShann,%20Huang,%20Chen%5D%20-%20A%20practical%20nonblocking%20queue%20algorithm%20using%20compare-and-swap.pdf download])<br />
<br />
===Read-Copy-Update===<br />
* [[McKenney, Slingwine - Read-Copy Update; Using Execution History to Solve Concurrency Problems]] ([http://www.liblfds.org/downloads/white%20papers/%5BRCU%5D%20-%20%5BMcKenney,%20Slingwine%5D%20-%20Read-Copy%20Update;%20Using%20Execution%20History%20to%20Solve%20Concurrency%20Problems.pdf download])<br />
<br />
===Safe Memory Reclamation===<br />
* [[Herlihy, Luchangco, Moir - The Repeat Offender Problem]] ([http://www.liblfds.org/downloads/white%20papers/%5BSMR%5D%20-%20%5BHerlihy,%20Luchangco,%20Moir%5D%20-%20The%20Repeat%20Offender%20Problem.pdf download])<br />
* [[Michael - Hazard Pointers; Safe Memory Reclaimation for Lock-Free Objects]] ([http://www.liblfds.org/downloads/white%20papers/%5BSMR%5D%20-%20%5BMichael%5D%20-%20Hazard%20Pointers;%20Safe%20Memory%20Reclaimation%20for%20Lock-Free%20Objects.pdf download])<br />
* [[Michael, Scott - Correction of a Memory Management Technique for Lock-Free Data Structures]] ([http://www.liblfds.org/downloads/white%20papers/%5BSMR%5D%20-%20%5BMichael,%20Scott%5D%20-%20Correction%20of%20a%20Memory%20Management%20Technique%20for%20Lock-Free%20Data%20Structures.pdf download])<br />
<br />
===Skip-list===<br />
* [[Fomitchev, Ruppert - Lock-Free Linked Lists and Skip Lists]] ([http://www.liblfds.org/downloads/white%20papers/%5BSkip%20List%5D%20-%20%5BFomitchev,%20Ruppert%5D%20-%20Lock-Free%20Linked%20Lists%20and%20Skip%20Lists.pdf download])<br />
* [[Herlihy, Lev, Luchangco, Shavit - A Provably Correct Scalable Concurrent Skip List]] ([http://www.liblfds.org/downloads/white%20papers/%5BSkip%20List%5D%20-%20%5BHerlihy,%20Lev,%20Luchangco,%20Shavit%5D%20-%20A%20Provably%20Correct%20Scalable%20Concurrent%20Skip%20List.pdf download])<br />
<br />
===Stack===<br />
* [[Hendler, Shavit, Yerushalmi - A Scalable Lock-Free Stack Algorithm]] ([http://www.liblfds.org/downloads/white%20papers/%5BStack%5D%20-%20%5BHendler,%20Shavit,%20Yerushalmi%5D%20-%20A%20Scalable%20Lock-Free%20Stack%20Algorithm.pdf download])<br />
<br />
===Trees===<br />
* [[Bronson, Casper, Chafi, Olukotun - A Practical Concurrent Binary Search Tree]] (AVL) ([http://www.liblfds.org/downloads/white%20papers/%5BAVL%20Tree%5D%20-%20%5BBronson,%20Casper,%20Chafi,%20Olukotun%5D%20-%20A%20Practical%20Concurrent%20Binary%20Search%20Tree.pdf download])<br />
* [[Braginsky, Petrank - A Lock-Free B+tree]] ([http://www.liblfds.org/downloads/white%20papers/%5BB+%20Tree%5D%20-%20%5BBraginsky,%20Petrank%5D%20-%20A%20Lock-Free%20B+tree.pdf download])<br />
* [[Kim, Cameron, Graham - Lock Free Red Black Trees Using CAS]] ([http://www.liblfds.org/downloads/white%20papers/%5BRed-Black%20Tree%5D%20-%20%5BKim,%20Cameron,%20Graham%5D%20-%20Lock%20Free%20Red%20Black%20Trees%20Using%20CAS.pdf download])</div>
Admin