Nir Shavit's Publications

Asynchronous Computability and Complexity

Concurrent Data-Structures and Synchronization Algorithms

Transactional Memory Algorithms

Asynchronous Computability and Complexity

N. Francez, N. Shavit. A New Approach to Detection of Locally Indicative Stability. Proc. of the 13th International Colloquium on Automata Languages and Programming (ICALP), Rennes, France, 344-358, Springer-Verlag (1986). [BibTex]

D. Dolev, E. Gafni, and N. Shavit. Toward a Non-Atomic Era: L-Exclusion as a Test Case. Proc. of the 20th Annual ACM Symposium on Theory of Computing (STOC), Chicago, 78-92, (1988). [BibTex]

H. Attiya, D. Dolev, and N. Shavit. Bounded Polynomial Randomized Consensus. Proc. of the 8th Annual ACM Symposium on Principles of Distributed Computing (PODC), Edmonton, 281-293 (1989). [BibTex]

M. Saks, N. Shavit, and H. Woll. Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice. Proc. of the 2nd ACM Symposium on Discrete Algorithms (SODA), San-Francisco, 351-362 (1991). [BibTex]

R. Gawlick, N. Lynch, and N. Shavit. Concurrent Time-Stamping Made Simple. Proc. of the Annual Israel Symposium on Theory and Computing Systems (ISTCS), Haifa 171-183 (1992). [BibTex]

N. Lynch and N. Shavit. Timing Based Mutual Exclusion. Proc. of the Annual Real-Time Symposium (RTSS), Phoenix, 2-11 (1992). [BibTex]

Y.Afek, H.Attiya, D.Dolev, E.Gafni, M.Merritt and N.Shavit. Atomic Snapshots of Shared Memory. Journal of the ACM Vol. 40, No. 4 (September 1993), pages 873-890.
A preliminary version appeared in Proc. 9th Annual ACM Symposium on Principles of Distributed Computing (PODC), Quebec-City, 1-14 (1990). [BibTex]

Y. Afek, D. Dolev, E. Gafni, M. Merritt and N. Shavit. A Bounded first-in, first-enabled solution to the l-exclusion problem. ACM Transactions on Programming Languages and Systems, (16)3, (May 1994), pages 939-953.
A preliminary version appeared in Proc. of the 4th Workshop on Distributed Algorithms (WDAG), Bari, Italy, 422-431 (1990). [BibTex]

H. Attiya, N. Lynch and N. Shavit. Are Wait-Free Algorithms Fast? Journal of the ACM, Vol. 41, No. 4 (July 1994), pages 725-763.
A preliminary version appeared in Proc. of the 31st Annual Symposium on the Foundations of Computer Science (FOCS), St. Louis, 55-64 (1990). [BibTex]

M.P. Herlihy, N. Shavit, and O. Waarts, Linearizable Counting Networks Distributed Computing, 9, (1996), pages 193-203.
A preliminary version entitled: Low Contention Linearizable Counting, appeared in Proc. of the 32nd Annual Symposium on the Foundations of Computer Science (FOCS), San Juan, 526-535 (1991). [BibTex]

D. Dolev and N. Shavit. Bounded Concurrent Time-stamping. SIAM Journal on Computing, Vol. 26, No. 2 (April 1997), pages 418-455.
A preliminary version entitled: Bounded Concurrent Time Stamp Systems Are Constructible, appeared in Proc. of the 21st Annual ACM Symposium on Theory of Computing (STOC), Seattle, 454-466, (1989). [BibTex]

F. Fich, M.P. Herlihy, N. Shavit. On the Space Complexity of Randomized Synchronization. Journal of the ACM, 45:5 (1998), pages 843-862.
A preliminary version appeared in Proc. of the Annual ACM Symposium on Principles of Distributed Computing (PODC), Ithaca, 241-249 (1993). [BibTex]

N. Shavit, E. Upfal, and A. Zemach. A Steady State Analysis of Diffracting Trees. Theory of Computing Systems, Special Issue, No. 31 (1998), pages 403-424.
A preliminary version appeared in Proc. of the 8th Annual Symposium on Parallel Algorithms and Architectures (SPAA), Padova, Italy, 33-41 (1996). [BibTex]

N. Lynch, N. Shavit, A. Shvartzman, and D. Touitou. Timing Conditions for Linearizability in Uniform Counting Networks. Theoretical Computer Science, Special Issue (1999), Vol. 220 (1), pages 67-91.
A preliminary version entitled: Counting Networks are Practically Linearizable, appeared in Proc. of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), Philadelphia, pages 280-289 (1996). [BibTex]

