Asynchronous Computability and
Complexity

Concurrent Data-Structures and
Synchronization Algorithms

Transactional Memory Algorithms

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.