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]
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]
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.
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.