M.P. Herlihy, N. Shavit. The Topological Structure of Asynchronous Computability. Journal of the ACM (1999), pages 858-923.
This work combines two preliminary papers, entitled: The Asynchronous Computability Theorem for t-Resilient Tasks, which appeared in Proc. of the 25th Annual Symposium on Theory of Computing (STOC), San-Diego, 111-120 (1993),
and: A Simple Constructive Computability Theorem for Wait-free Computation, which appeared in Proc. of the 26th Annual Symposium on Theory of Computing (STOC), 243-252 (1994). [BibTex]

O. Agesen, D. Detlefs, C. H. Flood, A. Garthwaite, P. Martin, N. Shavit, G. L. Steele Jr.: DCAS-Based Concurrent Deques. Theory of Computing Systems, Special Issue 35(3), pp. 349-386, 2002.
A preliminary version appeared in Proc. of the Twelfth ACM Symposium on Parallel Algorithms and Architectures , Bar Harbor, Maine, pages 137-146, August 2000. [BibTex]

D. Hendler and N. Shavit. Operation-Valency and the Cost of Coordination. Proc. of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 84-91, Boston, Massachusetts, July 2003.
Submitted to Distributed Computing. [BibTex]

V. Luchangco, M. Moir and N. Shavit. On the Uncontended Complexity of Consensus. Proc. of the 17th International Conference on Distributed Computing, pages 45-59, Sorrento, Italy, October 2003. [BibTex]

S. Doherty, D. Detlefs, L. Groves, C. H. Flood, V. Luchangco, P. A. Martin, M. Moir, N. Shavit, G. L. Steele Jr. DCAS Is Not a Silver Bullet for Nonblocking Algorithm Design. Proc. of the sixteenth ACM Symposium on Parallelism in Algorithms and Architectures, pages 216-224, Barcelona, Spain, June 2004. [BibTex]

F. Fich, V. Luchangco, M. Moir, and N. Shavit. Obstruction-Free Algorithms Can Be Practically Wait-Free. Proc. of the 19th International Symposium on Distributed Computing (DISC 2005), pages 78-92, Krakow, Poland, September 2005. [BibTex]

F. Fich, V. Luchangco, M. Moir, and N. Shavit. Obstruction-Free Step Complexity: Lock-Free DCAS as an Example (Brief announcement). Proc. of the 19th International Symposium on Distributed Computing (DISC 2005), pages 493-494, Krakow, Poland, September 2005. [BibTex]

F. E. Fich, D. Hendler, and N. Shavit. Linear Lower Bounds on Real-World Implementations of Concurrent Objects. Proc. of the 46th Annual Symposium on Foundations of Computer Science (FOCS 2005), pages 165-173, Pittsburgh, PA, October 2005. Submitted to Theory of Computing. [BibTex]

G. Hoest and N. Shavit. Towards a Topological Characterization of Asynchronous Complexity. SIAM Journal on Computing. 36(2), pages: 457-497, 2006.
A preliminary version appeared in Proc. of the 16th Annual ACM Symposium on Principals of Distributed Computing (PODC), Santa Barbara (1997), pages 199-208. [BibTex]


Concurrent Data-Structures and Synchronization Algorithms

J. Aspnes, M.P. Herlihy, and N. Shavit. Counting Networks. Journal of the ACM, Vol. 41, No. 5 (September 1994), pages 1020-1048.
A preliminary version entitled: Counting Networks and Multi-Processor Coordination, appeared in Proc.of the 23rd Annual Symposium on Theory of Computing (STOC), New Orleans 348-358 (1991). [BibTex]

M. Herlihy, B. H. Lim, and N. Shavit. Scalable Concurrent Counting. ACM Transactions on Computer Systems, 13:4 (1995), pages 343-364.
A preliminary version entitled: Low contention load balancing on large scale multiprocessors, appeared in Proc. of the Annual Symposium on Parallel Algorithms and Architectures (SPAA), San Diego, 219-227 (1992). [BibTex]

M.P. Herlihy and N. Shavit. Applications of Algebraic Topology to Concurrent Computation. In Applications on Advanced Architecture Computers , Chapter 23, pages 255-263. Greg Astfalk, editor. SIAM Press, 1996.
Also appeared in slightly edited form in Siam News, 27-10, December 1994. [BibTex]

Y. Afek, B. Awerbuch, E. Gafni, Y. Mansour, A. Rosen, N. Shavit. Slide: the Key to Polynomial End-to-end Communication, Journal of Algorithms, 22 (1997), pages 158-186.
Based on a paper entitled: Polynomial End-to-End Communication, which appeared in Proc. of the 30th Annual Symposium on Foundations of Computer Science (FOCS), 358-363 (1989), and on a PODC paper by Y. Afek, E. Gafni and A. Rosen. [BibTex]

