You are here: Home Papers

Multicore Computing Group Publications

Books

The Art of Multiprocessor Programming.  Maurice Herlihy, Nir Shavit.  Morgan Kaufmann 2008.

PhD Theses

Consistency Oblivious Programming. Hillel Avni. April 2014.

Fast and Scalable Software Execution on Multicores. Adam Morrison. December 2013.

Practical Solutions for Multicore Programming. Guy Korland. July 2011.

Techniques for Building Highly Concurrent Data Structures.  Ori Shalev.  October 2007.

MSc Theses

Programming with Hardware Lock Elision. Amir Levy. September 2013.

CBTree: A Practical Concurrent Self-Adjusting Search Tree. Boris Korenfeld. May 2012.

Fast and Scalable Rendezvousing.  Michael Hakimi.  September 2011.

Quasi-Linearizability: Relaxed Consistency For Improved Concurrency. Eitan Yanovsky. August 2011.

Coping With Context Switches in Lock-Based Software Transacional Memory Algorithms.  Yoav Cohen.  July 2011.

Lowering STM Overhead with Static Analysis.  Arie Zilberstein.  September 2010.

Multicore Programming in the Face of Metamorphosis: Union-Find as an Example.  Igor Berman.  July 2010.

Scalable Flat-Combining Based Synchronous Queues. Itai Incze. July 2010.

Building Scalable Producer-Consumer Pools based on Elimination-Diffraction Trees.  Maria Natanzon.  July 2010.

Combining Techniques Application for Tree Search Structures.  Vladimir Budovsky.  June 2010.

Dynamic Identification of Shared Transactional Locations.  Alexander Matveev.  2009.

A Transactional Consistency Clock Defined and Optimized.  Hillel Avni.  May 2009.

FIFO Queue Synchronization.  Moshe Hoffman.  July 2008.

Conference Publications

Temporally Bounding TSO for Fence-Free Asymmetric Synchronization. Adam Morrison and Yehuda Afek. Proceedings of the 20th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2015).

Brief Announcement: COP Composition Using Transaction Suspension in the Compiler. Hillel Avni and Adi Suissa-Peleg. Proceedings of the 28th International Symposium on Distributed Computing (DISC 2014).

Distributed Computing Building Blocks for Rational Agents. Yehuda Afek, Yehonatan Ginzberg, Shir Landau Feibish, and Moshe Sulamy. Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC 2014).

Software-Improved Hardware Lock Elision. Yehuda Afek, Amir Levy, and Adam Morrison. Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC 2014).

Fence-Free Work Stealing on Bounded TSO Processors. Adam Morrison and Yehuda Afek. Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2014).

Recursive Design of Hardware Priority Queues. Yehuda Afek, Anat Bremler-Barr, and Liron Schiff. Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013).

Reduced Hardware Transactions: a New Approach to Hybrid Transactional Memory. Alexander Matveev and Nir Shavit. Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013).

Leaplist: Lessons Learned in Designing TM-Supported Range Queries. Hillel Avni, Nir Shavit, and Adi Suissa. Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC 2013)

NUMA-Aware Reader-Writer Locks. Irina Calciu, Dave Dice, Yossi Lev, Victor Luchangco, Virendra Marathe, and Nir Shavit. Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2013).

Fast Concurrent Queues for x86 Processors. Adam Morrison and Yehuda Afek. Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2013).

MCA2: Multi-Core Architecture for Mitigating Complexity Attacks. Yehuda Afek, Anat Bremler-Bar, Yotam Harchol, David Hay, and Yaron Koral. Proceedings of the eighth ACM/IEEE symposium on Architectures for networking and communications systems (ANCS 2012).

Range Queries in Non-blocking k-ary Search Trees. Hillel Avni and Trevor Brown. Proceedings of the 16th International Conference On Principles Of Distributed Systems (OPODIS 2012).

Pessimistic Software Lock Ellision.  Yehuda Afek, Alexander Matveev, and Nir Shavit.  Proceedings of the 26th International Symposium on Distributed Computing (DISC 2012).

CBTree: A Practical Concurrent Self-Adjusting Search Tree.  Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E. Tarjan.  Proceedings of the 26th International Symposium on Distributed Computing (DISC 2012). Best student paper award.