N. Shavit and A. Zemach. Diffracting Trees, ACM Transactions on Computer Systems, 14:4 (1996), 385-428.
A preliminary version appeared in Proc. of the Annual Symposium on Parallel Algorithms and Architectures (SPAA) 167-176 (1994). [BibTex]

N. Shavit and D. Touitou. Elimination Trees and the Construction of Pools and Stacks. Theory of Computing Systems, Special Issue, No. 30 (1997), pages 645-670.
A preliminary version appeared in Proc. of the Annual Symposium on Parallel Algorithms and Architectures (SPAA), Santa Barbara, 54-63 (1995). [BibTex]

Y. Riany, N. Shavit, D. Touitou. Towards a Practical Snapshot Algorithm. Theoretical Computer Science 269, pages 163-201 (2001).
A preliminary version appeared in Proc. of the Third Israel Symposium on Theory and Computing Systems (ISTCS), Tel Aviv (1995), 121-129. [BibTex]

G. Della-Libera and N. Shavit. Reactive Diffracting Trees. Journal of Parallel and Distributed Computing 60:7 (2000), pp. 853-890.
A preliminary version appeared in Proc. of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Newport, RI, (1997), pages 24-32. [BibTex]

N. Shavit and A. Zemach. Combining Funnels: A Dynamic Approach to Software Combining. Journal of Parallel and Distributed Computing 60:11 (2000), pages 1355-1387.
A preliminary version entitled: Combining Funnels, appeared in Proc. of the 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), Puerto Vallarta, Mexico, pages 61-70 (1998). [BibTex]

N. Shavit, E. Upfal, and A. Zemach. A Wait-free Sorting Algorithm. Theory of Computer Systems,Vol. 34 Num. 36 pages 519-544 (November/December 2001).
A preliminary version appeared in Proc. of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), Santa Barbara, pages 121-128 (1997). [BibTex]

N. Shavit and A. Zemach. Scalable Concurrent Priority Queue Algorithms. Proc. of the 18th Annual ACM Symposium on Principals of Distributed Computing (PODC), Atlanta, GA, (1999), pages 113-122. [BibTex]

W. Aiello, C. Busch, M. Herlihy, M. Mavronicolas, N. Shavit and D. Touitou. Supporting Increment and Decrement Operations in Balancing Networks. Chicago Journal of Theoretical Computer Science, 2000,4, MIT Press, December, 2000.
A preliminary version appeared in Proc. of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS), Trier, Germany (March 1999), pages 393-403. [BibTex]

D. Detlefs, C. H. Flood, A. Garthwaite, P. Martin, N. Shavit, G. L. Steele Jr.: Even Better DCAS-Based Concurrent Deques. Proc. of the 14th International Symposium on Distributed Computing (DISC), Toledo, Spain, pages 59-73, Springer-Verlag, 2000. [BibTex]

I. Lotan and N. Shavit. Skiplist-Based Concurrent Priority Queues. Proc. of the 14th International Parallel and Distributed Processing Symposium (IPDPS), Cancun, Mexico, 2000, pages 263-268. [BibTex]

D. Detlefs, C. Flood, N. Shavit, and X. Zhang, Parallel Garbage Collection for Shared Memory Multiprocessors . Proc. Java TM Virtual Machine Research and Technology Symposium , April 2001, Monterey, California. [BibTex]

D. Hendler and N. Shavit. Non-Blocking Steal-half Work Queues. Proc. of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 280-289, Monterey, California, July 2002. [BibTex]

D. Hendler and N. Shavit. Work Dealing. Proc. of the Fourteenth ACM Symposium on Parallel Algorithms and Architectures , Winnipeg, Manitoba, Canada, pages 164 - 172, August 2002. [BibTex]

D. Hendler, N. Shavit, and L. Yerushalmi. A Scalable Lock-Free Stack Algorithm. Proc. of the sixteenth ACM Symposium on Parallelism in Algorithms and Architectures , pages 206-215, Barcelona, Spain, June 2004.
Submitted to Journal of Parallel and Distributed Computing. [BibTex]

E. Ladan-Mozes and N. Shavit. An Optimistic Approach to Lock-Free FIFO Queues. Proc. of the 18th International Conference on Distributed Computing , pages 117-131, Amsterdam, The Netherlands, October 2004.
Submitted to Distributed Computing. [BibTex]

M. Moir, D. Nussbaum, O. Shalev, and N. Shavit. Using Elimination to Implement Scalable and Lock-Free FIFO Queues. Proc. of the seventeenth ACM Symposium on Parallelism in Algorithms and Architectures, pages 253-262, Las Vegas, Nevada July 2005. [BibTex]