Towards Consistency Oblivious Programming.  Yehuda Afek, Hillel Avni, and Nir Shavit.  Proceedings of the 15th International Conference On Principles Of Distributed Systems (OPODIS 2011).

Fast and Scalable Rendezvousing.  Yehuda Afek, Michael Hakimi, and Adam Morrison.  Proceedings of the 25th International Symposium on Distributed Computing (DISC 2011). Best student paper award.

Flat-combining NUMA locks. Dave Dice, Virendra J. Marathe, and Nir Shavit. Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011).

Cache index-aware memory allocation. Yehuda Afek, Dave Dice, and Adam Morrison. Proceedings of the 10th International Symposium on Memory Management (ISMM 2011).

Coping with context switches in lock-based software transactional memory. Yehuda Afek, Yoav Cohen, and Adam Morrison. Proceedings of the 4th Annual International Systems and Storage Conference (SYSTOR 2011).

Quasi-Linearizability: Relaxed Consistency for Improved Concurrency. Yehuda Afek, Guy Korland, and Eitan Yanovsky. Proceedings of the 14th International Conference On Principles Of Distributed Systems (OPODIS 2010).

Efficient Lock Free Privatization. Yehuda Afek, Hillel Avni, Dave Dice, and Nir Shavit. Proceedings of the 14th International Conference On Principles Of Distributed Systems (OPODIS 2010).

Lowering STM Overhead with Static Analysis. Yehuda Afek, Guy Korland, and Arie Zilberstein. Proceedings of the 23rd International Workshop on Languages and Compilers for Parallel Computing (LCPC2010).

Scalable Flat-Combining Based Synchronous Queues. Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir. Proceedings of the 24th International Symposium on Distributed Computing (DISC 2010).

Scalable Producer-Consumer Pools Based on Elimination-Diffraction Trees. Yehuda Afek, Guy Korland, Maria Natanzon, and Nir Shavit. Euro-Par (2) 2010.

Transactional Mutex Locks. Luke Dalessandro, Dave Dice, Michael L. Scott, Nir Shavit, and Michael F. Spear. Euro-Par (2) 2010.

TLRW: return of the read-write lock. Dave Dice and Nir Shavit. Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010).

Flat combining and the synchronization-parallelism tradeoff. Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir. Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010).

Interrupting Snapshots and the Java Size() Method. Yehuda Afek, Nir Shavit, and Moran Tzafrir. Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009).

Hopscotch Hashing. Maurice Herlihy, Nir Shavit, and Moran Tzafrir. Proceedings of the 22nd International Symposium on Distributed Computing (DISC 2008).

Maintaining Consistent Transactional States without a Global Clock. Hillel Avni and Nir Shavit. Proceedings of the 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008).

The Baskets Queue. Moshe Hoffman, Ori Shalev, and Nir Shavit. Proceedings of the 11th International Conference On Principles Of Distributed Systems (OPODIS 2007).

A Simple Optimistic Skiplist Algorithm. Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2007).

Understanding Tradeoffs in Software Transactional Memory. Dave Dice and Nir Shavit. Proceedings of the 2007 International Symposium on Code Generation and Optimization (CGO 2007).

Transactional Locking II. Dave Dice, Ori Shalev, and Nir Shavit. Proceedings of the 20th International Symposium on Distributed Computing (DISC 2006).

A Hierarchical CLH Queue Lock. Victor Luchangco, Daniel Nussbaum, and Nir Shavit. Euro-Par 2006.

Predictive log-synchronization. Ori Shalev and Nir Shavit. Proceedings of EuroSys 2006.

Composite Abortable Locks. Virendra J. Marathe, Mark Moir, and Nir Shavit. Proceedings of the 20th IEEE International Parallel & Distributed Processing Symposium (IPDPS 2006).

A Lazy Concurrent List-Based Set Algorithm. Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit. Proceedings of the 9th International Conference On Principles Of Distributed Systems (OPODIS 2005).

Linear Lower Bounds on Real-World Implementations of Concurrent Objects. Faith Ellen Fich, Danny Hendler, and Nir Shavit. Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005).