S. Heller, M. Herlihy, V. Luchangco, M. Moir, W. Scherer, and N. Shavit. A Lazy Concurrent List-Based Set Algorithm. Proc. of the 9th International Conference On Principles Of Distributed Systems (OPODIS 2005), Pisa, Italy, pages 3-16, December 2005. [BibTex]

D. Hendler, Y. Lev, M. Moir, and N. Shavit. A Dynamic-Sized Nonblocking Work Stealing Deque. Distributed Computing (Special Issue), 18(3), pages 189-207, 2006.
A preliminary version entitled: Dynamic Memory ABP Work-Stealing, appeared in Proc. of the 18th International Conference on Distributed Computing , pages 188-200, Amsterdam, The Netherlands, October 2004. [BibTex]

V. Marathe, M. Moir, and N. Shavit. Composite Abortable Locks. Proc. of the 20th IEEE International Parallel & Distributed Processing Symposium, Rhodes Island, Greece, pages 1-10, April 2006. [BibTex]

O. Shalev and N. Shavit. Split-Ordered Lists - Lock-free Extensible Hash Tables. Journal of the ACM 53(3), pages 379-405, 2006.
A preliminary version appeared in Proc. of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 102-111, Boston, Massachusetts, July 2003. [BibTex]

O. Dvir, M. Herlihy, and N. Shavit. Virtual Leashing: Creating a Computational Foundation for Software Protection. Journal of Parallel and Distributed Computing (Special Issue) 66(9), Pages 1233-1240, September 2006.
A preliminary version entitled: Virtual leashing: Internet-Based Software Protection, appeared in Proc. of the 18th International Conference on Distributed Computing Systems , pages 283-292, Columbus, Ohio, 2005. [BibTex]

V. Luchangco, D. Nussbaum, and N. Shavit. A Hierarchical CLH Queue Lock Proc. of the European Conference on Parallel Computing (EuroPar 2006), pages 801-810, Dresden, Germany, September 2006. [BibTex]

Y. Lev, M. Herlihy, V. Luchangco, and N. Shavit. A Provably Correct Scalable Skiplist (Brief Announcement). Proc. of the 10th International Conference On Principles Of Distributed Systems (OPODIS), Bordeaux, France, December 2006. [BibTex] Parallel Computing (EuroPar 2006), pages 801-810, Dresden, Germany, September 2006. [BibTex]

M. Moir and N. Shavit. Concurrent Data Structures (Book Chapter). In Handbook of Data Structures and Applications, D. Metha and S.Sahni Editors, Chapman and Hall/CRC Press, Chapter 47, pages 47-1-- 47-30, 2004.[BibTex]


Transactional Memory Algorithms

N. Shavit, and D. Touitou. Software Transactional Memory. Distributed Computing, Special Issue, 10 (1997), pages 99-116.
A preliminary version appeared in Proc. of the 12th Annual ACM Symposium on Principles of Distributed Computing (PODC), Ottawa, 204-213 (1995). [BibTex]

M. Moir, V. Luchangco, and N. Shavit. Non-blocking K-Compare Single Swap. Proc. of the fifteenth ACM Symposium on Parallel Algorithms and Architectures, pages 314-323, San-Diego, California, June 2003. [BibTex]

F.E. Fich, D. Hendler and N. Shavit. On the Inherent Weakness of Conditional Primitives. Distributed Computing, 18(4), pages 267-277, 2006.
A preliminary version entitled: On the Inherent Weakness of Conditional Synchronization Primitives, appeared in Proc. of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 80-87, Saint Johns, Newfoundland, Canada, July 2004. [BibTex]

D. Dice and N. Shavit. What Really Makes Transactions Faster? Proc. of the 1st TRANSACT 2006 workshop, Ottawa, Canada, March 2006 (Transact06). [BibTex]

O. Shalev and N. Shavit. Predictive Log Synchronization. Proc. of EuroSys 2006, pages 305-315, Leuven, Belgium, April 2006. Submitted to Journal of Parallel and Distributed Computing. [BibTex]

D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. Proc. of the 20th International Symposium on Distributed Computing (DISC 2006), pages 194-208, Stockholm, Sweden, September 2006. [BibTex]

D. Dice and N. Shavit. Understanding Tradeoffs in Software Transactional Memory. To appear in Proc. of the 2007 International Symposium on Code Generation and Optimization (CGO), San Jose, CA, March 2007. [BibTex]

A. Matveev, O. Shalev, and N. Shavit. Dynamic Identification of Transactional Memory Locations. Technical Report.

shanir@post.tau.ac.il
Last updated: February 2007

ACM publications are copyright of the Association for Computing Machinery, SIAM publications are copyright of the Society for Industrial and Applied Mathematics, and TCS publications are Copyright (c) Elsevier Science B.V.