Space and Step Complexity Efficient Adaptive Collect. Yehuda Afek and Yaron De Levie. Proceedings of the 19th International Symposium on Distributed Computing (DISC 2005).

Obstruction-Free Step Complexity: Lock-Free DCAS as an Example. Faith Ellen Fich, Victor Luchangco, Mark Moir, and Nir Shavit. Proceedings of the 19th International Symposium on Distributed Computing (DISC 2005).

Obstruction-Free Algorithms Can Be Practically Wait-Free. Faith Ellen Fich, Victor Luchangco, Mark Moir, and Nir Shavit. Proceedings of the 19th International Symposium on Distributed Computing (DISC 2005).

Using elimination to implement scalable and lock-free FIFO queues. Mark Moir, Daniel Nussbaum, Ori Shalev, and Nir Shavit. Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005).

Virtual Leashing: Internet-Based Software Piracy Protection. Ori Dvir, Maurice Herlihy, and Nir Shavit. Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS 2005).

An Optimistic Approach to Lock-Free FIFO Queues. Edya Ladan-Mozes and Nir Shavit. Proceedings of the 18th International Symposium on Distributed Computing (DISC 2004).

Dynamic Memory ABP Work-Stealing. Danny Hendler, Yossi Lev, and Nir Shavit. Proceedings of the 18th International Symposium on Distributed Computing (DISC 2004).

On the inherent weakness of conditional synchronization primitives. Faith Ellen Fich, Danny Hendler, and Nir Shavit. Proceedings of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004).

A scalable lock-free stack algorithm. Danny Hendler, Nir Shavit, and Lena Yerushalmi. Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004).

DCAS is not a silver bullet for nonblocking algorithm design. Simon Doherty, David Detlefs, Lindsay Groves, Christine H. Flood, Victor Luchangco, Paul A. Martin, Mark Moir, Nir Shavit, and Guy L. Steele Jr.. Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004).

On the Uncontended Complexity of Consensus. Victor Luchangco, Mark Moir, and Nir Shavit. Proceedings of the 17th International Symposium on Distributed Computing (DISC 2003).

Split-ordered lists: lock-free extensible hash tables. Ori Shalev and Nir Shavit. Proceedings of the 22nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2003).

Operation-valency and the cost of coordination. Danny Hendler and Nir Shavit. Proceedings of the 22nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2003).

Nonblocking k-compare-single-swap. Victor Luchangco, Mark Moir and Nir Shavit. Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2003).

Non-blocking steal-half work queues. Danny Hendler and Nir Shavit. Proceedings of the 21st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2002).

Work dealing. Danny Hendler and Nir Shavit. Proceedings of the 14th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2002).

Workshop Publications

Optimal Pheromone Utilization. Yehuda Afek, Roman Kecher and Moshe Sulamy. 2nd Workshop on Biological Distributed Algorithms (BDA 2014).

Reduced Hardware Lock Elision. Yehuda Afek, Alex Matveev and Nir Shavit. 6th Workshop on the Theory of Transactional Memory (WTTM 2014).

Evaluating the Addition of Non-Transactional Loads to HTM (TSX). Hillel Avni and Yehuda Afek. 6th Workshop on the Theory of Transactional Memory (WTTM 2014).

Reduced Hardware NOREC: An Opaque Obstruction-Free and Privatizing HyTM. Alexander Matveev and Nir Shavit. The 9th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT 2014).

Improving HTM Scaling with Consistency-Oblivious Programming. Hillel Avni and Bradley Kuszmaul. The 9th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT 2014).

Reduced Hardware Transactions: a New Approach to Hybrid Transactional Memory. Alexander Matveev and Nir Shavit. The 8th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT 2013).

Leaplist: Lessons Learned in Designing TM-Supported Range Queries. Hillel Avni, Nir Shavit, and Adi Suissa. The 8th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT 2013).

Towards a Fully Pessimistic STM Model. Alexander Matveev and Nir Shavit.  The 7th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT 2012).

Implicit Privatization Using Private Transactions. Dave Dice, Alexander Matveev, and Nir Shavit.  The 5th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT 2010).

View Transactions and the Relaxation of Consistency Checks in Software Transactional Memory.  Yehuda Afek, Adam Morrison, and Moran Tzafrir.  The 2nd Workshop on the Theory of Transactional Memory (WTTM 2010).

Noninvasive concurrency with Java STM.  Guy Korland, Nir Shavit, and Pascal Felber.  The 3rd Workshop on Programmability Issues for Multi-Core Computers (MULTIPROG 2010)Best paper award.

TLRW: Return of the Read-Write Lock.  Dave Dice and Nir Shavit.  The 4th ACM SIGPLAN Workshop on Transactional Computing (TRANSACT 2009).

What Really Makes Transactions Faster? Dave Dice and Nir Shavit.  The 1st ACM SIGPLAN Workshop on Transactional Computing (TRANSACT 2006).

Journal Publications

The CB Tree: A Practical Concurrent Self-Adjusting Search Tree. Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E. Tarjan. Distributed Computing. 2014.

Fast and Scalable Rendezvousing. Yehuda Afek, Michael Hakimi, and Adam Morrison. Distributed Computing 26(4). 2013.

Data structures in the multicore age. Nir Shavit. Communications of the ACM 54(3).  2011.

The Velox Transactional Memory Stack. Yehuda Afek, Ulrich Drepper, Pascal Felber, Christof Fetzer, Vincent Gramoli, Michael Hohmuth, Etienne Riviere, Per Stenstr.m, Osman S. Unsal, Walther Maldonado, Derin Harmanci, Patrick Marlier, Stephan Diestelhorst, Martin Pohlack, Adri.n Cristal, Ibrahim Hur, Aleksandar Dragojevic, Rachid Guerraoui, Michal Kapalka, Sasa Tomic, Guy Korland, Nir Shavit, Martin Nowack, and Torvald Riegel. IEEE Micro 30(5). 2010.

Deuce: Noninvasive Software Transactional Memory in Java.  Guy Korland, Nir Shavit, and Pascal Felber.  Transactions on HiPEAC 5(2). 2010.

A scalable lock-free stack algorithm. Danny Hendler, Nir Shavit, and Lena Yerushalmi. Journal of Parallel and Distributed Computing 70(1). 2010.

Nonblocking k-Compare-Single-Swap. Victor Luchangco, Mark Moir, and Nir Shavit. Theory of Computing Systems 44(1). 2009.

An optimistic approach to lock-free FIFO queues. Edya Ladan-Mozes and Nir Shavit. Distributed Computing 20(5).  2008.

Solo-valency and the cost of coordination. Danny Hendler and Nir Shavit. Distributed Computing 21(1). 2008.

Efficient adaptive collect algorithms. Yehuda Afek and Yaron De Levie. Distributed Computing 20(3). 2007.

A Lazy Concurrent List-Based Set Algorithm. Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit. Parallel Processing Letters 17(4). 2007.

A dynamic-sized nonblocking work stealing deque. Danny Hendler, Yossi Lev, Mark Moir, and Nir Shavit. Distributed Computing 18(3). 2006.

On the inherent weakness of conditional primitives. Faith Ellen Fich, Danny Hendler, and Nir Shavit. Distributed Computing 18(4). 2006.

Split-ordered lists: Lock-free extensible hash tables. Ori Shalev and Nir Shavit. Journal of the ACM 53(3). 2006.

Virtual Leashing: Creating a computational foundation for software protection. Ori Dvir, Maurice Herlihy, and Nir Shavit. Journal of Parallel and Distributed Computing 66(9). 2006.

Toward a Topological Characterization of Asynchronous Complexity. Gunnar Hoest and Nir Shavit. SIAM Journal on Computing 36(2). 2006.

Concurrency and synchronization in Java programs. Mark Moir, Nir Shavit, and Jan Vitek. Science of Computer Programming 58(3). 2005.

DCAS-Based Concurrent Deques. Ole Agesen, David Detlefs, Christine H. Flood, Alexander T. Garthwaite, Paul A. Martin, Mark Moir, Nir Shavit, and Guy L. Steele Jr.. Theory of Computing Systems 35(3). 2002.