%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Non-blocking Synchronization Bibliography (Annotated) % % (c) 1997 Michael B. Greenwald % Distributed Systems Group % Computer Science Department % Stanford University %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Add URLs to all entries. % Go through my papers and add all relevant references % Convert text entries to inproceedings etc. % Add abstracts. @string{decsrc = "Digital Equipment Corporation Systems Research Center"} @string{springer = "Springer-Verlag"} @string{deccrl = "DEC Cambridge Research Lab"} @string{rpi = "Rensselaer Polytechnic Institute, Department of Computer Science"} @string{mit = "Massachusetts Institute of Technology"} @string{mitp = "The MIT Press"} @string{mitlcs = "MIT Laboratory for Computer Science"} @string{cmu = "Carnegie-Mellon University"} @string{ufl = "University of Florida"} @string{columbia = "Columbia University"} @string{rochester = "University of Rochester"} @string{washington = "University of Washington, Department of Computer Science and Engineering"} @string{lncs = "Lecture Notes on Computer Science"} @string{tr = "Technical Report"} @string{miteecs = "The {MIT} Electrical Engineering and Computer Science Series"} @string{cacm = "Communications of the {ACM}"} @string{jacm = "Journal of the {ACM}"} @string{tocs = "{ACM} Transactions on Computer Systems"} @string{toplas = "{ACM} Transactions on Programming Languages and Systems"} @string{proc = "Proceedings of the "} @string{proc1 = "Proceedings of "} @string{asplos = " International Conference on Architectural Support for Programming Languages and Operating Systems"} @string{dcs = " International Conference on Distributed Computing Systems"} @string{ieeert = " Real-Time Systems Symposium"} @string{isca = " Annual International Symposium on Computer Architecture"} @string{podc = " Symposium on Principles of Distributed Computing"} @string{popl = " Symposium on Principles of Programming Languages"} @string{ppopp = " {ACM} Symposium on Principles and Practice of Parallel Programming"} @string{sosp = " Symposium on Operating Systems Principles"} @string{spaa = " Symposium on Parallel Algorithms and Architectures"} @string{wdag = " International Workshop on Distributed Algorithms"}, @string{disc = " International Symposium on {DIStributed} Computing"}, @string{stoc = " {ACM} Symposium on Theory of Computing"} @string{pods = " Symposium on Principles of Database Systems"} @string{asplos89 = proc # "Second" # asplos} @string{asplos91 = proc # "Fourth" # asplos} @string{asplos92 = proc # "Fifth" # asplos} @string{asplos94 = proc # "Sixth" # asplos} @string{icdcs88 = proc # "Eighth" # dcs} @string{icdcs89 = proc # "Ninth" # dcs} @string{icdcs93 = proc # "Thirteenth" # dcs} @string{isca84 = proc # "Eleventh" # isca} @string{isca85 = proc # "Twelfth" # isca} @string{isca89 = proc # "Sixteenth" # isca} @string{isca93 = proc # "Twentieth" # isca} @string{podc83 = proc # "Second" # podc} @string{podc84 = proc # "Third" # podc} @string{podc85 = proc # "Fourth" # podc} @string{podc86 = proc # "Fifth" # podc} @string{podc87 = proc # "Sixth" # podc} @string{podc88 = proc # "Seventh" # podc} @string{podc89 = proc # "Eighth" # podc} @string{podc90 = proc # "Ninth" # podc} @string{podc91 = proc # "Tenth" # podc} @string{podc92 = proc # "Eleventh" # podc} @string{podc93 = proc # "Twelfth" # podc} @string{podc94 = proc # "Thirteenth" # podc} @string{podc95 = proc # "Fourteenth" # podc} @string{podc96 = proc # "Fifteenth" # podc} @string{podc97 = proc # "Sixteenth" # podc} @string{podc98 = proc # "Seventeenth" # podc} @string{sosp72 = proc # "Third" # sosp} @string{sosp85 = proc # "Tenth" # sosp} @string{sosp89 = proc # "Twelfth" # sosp} @string{wdag85 = proc # "First" # wdag} @string{wdag87 = proc # "Second" # wdag} @string{wdag89 = proc # "Third" # wdag} @string{wdag90 = proc # "Fourth" # wdag} @string{wdag91 = proc # "Fifth" # wdag} @string{wdag92 = proc # "Sixth" # wdag} @string{wdag93 = proc # "Seventh" # wdag} @string{wdag94 = proc # "Eighth" # wdag} @string{wdag97 = proc # "Eleventh" # wdag} @string{disc98 = proc # "Twelfth" # disc} @string{spaa90 = proc # "Second" # spaa} @string{spaa91 = proc # "Third" # spaa} @string{spaa92 = proc # "Fourth" # spaa} @string{spaa93 = proc # "Fifth" # spaa} @string{spaa98 = proc # "Tenth" # spaa} @string{ppopp90 = proc # "Second" # ppopp} @string{stoc91 = proc # "Twenty-Third" # stoc} @string{pods88 = proc # "Seventh" # pods} @inproceedings{afek:size93, author = {Yehuda Afek and Gideon Stupp}, title = {Synchronization Power Depends on Size}, booktitle = {Proceedings of the 34th IEEE Annual Symposium on the Foundations of Computer Science}, year = {1993}, pages = {196--205}, month = November, organization = IEEE } @inproceedings{afek:size94, author = {Yehuda Afek and Gideon Stupp}, title = {Delimiting the Power of Bounded Size Synchronization Objects}, booktitle = podc94, pages = {42-51}, year = 1994, note = {Los Angeles, CA}, month = {August, 14--17} } @inproceedings{afek:multi97, title = {Disentangling Multi-object Operations}, author = {Yehuda Afek and Michael Merritt and Gadi Taubenfeld and Dan Touitou}, booktitle = podc97, pages = {111-120}, month = {August}, year = 1997, note = {Santa Barbara, CA} } @inproceedings{allemany:solo92, author = {Juan Allemany and Ed W. Felten}, title = {Performance Issues in Non-Blocking Synchronization on Shared Memory Multiprocessors}, booktitle = {Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing}, pages = {125--134}, month = {August}, year = 1992 } @inproceedings{anderson:k-exclusion94, author = {James H. Anderson and Mark Moir}, title = {Using $k$-exclusion to Implement Resilient, Scalable, Shared Objects}, booktitle = { Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing}, note = {Los Angeles, CA}, pages = {141--150}, month = {August, 14--17}, year = 1994 } @inproceedings{anderson:multi95, author = {James H. Anderson and Mark Moir}, title = {Universal Constructions for Multi-Object Operations}, booktitle = {Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing}, note = {Ottawa, Ont. Canada}, pages = {184-193}, month = {August 20--23}, year = 1995 } @inproceedings{anderson:universal95, author = {James H. Anderson and Mark Moir}, title = {Universal Constructions for Large Objects}, booktitle = {9th Intl Workshop on Distributed Algorithms '95}, note = {Lecture Notes in Computer Science, Vol. 972}, publisher = {Springer Verlag}, pages = {168-182}, month = {September}, year = 1995, abstract = { % k-exclusion + real-time, means that read&write are universal on % real-time uniprocessors. } } @InProceedings{anderson:realtime-uni96, author = "Srikanth Ramamurthy and Mark Moir and James H. Anderson", title = "Real-Time Object Sharing with Minimal System Support (Extended Abstract)", pages = "233--242", booktitle = podc96, ISBN = "0-89791-800-2", month = may, publisher = "ACM", address = "New York, USA", year = "1996", } @inproceedings{anderson:realtime95, author = {James H. Anderson and Srikanth Ramamurthy}, title = {Using Lock-Free Objects in Hard Real-Time Applications}, booktitle = {Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing}, note = {Ottawa, Ont. Canada}, pages = {272}, month = {August 20--23}, year = {1995}} @article{anderson:realtime97, author = {James H. Anderson and Srikanth Ramamurthy and Kevin Jeffay}, title = {Real-Time Computing with Lock-Free Shared Objects}, journal = {ACM Transactions on Computer Systems}, volume = 15, number = 2, pages = {134-165}, month = {May}, year = {1997}} @inproceedings{anderson:ccas97, author = {James H. Anderson and Srikanth Ramamurthy and R. Jain}, title = {Implementing Wait-Free Objects on Priority-Based Systems}, booktitle = {Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing}, note = {Santa Barbara, CA}, month = {August}, year = {1997} } @inproceedings{anderson:disc98, author = {James H. Anderson and Rohit Jait and David Ott}, title = {Wait--Free synchronization in Quantum based multiprogrammed systems}, booktitle = disc98, month = {September 24--26}, year = 1998, note = {Andros, Greece} } @inproceedings{anderson:stoc91, author = {R. J. Anderson and H. Woll}, title = {Wait-Free Parallel Algorithms For The Union-Find Problem}, booktitle= stoc91, pages = {370--380}, year = 1991, annote = { Implements concurrent, lock-free up-trees with path halving, using Compare-and-Swap. } } @inproceedings{attiya:binary96, author = {Hagit Attiya and E. Dagan}, title = {Universal Operations: Unary versus Binary}, booktitle = {Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing}, note = {Phila. PA}, month = {May 23-26}, year = 1996 } @inproceedings{attiya:podc98, author = {Hagit Attiya and Arie Fouren}, title = {Adaptive Wait--Free Construction for Closed Objects}, pages = {277--286}, booktitle = podc98, month = {June 28 - July 2}, year = 1998, note = {Puerto Vallarta, Mexico} } @book{attiya:textbook98, author = {Hagit Attiya and Jennifer Welch}, title = {Distributed Computing: Fundamentals, Simulations, and Advanced Topics}, year = 1998, publisher = {McGraw-Hill}, address = {Maidenhead, Berkshire, England} } @inproceedings{barnes:caching93, author = {Gregg Barnes}, title = {A Method for Implementing Lock-Free Shared Data Structures}, pages = {261--270}, booktitle = {Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures}, month = {June}, year = 1993, annote = { Universal method for converting a lock-based implementation into a wait-free one, using the Load-Linked/Store-Conditional pair of primitives. This uses the ``caching method'' in order to avoid the problem with deadlocks that the method of Turek {\em et al.\/} has. } } @techreport{bershad:os-tr91, author = {Brian N. Bershad}, title = {Practical Considerations for Lock-Free Concurrent Objects}, institution = {Carnegie Mellon University}, year = 1991, number = {CMU-CS-91-183}, } @inproceedings{bershad:os93, author = {Brian N. Bershad}, title = {Practical considerations for non-blocking concurrent objects}, booktitle = {Proceedings 13th IEEE International Conference on Distributed Computing Systems}, note = {Los Alamitos CA}, organization = {IEEE Computer Society Press}, pages = {264--273}, month = {May 25--28}, year = {1993} } @techreport{brewer:proteus91, author = {Eric A. Brewer and Chrysanthos N. Dellarocas and Adrian Colbrook and William E. Weihl}, title = {PROTEUS: A High-Performance Parallel-Architecture Simulator}, type = {Technical Report}, number = {MIT/LCS/TR-516}, institution = {MIT Laboratory for Computer Science}, month = {September}, year = {1991} } @inproceedings{chandra:podc98, author = {Tushar Chandra and Prasad Jayanti and King Tan}, title = {A Polylog Time Wait-Free Construction for Closed Objects}, pages = {287--296}, booktitle = podc98, month = {June 28 - July 2}, year = 1998, note = {Puerto Vallarta, Mexico} } @misc{chesson:note96, author = {Greg Chesson}, title = {Personal Communication}, note = {SGI}, month = {December}, year = {1996}} @misc{muir:note99, author = {Steven J. Muir}, title = {Personal Communication}, note = {University of Pennsylvania}, month = jan, year = 1999} @techreport{dwork:contention-cost93, author = {Cynthia Dwork and Maurice Herlihy and Orli Waarts}, title = {Contention in Shared Memory Algorithms}, number = {CRL 93/12}, institution = {Digital Equipment Corp. Cambridge Research Lab}, type = {Technical Report}, month = {August 4th}, year = {1993} } @inproceedings{eberly:disc98, author = {Wayne Eberly and Lisa Higham and Jolanta Warpechowska-Gruca}, title = {Amortized complexity of wait free protocols: the cases of renaming.}, booktitle = disc98, month = {September 24--26}, year = 1998, note = {Andros, Greece} } @inproceedings{fischer:consensus83, author = {Michael J. Fischer and Nancy A. Lynch and Michael S. Paterson}, title = {Impossibility of distributed consensus with one faulty process}, booktitle = {Proceedings of the 2nd ACM Symposium on Principles of Database Systems}, month = {March}, year = 1983, pages = {1--7} } @article{fischer:consensus85, author = {Michael J. Fischer and Nancy A. Lynch and Michael S. Paterson}, title = {Impossibility of distributed consensus with one faulty process}, journal = {Journal of the ACM}, volume = 32, number = 2, month = {April}, year = 1985, pages = {374--382} } @techreport{greenwald:podc98, author = {Michael B. Greenwald}, title = {Non-blocking transactions using binary primitives}, number = {DSG 97/??}, type = {Technical Report}, year = 1997, institution = {Stanford University, Distributed Systems Group} } @phdthesis{greenwald:thesis97, author = {Michael B. Greenwald}, title = {Non-blocking Synchronization and System Design}, school = {Stanford University}, note = {In Progress}, month = {June}, year = 1998 } @inproceedings{her:impossibility88, author = {Maurice Herlihy}, title = {Impossibility and Universality Results for Wait-Free Sycnhronization}, booktitle = podc88, pages = {276-290}, note = {Toronto, Ont., Canada}, month = {August 15-17}, year = 1988 } @article{her:wait-free91, author = "Maurice P. Herlihy", title = "Wait-Free Synchronization", journal = "ACM Transactions on Programming Languages and Systems", volume = "13", number = "1", pages = "124--149", month = jan, year = "1991", url = "http://www.acm.org/pubs/toc/Abstracts/0164-0925/102808.html", abstract = "A {\em wait-free} implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a concensus protocol, for proving statements of the form, ``there is no wait-free implementation of $X$ by $Y$.'' We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: they cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such as {\em test\&set} and {\em fetch\&add}, while more powerful than {\em read} and {\em write}, are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.", } @article{her:toplas93, author = {Maurice Herlihy}, title = {A Methodology For Implementing Highly Concurrent Data Objects}, journal = {ACM Transactions on Programming Languages and Systems}, volume = 15, number = 5, pages = {745--770}, month = {November}, year = 1993, } @inproceedings{her:ppopp90, author = {Maurice P. Herlihy}, title = {A Methodology For Implementing Highly Concurrent Data Structures}, booktitle = ppopp90, pages = {197--206}, month = {March}, note = {New York}, organization = {ACM}, year = 1990 } @article{her:linearizability90, author = {Maurice P. Herlihy and Jeannette M. Wing}, title = {Linearalizability: A Correctness Condition for Concurrent Objects}, journal = {ACM Transactions on Programming Languages and Systems}, volume = 12, number = 3, pages = {463--492}, month = {July}, year = 1990 } @inproceedings{herlihy:disc98, author = {Maurice Herlihy and Sergio Rajesbaum}, title = {A complete classification of wait-free loop agreement tasks}, booktitle = disc98, month = {September 24--26}, year = 1998, note = {Andros, Greece} } @Article{herlihy:tods90, key = "Herlihy", author = "Maurice Herlihy", title = "Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstrct Data Types", journal = "ACM Transactions on Database Systems", pages = "96--124", volume = "15", number = "1", month = mar, year = "1990" } @inproceedings{israeli:heap93, author = {Amos Israeli and Lihu Rappaport}, title = {Efficient wait-free implementation of a concurrent priority queue}, booktitle = wdag93, note = {Lausanne, Switzerland, also published as {\em Lecture Notes in Computer Science 725}}, publisher = {Springer Verlag}, pages = {1--17}, month = {September}, year = {1993} } @inproceedings{israeli:universal94, author = {Amos Israeli and Lihu Rappaport}, title = {Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives}, booktitle = {Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing}, note = {Los Angeles, CA}, pages = {151--160}, month = {August 14--17}, year = {1994} } @inproceedings{jayanti:disc98, author = {Prasad Jayanti}, title = {A complete and constant time wait-free implementation of CAS from LL/SC and vise versa}, booktitle = disc98, month = {September 24--26}, year = 1998, note = {Andros, Greece} } @inproceedings{jayanti:local-podc98, author = {Prasad Jayanti}, title = {A Lower Bound on the Local Time Complexity of Universal Constructions}, pages = {183--192}, booktitle = podc98, month = {June 28 - July 2}, year = 1998, note = {Puerto Vallarta, Mexico} } @inproceedings{jayanti:random-podc98, author = {Prasad Jayanti}, title = {A Time Complexity Lower Bound for Randomized Implementations of Some Shared Objects}, pages = {201--210}, booktitle = podc98, month = {June 28 - July 2}, year = 1998, note = {Puerto Vallarta, Mexico} } @techreport{johnson:spinlock93, author = {Theodore Johnson and K. Harathi}, title = {A Prioritized Multiprocessor Spin Lock}, type = {Technical Report}, number = {TR93-005}, institution = {Dept. of Computer and Information Science, University of Florida}, year = 1993} @techreport{johnson:performance93, author = {Theodore Johnson}, title = {Characterizing the Performance of Algorithms for Lock-Free Objects}, type = {Technical Report}, number = {93-021}, institution = {Dept. of Computer and Information Science, University of Florida}, year = 1993} @techreport{johnson:ics94, author = {Theodore Johnson and Krishna Harathi}, title = {Interruptible Critical Sections}, type = {Technical Report}, number = {94-007}, institution = {Dept. of Computer and Information Science, University of Florida}, year = 1994} @article{kung:tods81, author = {H.T. Kung and John Robinson}, title = {On Optimistic Methods of Concurrency Control}, journal = {ACM Transactions On Database Systems}, pages = {213--226}, year = {1981}, month = {June}, volume = 6, number = 2} @article{lamport:consensus80, author = {Marshall C. Pease and Robert E. Shostak and Leslie Lamport}, title = {Reaching Agreement in the presence of faults}, journal = {Journal of the ACM}, volume = 27, number = 2, pages = {228--234}, month = {April}, year = 1980}r @inproceedings{lamarca:eval94, author = {Anthony LaMarca}, title = {A Performance Evaluation of Lock-Free Synchronization Protocols}, booktitle = {Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing}, note = {Los Angeles, CA}, pages = {130--140}, month = {August 14--17}, year = {1994}} @inproceedings{lanin:pods88, author = {V. Lanin and D. Shasha}, title = {Concurrent Set Manipulation Without Locking}, pages = {211--220}, year = 1988, booktitle = pods88 } @inproceedings{menke:podc98, author = {Stephen Menke and Mark Moir and Srikath Ramamurthy}, title = {Synchronization Mechanisms in the {SCRAMNet+} Systems}, pages = {71--80}, booktitle = podc98, month = {June 28 - July 2}, year = 1998, note = {Puerto Vallarta, Mexico} } @inproceedings{michael:queue96, author = {Maged M. Michael and Michael L. Scott}, title = {Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms}, booktitle = podc96, note = {Phila. PA}, pages = {267--276}, month = {May 23-26}, year = 1996 }} @techreport{michael:valois95, author = {Maged M. Michael and Michael L. Scott}, title = {Correction of a Memory Management Method for Lock-Free Data Structures}, type = {Technical Report}, number = {599}, institution = {Computer Science Department, University of Rochester}, month = {December}, year = {1995} } @techreport{michael:structs96, author = {Maged M. Michael and Michael L. Scott}, title = {Concurrent Update on Multiprogrammed Shared Memory Multiprocessors}, number = 614, type = {Technical Report}, institution = {Computer Science Department, University of Rochester}, month = {April}, year = {1996} } @TechReport{michael:primitives94, author = "Maged M. Michael and Michael L. Scott", title = "Scalability of Atomic Primitives on Distributed Shared Memory Multiprocessors", institution = "University of Rochester, Computer Science Department", number = "TR528", month = jul, year = "1994", url = "ftp://ftp.cs.rochester.edu/pub/papers/systems/94.tr528.Scalability_of_atomic_primitives.ps.Z", abstract = "Many hardware primitives have been proposed for synchronization and atomic memory update on shared-memory multiprocessors. In this paper, we focus on general-purpose primitives that have proven popular on small-scale bus-based machines, but have yet to become widely available on large-scale, distributed-memory machines. Specifically, we propose several alternative implementations of fetch\_and\_$\backslash$Phi, compare\_and\_swap, and load\_linked/store\_conditional. We then analyze the performance of these implementations for various data sharing patterns, in both real and synthetic applications. Our results indicate that good overall performance can be obtained by implementing compare\_and\_swap in a multiprocessor's cache controllers, and by providing an additional instruction to load an exclusive copy of a line.", } @inproceeedings{michael:primitives95, author = {Maged M. Michael and Michael L. Scott}, title = {Implementation of General-purpose atomic primitives for distributed shared-memoery multiprocessors}, booktitle = {Proceedings of the First International Symposium on High Performance Computer Architecture}, pages = {222-231}, note = {Raleigh, NC}, month = {January}, year = {1995} } @inproceedings{moir:primitives97, author = {Mark Moir}, title = {Practical Implementations of Non-Blocking Synchronization Primitives}, booktitle = podc97, pages = {219--228}, month = {August}, year = 1997, note = {Santa Barbara, CA} } @inproceedings{moir:wdag97, author = {Mark Moir}, title = {Transparent Support for Wait-Free Transactions}, booktitle = wdag97, publisher = {Springer Verlag}, pages = {305--319}, note = {Saarbrucken, Germany, also published as {\em Lecture Notes in Computer Science Vol. 1320}}, month = {September 24--26}, year = {1997} } @inproceedings{plotkin:sticky89, author = {Serge A. Plotkin}, title = {Sticky Bits and the Universality of Consensus}, booktitle = podc89, pages = {159-175}, note = {Edmonton, Alberta, Canada}, month = {August}, year = 1989 } @inproceedings{ruppert:podc97, author = {Eric Ruppert}, title = {Determining Consensus Numbers}, booktitle = podc97, month = {August}, year = 1997, note = {Santa Barbara, CA} } @inproceedings{ruppert:podc98, author = {Eric Ruppert}, title = {Consensus Numbers of Multi-Objects}, pages = {211--217}, booktitle = podc98, month = {June 28 - July 2}, year = 1998, note = {Puerto Vallarta, Mexico} } @inproceedings{schenk:hierarchy97, author = {Eric Schenk}, title = {The Concensus Hierarchy is not Robust}, booktitle = {Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing}, note = {Santa Barbara, CA}, month = {August}, year = {1997} } @inproceedings{shavit:STM95, author = {Nir Shavit and Dan Touitou}, title = {Software Transactional Memory}, booktitle = podc95, note = {Ottawa, Ont. Canada}, pages = {204--213}, month = {August 20--23}, year = {1995} } @inproceedings{shavit:sort97, author = {Nir Shavit, E. Upfal and Asaph Zemach}, title = {A Wait-Free Sorting Algorithm}, booktitle = podc97, note = {Santa Barbara, CA}, month = {August}, year = 1997, pages = {121-128} } @article{shavit:diffract96, author = {Nir Shavit and Asaph Zemach}, title = {Diffracting Trees}, pages = {385--428}, journal = tocs, month = {November}, year = 1996, volume = 14, number = 2} @techreport{treiber:stack86, author = {R.K.Treiber}, title = {Systems Programming: Coping with Parallelism}, number = {RJ5118}, year = 1986, month = {April}, institution = {IBM Almaden Research Center}} @inproceedings{turek:stack92, author = {J. Turek and D. Shasha and S. Prakash}, title = {Locking without blocking: Making Lock-Based Concurrent Data Structure Algorithms Non-Blocking}, booktitle = {Proceedings of the 1992 Principles of Database Systems}, pages = {212-222}, year = 1992 } @inproceedings{valois:lists95, author = {John Valois}, title = {Lock-Free Linked Lists Using Compare-and-Swap}, booktitle = {Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing}, note = {Ottawa, Ont. Canada}, pages = {214-222}, month = {August 20--23}, year = 1995 } @misc{valois:space96, author = {John Valois}, title = {Space Bounds for Transactional Synchronization, unpublished manuscript, November, 1996 }} @string{columbia = "Columbia University"} @string{tr = "Technical Report"} @string{proc = "Proceedings of the "} @string{proc1 = "Proceedings of "} @string{sosp = " Symposium on Operating Systems Principles"} @string{spaa = " Symposium on Parallel Algorithms and Architectures"} @string{spaa98 = proc # "Tenth" # spaa} @string{sosp89 = proc # "Twelfth" # sosp} @string{tocs = "{ACM} Transactions on Computer Systems"} @inproceedings{blumofe:deque98, author = {Nimar S. Arora and Robert D. Blumofe and C. Greg Plaxton}, title = {Thread scheduling for multiprogrammed multiprocessors}, annot = {Presents a non-blocking implementation of a work-stealing scheduler by using a non-blocking implementation of a DEQUE using only CAS. It depends on single reader and other specifics of the work-stealing algorithm.}, booktitle = spaa98, pages = {119--129}, note = {Puerto Vallarta, Mexico}, month = {June 28 -- July 2}, year = 1998 } @inproceedings{cher:cachekernel94, author = {David R. Cheriton and Kenneth J. Duda}, title = {A Caching Model of Operating System Kernel Functionality}, booktitle ={Proceedings of 1st Symposium on Operation Systems Design and Implementation}, note = {Monterey, CA}, pages = {179--193}, month = {November 14--17}, year = 1994} @inproceedings{greenwald:osdi96, author = {Michael B. Greenwald and David R. Cheriton}, title = {The synergy between non-blocking synchronization and operating system structure}, booktitle = {2nd Symposium on Operating Systems Design and Implementation}, note = {Seattle, WA.}, pages = {123-136}, month = {October 28--31}, year = 1996} @techreport{massalin:synthesis91, author = {Henry Massalin and Carleton Pu}, title = {A Lock-Free Multiprocessor {OS} Kernel}, institution = columbia, type = tr, number = {CUCS--005--91}, month = {October}, year = 1991, annote = { Describes Synthesis, a multiprocessor OS built entirely using lock-free data structures in the kernel. The algorithms often rely on the powerful two word Compare-and-Swap instruction found on the Motorola~68020. } } @inproceedings{massalin:sosp89, author = {Henry Massalin and Calton Pu}, title = {Threads and Input/Output in the Synthesis Kernel}, booktitle = sosp89, address = {Arizona}, pages = {191--201}, month = {December}, year = {1989} } @phdthesis{massalin:thesis92, author = {Henry Massalin}, title = {Synthesis: An Efficient Implementation of Fundamental Operating System Services}, school = {Columbia University}, year = 1992 } @article{scott:scheduler97, author = {Leonidas I. Kontothanassis and Robert W. Wisniewski and Michael L. Scott}, title = {Scheduler-Conscious Synchronization}, pages = {3--40}, journal = tocs, month = {February}, year = 1997, volume = 15, number = 1, annote = { Universal transformations are too expensive, so the authors investigate preemptible locks concentrating on the advantages available by scheduler support. } } @string{proc = "Proceedings of the "} @string{isca = " Annual International Symposium on Computer Architecture"} @string{isca95 = proc # "Twenty Second" # isca} @Manual{68000man, title = "M68000 Family Programmer's Reference Manual", organization = "Motorola, Inc.", year = 1989 } @Manual{ALPHAman, author = {R. Sites}, title = {DEC Alpha Architecture}, organization = {Digital Press}, address = {Burlington, Massachussets}, year = 1992 } @Manual{PowerPC, title = "PowerPC 601 RISC Mircroprocessor User's Manual", organization = "Motorola, Inc.", year = 1993 } @Manual{R4000, author = {Joseph Heinrich}, title = {MIPS R4000 User's Manual}, organization = {PTR Prentice Hall}, address = {Englewood Cliffs, NJ}, year = 1993 } @manual{Sparcmanv8, author = {SUN Microsystems, Inc.}, title = {Sparc Architecture Manual v8} } @manual{Sparcman, organization = {SUN Microsystems, Inc.}, title = {The SPARC Architecture Manual Version 9} } @manual{VAXman, organization = {Digital Equipment Corporation}, title = {VAX11 Architecture Handbook}, year = {1979 } } \comment{ @misc{greenwald:hardware-dcas97, author = {Michael Greenwald}, title = {A Hardware Implementation of a Non-blocking, Atomic, Binary Synchronization Primitive for a RISC Processor, {\em DSG-97-?? ??}, Stanford, CA. May, 1997. }} @inproceedings{greenwald:asplos98, author = {Michael B. Greenwald and David R. Cheriton}, title = {Optimal Architectural Suppport for Software Synchronization}, booktitle = {Submitted to ASPLOS '98}, year = 1998} } @book{hennessy:arch90, author = {John L. Hennessy and David A. Patterson}, title = {Computer architecture: a quantitative approach}, year = {1990}, publisher = {Morgan Kaufmann}, address = {San Francisco, California}, edition = {First} } @book{patterson:arch94, author = {David A. Patterson and John L. Hennessy}, title = {Computer Organization and Design: The Hardware/Software Interface}, year = {1994}, publisher = {Morgan Kaufmann}, address = {San Francisco, California}, edition = {First} } @book{hennessy:arch96, author = {John L. Hennessy and David A. Patterson}, title = {Computer architecture: a quantitative approach}, year = {1996}, publisher = {Morgan Kaufmann}, address = {San Francisco, California}, edition = {Second} } @techreport{her:trans-mem-tr92, author = {Maurice P. Herlihy and J. Eliot B. Moss}, title = {Transactional Memory: {A}rchitectural Support for Lock-Free Data Structures}, number = {CRL 92/07}, type = {Technical Report}, year = 1992, institution = {Digital Equipment Corp. Cambridge Research Lab} } @inproceedings{her:trans-mem93, author = {Maurice P. Herlihy and J. Eliot B. Moss}, title = {Transactional Memory: Architectural support for Lock-Free Data Structures}, booktitle ={1993 20th Annual Symposium on Computer Architecture}, note = {San Diego, CA}, pages = {289--301}, month = {May}, year = 1993 } @misc{ibm:370, author = {IBM}, title = {System/370 principles of operation}, note = {Order Number GA22-7000.} } @inproceedings{james:ccas95, author = {David V. James and David Singer}, title = {Nonblocking Shared-Data Updates using Conditional Lock Primitives}, booktitle = {Proceedings of the 2nd International Workshop on SCI-based High-Performance Low-Cost Computing}, note = {Santa Clara, CA}, pages = {67--73}, month = {March 21}, year = 1995 } @misc{jensen:llsc87, author = {E. H. Jensen and G. W. Hagensen and J. M. Broughton}, title = {A New Approach to Exclusive Data Access in Shared Memory Multiprocessors, TR UCRL-97663, Lawrence Livermore National Laboratory, November 1987. }} @article{stone:oklahoma93, author = {J. Stone and H. Stone and P. Heidelbergher and J. Turek}, title = {Multiple Reservations and the Oklahoma Update}, journal = {IEEE Parallel and Distributed Technology}, volume = 1, number = 4, year = 1993, pages = {58--71}, month = {November} } @inproceedings{gupta:isca95, author = {Steven Cameron Woo and Moriyoshi Ohara and Evan Torrie and Jaswinder Pal Singh and Anoop Gupta}, title = {The {SPLASH-2} Programs: Characterization and Methodological Considerations}, pages = {24--36}, month = {June}, booktitle = isca95, year = 1995 } @string{proc = "Proceedings of the "} @string{sosp85 = proc # "Tenth" # sosp} @string{sosp91 = proc # "Thirteenth" # sosp} @string{sosp97 = proc # "Sixteenth" # sosp} @string{cacm = "Communications of the {ACM}"} @article{anderson:queuelocks90, author={T. E. Anderson}, title={The performance of Spin Lock Alternatives for Shared-Memory Multiprocessors}, journal = {IEEE Transactions on Parallel and Distributed Systems}, month = {January}, year = 1990, pages = {6--16}, volume = 1, number = 1} @InProceedings{anderson:sosp91, author = "Thomas E. Anderson and Brian N. Bershad and Edward D. Lazowska and Henry M. Levy", title = "Scheduler Activations: effective kernel support for the user-level management of parallelism", booktitle = sosp91, address = "Asilomar, Pacific Grove, CA", publisher = "ACM SIGOPS", month = oct, year = "1991", pages = "95--109", note = "Published in ACM Operating Systems Review Vol.25, No.5, 1991. Also published ACM Transactions on Computer Systems Vol.10 No.1, pp.53--70, Feb 92", note2 = "HAR", url = "http://www.acm.org:80/pubs/citations/journals/tocs/1992-10-1/p53-anderson/", abstract = "Threads can be supported either by the operating system kernel or by user-level library code in the appliation address space, but neither approach has been fully satisfactory. This paper addresses this dilemma. First, we argue that the performance of kernel threads is inherently worse than that of user-level threads, rather than this being an artifact of existing implementations; we thus argue that managing parallelism at the user level is essential to high-performance parallel computing. Next, we argue that the lack of system integration exhibited by user-level threads is a consequence of the lack of kernel support for user-level threads provided by contemporary multiprocessor operating systems; we thus argue that kernel threads or processes, as currently conceived, ar the wrong abstraction on which to support user-level management of parallelism. Finally, we describe the design, implementation, and performance of a new kernel interface and user-level thread package that together provide the same functionality as kernel threads without compromising the performance and flexibility advantages of user-level management of parallelism.", } @inproceedings{andrews:filaments94, author = {Vincent W. Freeh and David K. Lowenthal and Gregory R. Andrews}, title = {Distributed Filaments: efficient fine-grain parallelism on a cluster of workstations}, booktitle ={Proceedings of 1st Symposium on Operation Systems Design and Implementation}, note = {Monterey, CA}, pages = {201--213}, month = {November 14--17}, year = 1994} @inproceedings{batory:scalable93, author = {Don Batory and Vivek Singhal and Marty Sirkin and Jeff Thomas}, title = {Scalable Software Libraries}, booktitle = {Proceedings of ACM SIGSOFT '93}, note = {CA}, pages = {191--199}, month = {December}, year = {1993} } @inproceedings{bershad:ras92, author = {Brian N. Bershad and David D. Redell and John R. Ellis}, title = {Fast Mutual Exclusion for Uniprocessors}, pages = {223--233}, year = 1992, booktitle = asplos92, annote = { Use of restartable atomic sequences on uniprocessors for optimistic synchronization. } } @article{blumofe:cilk96, author = {Robert D. Blumofe and Christopher F. Joerg and Bradley C. Kuszmaul and Charles E. Leiserson and keith H. Randall and Yuli Zhou}, title = {Cilk: an efficient multithreaded runtime system}, journal = {Journal of Parallel and Distributed Computing}, volume = 37, number = 1, pages = {55-69}, month = {August}, year = 1996 } @inproceedings{blumofe:work-stealing94, author = {Robert D. Blumofe and Charles E. Leiserson}, title = {Scheduling multi-threaded computations by work-stealing}, booktitle = {Proceedings of the 35th Annual Symposium on Foundation of Computer Science}, note = {Santa Fe, New Mexico}, pages = {356--368}, month = {November}, year = {1994} } @book{booch:components87, author = {G. Booch}, title = {Software Components with Ada}, publisher = {Benjamin/Cummings}, year = 1987 } @article{chen:rtsj90, author = {M. I. Chen and K. J. Lin}, title = {Dynamic priority ceiling: A concurrency control protocol for real-time systems}, journal = {Real-Time Systems Journal}, pages = {325--346}, year = 1990, volume = 2, number = 4} @article{cher:mem-based-msg93, author = "David R. Cheriton and Robert A. Kutter", title = "Optimized Memory-Based Messaging: Leveraging the Memory System for High-Performance Communication", editor = "{USENIX}", journal = "Computing Systems Journal", publisher = "USENIX", address = "Berkeley, CA, USA", month = "Summer", year = "1996", volume = "9", number = "3", institution = "Stanford University", pages = "179--215", bibdate = "Wed Aug 13 10:48:45 MDT 1997", note = {Also available as Stanford Computer Science Technical Report TR-94-1506}, abstract = "Memory-based messaging, passing messages between programs using shared memory, is a recognized technique for efficient communication that takes advantage of memory system performance. However, the conventional operating system support for this approach is inefficient, especially for large-scale multiprocessor interconnects, and is too complex to effectively support in hardware. This paper describes hardware and software optimizations for memory-based messaging that efficiently exploit the mechanisms of the memory system to provide superior communication performance. We describe the overall model of optimized memory-based messaging, its implementation in an operating system kernel and hardware support for this approach in a scalable multiprocessor architecture. The optimizations include address-valued signals, message-oriented memory consistency and automatic signaling on write. Performance evaluations show these extensions provide a three-to-five-fold improvement in communication performance over a comparable software-only implementation." } @inproceedings{cher:mp3d91, author = {David R. Cheriton and Hendrik A. Goosen and Philip Machanick}, title = {Restructuring a Parallel Simulation to Improve Cache Behavior in a Shared-Memory Multiprocessor: A First Experience}, booktitle = {Proceedings of the International Symposium on Shared Memory Multiprocessing}, note = {Tokyo, Japan}, pages = {23--31}, month = {April}, year = {1991} } @inproceedings{cher:mp3d93, author = {David R. Cheriton and Hendrik A. Goosen and Hugh Holbrook and Philip Machanick}, title = {Restructuring a Parallel Simulation to Improve Cache Behavior in a Shared-Memory Multiprocessor: The value of distributed synchronization}, booktitle = {Proceedings of the Seventh Workshop on Parallel and Distributed Simulation}, pages = {159--162}, month = {May}, year = {1993} } @article{cher:paradigm91, author = {David R. Cheriton and Henk Goosen and Patrick Boyle}, title = {ParaDiGM: A Highly Scalable Shared-Memory Multi-Computer Architecture}, journal = {IEEE Computer}, volume = 24, number = 2, month = {February}, year = 1991 } @article{cher:V88, author = {David R. Cheriton}, title = {The V Distributed System}, journal = {Communications of the ACM}, volume = 31, number = 3, pages = {314--333}, month = {March}, year = 1988 } @article{cher:V, author = {David R. Cheriton}, title = {The V distributed operating system}, journal = {Communications of the ACM}, volume = 31, number = 2, pages = {105--115}, month = {February}, year = 1988 } @inproceedings{clark:swift85, author = {David D. Clark}, title = {The Structuring of Systems Using Upcalls}, note = {Orcas Island, WA}, year = {1985}, booktitle = sosp85, pages = {171--180} } @inproceedings{druschel:osiris94, author = {Peter Druschel and Larry L. Peterson and B.S.Davies}, title = {Experiences with a High Speed Network Adaptor: A Software Perspective}, booktitle = {Proceedings of ACM SIGCOMM '94}, pages = {2--13}, month = {September}, year = 1994, note = {London} } @article{finkel:dib87, author = {Raphael Finkel and Udi Manber}, title = {DIB --- a distributed implementation of backtracking}, journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)}, volume = 9, number = 2, pages = {235--256}, month = {April}, year = 1987} @book{Gray93, author = {Jim Gray and Andreas Reuter}, title = {Transaction Processing: Concepts and Techniques}, year = 1993, publisher = {Morgan Kaufmann}, series = {The Morgan Kaufmann Series in Data Management Systems}, address = {San Francisco, California} } @article{gray:ieee91, author = {Jim Gray and Daniel P. Siewiorek}, title = {High-Availability Computer Systems}, journal = {IEEE Computer}, month = {September}, year = 1991, volume = 24, number = 9, pages = {39--48}, annot = {Mentions that 90 percent of failures are OS, and only 10 percent hardware} } @inproceedings{gupta92, author = {J. Torrellas and A. Gupta and J. Hennessy}, title = {Characterizing the Caching and Synchronization Performance of a Multiprocessor Operating System}, booktitle = {Fifth International Conference on Architectural Support for Programming Languages and Operating Systems}, pages = {162--174}, month = {October}, year = 1992 } @inproceedings{halstead:multilisp84, author = {Robert H. {Halstead Jr.}}, title = {Implementation of Multilisp: Lisp on a multiprocessor}, booktitle = {Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming}, pages = {9--17}, note = {Austin, TX}, month = {August}, year = 1984 } @misc{jpl:pathfinder-website-tax, author = {Donna Shirley}, month = {July 21}, year = {1997}, title = {{\tt http://quest.arc.nasa.gov/\-mars/ask/about\--mars\--path\-/How\_\-much\-\_we\-\_are\-\_pay\-ing\-\_with\-\_\-our\-\_tax\_\-dol\-lars\_for\-\_Pathfinder.txt}}, URL = {{\tt http://quest.arc.nasa.gov/mars/ask/about-mars-path/How\_much\_we\_are\_paying\_with\_our\_tax\_dollars\_for\_Pathfinder.txt}} } @misc{jpl:pathfinder-website-cost, author = {Donna Shirley}, month = {December 3}, year = {1997}, title = {{\tt http://quest.arc.nasa.gov/mars/ask/about\--mars\--path\-/Most\_\-expens\-ive\_\-part\_\-of\_MPF.txt}}, URL = {{\tt http://quest.arc.nasa.gov/mars/ask/about-mars-path/Most\_expensive\_part\_of\_MPF.txt}} } @inproceedings{kagi:qolb97, author = {Alain Kagi and Doug Burner and James R. Goodman}, title = {Efficient Synchronization: Let Them Eat QOLB}, booktitle = {24th International Symposium on Computer Architecture (ISCA)}, month = {June}, year = {1997}, publisher = {ACM} } @inproceedings{kuszmaul:work-stealing98, author = {Michael S. Bernstein and Bradley C. Kuszmaul}, title = {Communications-Efficient multithreading on wide-area networks ({B}rief Announcement, {SPAA} Revue)}, booktitle = {Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)}, note = {Puerto Vallarta, Mexico}, month = {June}, year = {1998} } @article{lampson:confinement73, author = {Butler W. Lampson}, title = {A note on the confinement problem}, journal = {Communications of the ACM}, volume = 16, number = 5, pages = {613-615}, month = {October}, year = 1973 } @InProceedings{lampson:sosp83, author = "Butler W. Lampson", title = "Hints for Computer System Design", booktitle = "Proceedings of the ACM Symposium on Operating System Principles", organization = "ACM", month = dec, year = "1983", pages = "33--48", abstract = "Experience with the design and implementation of a number of computer systems, and the study of many other systems, has led to some general hints for system design which are described here. They are illustrated by a number of examples, ranging from hardware such as the Alto and the Dorado to applications programs such a Bravo and Star.", bibdate = "Sat Jan 12 16:36:15 1985", note = {Reprinted in {\em IEEE Software} 1, 1 (Jan. 1984), pp 11--28}, } @article{lampson:mesa80, author = {Butler W. Lampson and David D. Redell}, title = {Experiences with Processes and Monitors in Mesa}, journal = CACM, volume = 23, number = 2, year = 1980, pages = {105--117}, month = {February}} @inproceedings{legedza:parsim96, author = {Ulana Legedza and William E. Weihl}, title = {Reducing Synchronization Overhead in Parallel Simulation}, year = 1996, note = {Phil. PA}, booktitle = {Proceedings of the 10th ACM Workshop on Parallel and Distributed Simulation}, annot = {Mentions that for fine grained simulation synchronization overhead is between 70 and 90 percent of total time} } @article{levoy:visualization94, author = {Jaswinder Pal Singh and Anoop Gupta and Marc Levoy}, title = {Parallel visualization algorithms: Performance and architectural implications}, journal = {IEEE Computer}, volume = 27, number = 7, pages = {45--55}, month = {July}, year = 1994} @InProceedings{linial:focs87, title = "Distributive Graph Algorithms---Global Solutions from Local Data", author = "Nathan Linial", pages = "331--335", booktitle = "Proceedings of the 28th Annual Symposium on Foundations of Computer Science", ISBN = "0-8186-0807-2", editor = "Ashok K. Chandra", month = "12--14 " # oct, year = "1987", address = "Los Angeles, California", organization = "IEEE", publisher = "IEEE Computer Society Press", } @misc{lispm:atomic-ops87, author={Symbolics, Inc.}, title={Genera 7.4 Documentation Set}, year=1989, volume=8, pages={38-39}, institution={Symbolics, Inc.}} @inproceedings{lowell:sosp97, author = {David E. Lowell and Peter M. Chen}, title = {Free transactions with {Rio Vista}}, booktitle = sosp97, address = {St. Malo, France}, year = 1997, pages = {92--101}, publisher = "ACM SIGOPS", month = oct, note = "Published in ACM Operating Systems Review Vol.31, No.5, Dec. 1997.", } @book{Lynch94, author = {Nancy Lynch and Michael Merritt and William Weihl and Alan Fekete}, title = {Atomic Transactions}, year = 1994, publisher = {Morgan Kaufmann}, address = {San Mateo, California}, series = {The Morgan Kaufmann Series in Data Management Systems} } @Article{mccabe:tose76, author = "Thomas J. McCabe", title = "A {C}omplexity {M}easure", journal = "IEEE Transactions on Software Engineering", year = "1976", volume = "2", number = "4", pages = "308--320", month = dec, } @InProceedings{mccabe:icse76, author = "T. J. McCabe", title = "A complexity measure", pages = "407", booktitle = "Proceedings of the ~2nd~ International Conference on Software Engineering", year = "1976", publisher = "IEEE Computer Society Press", month = oct, } @article{mcs:tocs91, author = {J.M. Mellor-Crummey and Michael L. Scott}, title = {Algorithms for scalable Synchronization on Shared-Memory Multiprocessors}, journal = {ACM Transactions on Computer Systems}, volume = 9, number = 1, year = 1991, pages = {21-65}, month = {February}} @Article{mitchell:cacm82, author = "James G. Mitchell and Jeremy Dion", title = "A Comparison of Two Network-Based File Servers", journal = "Communications of the ACM", volume = "25", number = "4", pages = "233--245", month = apr, year = "1982", coden = "CACMA2", ISSN = "0001-0782", bibdate = "Wed Sep 21 23:36:34 1994", abstract = "This paper compares two working network-based file servers, Xerox Distributed File System (XDFS) implemented at the Xerox Palo Alto Research Center, and the Cambridge File Server (CFS) implemented at the Cambridge University Computer Laboratory. Both servers support concurrent random access to files using atomic transactions, both are connected to local area networks, and both have been in service long enough to enable us to draw lessons from them for future file servers. We compare the servers in terms of design goals, implementation issues, performance, and their relative successes and failures, and discuss what we would do differently next time.", note = {(Originally in SOSP '81)}, keywords = "CACM operating XDFS CFS Cambridge lans", } @InProceedings{mogul:livelock96, author = "Jeffrey C. Mogul and K. K. Ramakrishnan", title = "Eliminating Receive Livelock in an Interrupt-driven Kernel", editor = "{USENIX Association}", booktitle = "Proceedings of the {USENIX} 1996 annual technical conference: January 22--26, 1996, San Diego, California, {USA}", publisher = "USENIX", address = "Berkeley, CA, USA", ISBN = "1-880446-76-6", series = "USENIX Conference Proceedings 1996", pages = "99--111", day = "22--26", month = jan, year = "1996", affiliation = "Digital Equipment Corporation Western Research Laboratory (author \#1). AT\&T Bell Laboratories (author \#2)"} @TechReport{reed:thesis78, type = "Technical Report", number = "MIT/LCS/TR-205", title = "{Naming} {and} {Synchronization} {in} {a} {Decentralized} {Computer} {System}", month = oct, pages = "181", year = "1978", bibdate = "February 25, 1995", author = "David P. Reed", abstract = "In this dissertation a new approach to the synchronization of accesses to shared data objects is developed. Traditional approaches to the synchronization problems of shared data accessed by concurrently running computations have relied on mutual exclusion -- the ability of one computation to stop the execution of other computations that might access or change shared data accessed by that computation. Our approach is quite different. We regard an object that is modifiable as a sequence of immutable versions; each version is the state of the object after an update is made to the object. Synchronization can then be treated as a mechanism for naming versions to be read and for defining where in the sequence of versions the version resulting from some update should be placed. In systems based on mutual exclusion, the timing of accesses selects the versions accessed. In the system developed here, called NAMOS, versions have two component names consisting of the name of an object and a pseudo-time, the name of the system state to which the version belongs. By giving programs control over the pseudo-time in which an access is made, synchronization of access to multiple objects is simplified. NAMOS is intended to be used in an environment where unreliable components, such as communication lines and processors, and autonomous control of resources occasionally cause certain objects to become inaccessible, perhaps in the middle of an atomic transaction. Computations may also suddenly halt (perhaps as the result of a system crash) never to be restarted. NAMOS provides facilities for recovering from such sudden failures, grouping updates into sets called possibilities, such that failure of any update belonging to a possibility prevents all of the other updates in the possibility. The naming mechanism of NAMOS also provides a useful tool for restoring a consistent state of the system after a failure resulting in irrecoverable loss of information or a user mistake resulting in an inconsistent state. An important motivation for the development of NAMOS is the need to support decentralized development of application systems by combining existing application systems that deal with shared data. NAMOS supports the construction of modules that locally ensure their own correct synchronization and recovery from inaccessibility. Larger modules that use several separately designed modules can then be constructed, perhaps with additional synchronization constraints, without modifying the modules used. In most systems based on mutual exclusion, such post hoc integration of modules is difficult or impossible.", institution = "Massachusetts Institute of Technology, Laboratory for Computer Science", } @misc{reeves97:email, title = {E-mail and newsgroup posting}, author = {Glenn E. Reeves}, note = {{\tt Glenn.E.Reeves@jpl.nasa.gov}, full text and related links available from {\small {\tt http://www.research.microsoft.com/research/os/mbj/Mars\_Pathfinder/}}}, month = {December 15}, year = {1997} } @article{ryan:portable-sync99, author = {Stein J. Ryan}, title = {Synchronization in Portable Device Drivers}, pages = {18--25}, journal = {Operating System Review}, month = {January}, year = 1999, volume = 33, number = 1, publisher = {ACM SIGOPS}, annote = { Overviews different synchronization mechanisms offered to device drivers by different OS kernels. Ignores NBS. Shows the difficulties in writing portable device drivers due to differing synchronization mechanisms. (NBS would allow simpler portability.) } } @article{saltzer:end2end84, author = "Jerome H. Saltzer and David P. Reed and David D. Clark", title = "End-To-End Arguments in System Design", journal = "ACM Transactions on Computer Systems", volume = "2", number = "4", month = nov, year = "1984", pages = "277--288"} @inproceedings{seltzer:osdi96, author = {Margo I. Seltzer and Yasuhiro Endo and Christopher Small and Keith A. Smith}, title = {Dealing with disaster: surviving misbehaved kernel exetensions}, booktitle = {2nd Symposium on Operating Systems Design and Implementation}, note = {Seattle, WA.}, pages = {213-227}, month = {October 28--31}, year = 1996, annot = {Implements kernel extensions as transactions}} @article{sha:toc90, author = {L. Sha and R. Rajkumar and J. P. Lehoczky}, title = {Priority Inheritance Protocols: An Approach to Real-Time Synchronization}, journal = {IEEE Transactions on Computers}, volume = 39, pages = {1175--1185}, month = {September}, year = 1990} @book{silberschatz:os83, author = {Abraham Silberschatz and James Peterson}, title = {Operating System Concepts (Alternate Edition)}, publisher = {Addison Wesley}, year = {1988} } @Article{Sturgis:osr80, author = "Howard E. Sturgis and James G. Mitchell and Jay E. Israel", title = "Issues in the Design of a Distributed File System", journal = "ACM Operating Systems Review", volume = "14", number = "3", pages = "55--69", month = jul, year = "1980", } @techreport{sturgis:xerox-tr74, author = "Howard E. Sturgis", title = {A Postmortem for a Time Sharing System}, type = "Technical Report", number = "CSL-74-1", year = "1974", bibdate = "February 25, 1995", institution = {Xerox Palo Alto Research Center}, pages = 100, month = jan, note = {(Also PhD thesis, UCBerkeley, May 73.)} } @misc{wilner:talk97, author = {David Wilner}, authortitle = {CTO of Wind River Systems}, title = {Invited Talk, {\em IEEE Real-Time Systems Syposium}}, conference = {IEEE Real-Time Systems Syposium}, month = {December}, year = {1997}, note = {(Summarized in RISKS 19.49 on December 9, 1997, by Mike Jones.)} } @inproceedings{zelesko:rpc96, author = {Matt Zelesko and David R. Cheriton}, title = {Specializing Object Oriented RPC for Functionality and Performance}, booktitle = {Proceedings 16th IEEE International Conference on Distributed Computing Systems}, organization = {IEEE Computer Society Press}, month = {May 27-30}, year = 1996 } % References on concurrent objects, lock-free data structures, % mutual exclusion, wait-free synchronization, efficient spinlocks, % and other related topics. % This file is in the public domain. % Please send corrections, updates, etc. to valoisj@cs.rpi.edu @string{acmp = "ACM Press"} @string{addwes = "Addison-Wesley"} @string{bc = "Benjamin/Cummings"} @string{decsrc = "Digital Equipment Corporation Systems Research Center"} @string{ieeecsp = "IEEE Computer Society Press"} @string{berkeley = "University of California Berkeley"} @string{springer = "Springer-Verlag"} @string{deccrl = "DEC Cambridge Research Lab"} @string{kluwer = "Kluwer Academic Publishers"} @string{rpi = "Rensselaer Polytechnic Institute, Department of Computer Science"} @string{mghill = "McGraw-Hill"} @string{mit = "Massachusetts Institute of Technology"} @string{mitp = "The MIT Press"} @string{mitlcs = "MIT Laboratory for Computer Science"} @string{morgank = "Morgan Kaufman Publishers, Inc."} @string{cmu = "Carnegie-Mellon University"} @string{ufl = "University of Florida"} @string{columbia = "Columbia University"} @string{ibm = "International Business Machines Corp."} @string{ibmalmaden = "IBM Almaden Research Center"} @string{ibmwatson = "IBM T. J. Watson Research Center"} @string{rochester = "University of Rochester"} @string{technion = "Technion, Israel Institute of Technology, Department of Computer Science"} @string{washington = "University of Washington, Department of Computer Science and Engineering"} @string{nyu = "New York University, Department of Computer Science"} @string{lncs = "Lecture Notes on Computer Science"} @string{tr = "Technical Report"} @string{textmono = "Texts and Monographs in Computer Science"} @string{miteecs = "The {MIT} Electrical Engineering and Computer Science Series"} @string{actai = "Acta Informatica"} @string{cacm = "Communications of the {ACM}"} @string{cs = "Computing Surveys"} @string{dc = "Distributed Computing"} @string{ibmjrd = "{IBM} Journal Of Research And Development"} @string{ic = "Information and Computation"} @string{ieeecomp = "{IEEE} Computer"} @string{ieeepds = "{IEEE} Transactions on Parallel and Distributed Systems"} @string{ieeesoft = "{IEEE} Software"} @string{ieeetoc = "{IEEE} Transactions on Computers"} @string{ijpp = "International Journal of Parallel Programming"} @string{jacm = "Journal of the {ACM}"} @string{jalg = "Journal of Algorithms"} @string{jpdc = "Journal of Parallel and Distributed Computing"} @string{jsyssoft = "Journal of Systems Software"} @string{osrev = "Operating Systems Review"} @string{pc = "Parallel Computing"} @string{sci = "Science"} @string{siamjc = "{SIAM} Journal on Computing"} @string{tocs = "{ACM} Transactions on Computer Systems"} @string{tods = "{ACM} Transactions on Database Systems"} @string{toplas = "{ACM} Transactions on Programming Languages and Systems"} @string{proc = "Proceedings of the "} @string{proc1 = "Proceedings of "} @string{asplos = " International Conference on Architectural Support for Programming Languages and Operating Systems"} @string{dcs = " International Conference on Distributed Computing Systems"} @string{focs = " Symposium on Foundations of Computer Science"} @string{ftcs = " International Symposium on Fault-Tolerant Computing"} @string{icalp = " International Conference on Automata, Languages, and Programming"} @string{icpp = " International Conference on Parallel Processing"} @string{ieeert = " Real-Time Systems Symposium"} @string{ieeepdcs = " {IEEE} Symposium on Parallel and Distributed Processing"} @string{isca = " Annual International Symposium on Computer Architecture"} @string{podc = " Symposium on Principles of Distributed Computing"} @string{pods = " Symposium on Principles of Database Systems"} @string{popl = " Symposium on Principles of Programming Languages"} @string{ppopp = " {ACM} Symposium on Principles and Practice of Parallel Programming"} @string{sosp = " Symposium on Operating Systems Principles"} @string{spaa = " Symposium on Parallel Algorithms and Architectures"} @string{stoc = " {ACM} Symposium on Theory of Computing"} @string{super = " Supercomputing"} @string{tark = " Conference on Theoretical Aspects of Reasoning about Knowledge"} @string{wdag = " International Workshop on Distributed Algorithms"}, @string{asplos89 = proc # "Second" # asplos} @string{asplos91 = proc # "Fourth" # asplos} @string{asplos92 = proc # "Fifth" # asplos} @string{asplos94 = proc # "Sixth" # asplos} @string{icdcs88 = proc # "Eighth" # dcs} @string{icdcs89 = proc # "Ninth" # dcs} @string{icdcs93 = proc # "Thirteenth" # dcs} @string{icpp79 = proc # "1979" # icpp} @string{icpp80 = proc # "1980" # icpp} @string{icpp81 = proc # "1981" # icpp} @string{icpp84 = proc # "1984" # icpp} @string{icpp91 = proc # "1991" # icpp} @string{ieeepdcs91 = proc # "Third" # ieeepdcs} @string{isca84 = proc # "Eleventh" # isca} @string{isca85 = proc # "Twelfth" # isca} @string{isca89 = proc # "Sixteenth" # isca} @string{isca93 = proc # "Twentieth" # isca} @string{podc83 = proc # "Second" # podc} @string{podc84 = proc # "Third" # podc} @string{podc85 = proc # "Fourth" # podc} @string{podc86 = proc # "Fifth" # podc} @string{podc87 = proc # "Sixth" # podc} @string{podc88 = proc # "Seventh" # podc} @string{podc89 = proc # "Eighth" # podc} @string{podc90 = proc # "Ninth" # podc} @string{podc91 = proc # "Tenth" # podc} @string{podc92 = proc # "Eleventh" # podc} @string{podc93 = proc # "Twelfth" # podc} @string{podc94 = proc # "Thirteenth" # podc} @string{podc95 = proc # "Fourteenth" # podc} @string{pods88 = proc # "Seventh" # pods} @string{pods92 = proc # "Eleventh" # pods} @string{popl87 = proc # "Fourteenth" # popl} @string{popl94 = proc # "Twenty-First" # popl} @string{ppopp90 = proc # "Second" # ppopp} @string{ppopp93 = proc # "Fourth" # ppopp} @string{focs79 = proc # "Twentieth" # focs} @string{focs82 = proc # "Twenty-Third" # focs} @string{focs83 = proc # "Twenty-Fourth" # focs} @string{focs84 = proc # "Twenty-Fifth" # focs} @string{focs86 = proc # "Twenty-Seventh" # focs} @string{focs87 = proc # "Twenty-Eighth" # focs} @string{focs88 = proc # "Twenty-Ninth" # focs} @string{focs89 = proc # "Thirtieth" # focs} @string{focs90 = proc # "Thirty-First" # focs} @string{focs91 = proc # "Thirty-Second" # focs} @string{focs92 = proc # "Thirty-Third" # focs} @string{focs93 = proc # "Thirty-Fourth" # focs} @string{sosp72 = proc # "Third" # sosp} @string{sosp89 = proc # "Twenty-First" # sosp} @string{stoc85 = proc # "Seventeenth" # stoc} @string{stoc86 = proc # "Eighteenth" # stoc} @string{stoc88 = proc # "Twentieth" # stoc} @string{stoc89 = proc # "Twenty-First" # stoc} @string{stoc90 = proc # "Twenty-Second" # stoc} @string{stoc91 = proc # "Twenty-Third" # stoc} @string{stoc92 = proc # "Twenty-Fourth" # stoc} @string{stoc93 = proc # "Twenty-Fifth" # stoc} @string{stoc94 = proc # "Twenty-Sixth" # stoc} @string{stoc95 = proc # "Twenty-Seventh" # stoc} @string{super90 = proc1 # super # "'90"} @string{pods82 = proc # "First" # pods} @string{pods87 = proc # "Sixth" # pods} @string{pods92 = proc # "Eleventh" # pods} @string{wdag85 = proc # "First" # wdag} @string{wdag87 = proc # "Second" # wdag} @string{wdag89 = proc # "Third" # wdag} @string{wdag90 = proc # "Fourth" # wdag} @string{wdag91 = proc # "Fifth" # wdag} @string{wdag92 = proc # "Sixth" # wdag} @string{wdag93 = proc # "Seventh" # wdag} @string{wdag94 = proc # "Eighth" # wdag} @string{spaa90 = proc # "Second" # spaa} @string{spaa91 = proc # "Third" # spaa} @string{spaa92 = proc # "Fourth" # spaa} @string{spaa93 = proc # "Fifth" # spaa} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @inproceedings{AndWoll91, author = {R. J. Anderson and H. Woll}, title = {Wait-Free Parallel Algorithms For The Union-Find Problem}, booktitle= stoc91, pages = {370--380}, year = 1991, annote = { Implements concurrent, lock-free up-trees with path halving, using Compare-and-Swap. } } @BOOK{Andrews91, AUTHOR = {G. Andrews}, PUBLISHER = {Benjamin/Cummings}, TITLE = {Concurrent Programming --- Principles and Practice}, YEAR = {1991}, comments = {Brief mention of lock-free work by Herlihy.} } @INPROCEEDINGS{AsHe90a, AUTHOR = {J. Aspnes and M. Herlihy}, BOOKTITLE = {Proceedings of the 1990 Symposium on Parallel Algorithms and Architectures}, PAGES = {340--349}, TITLE = {Wait-Free Data Structures in the Asynchronous {PRAM} Model}, YEAR = {1990} } @article{Dinning89, author = {A. Dinning}, title = {A Survey of Synchronization Methods for Parallel Computers}, journal = ieeecomp, month = jul, pages = {66--77}, year = 1989, annote = { Overview of various architectures' synchronization methods. } } @article{GLR83, author = {A. Gottlieb and B. Lubachevsky and L. Rudolph}, title = {Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors}, year = 1983, journal = toplas, pages = {164--189}, month = apr, number = 2, volume = 5, annote = { Presents in-place lock-free (but not non-blocking) queues using the Fetch-and-Add operation of the NYU Ultracomputer. Also show how to do semaphores, reader/writer, termination detection, etc.\ using FAA, and discuss the hardware combining network that makes FAA efficient. } } @ARTICLE{GraTha90, AUTHOR = {G. Graunke and S. Thakkar}, JOURNAL = {Computer}, MONTH = {June}, PAGES = {60--69}, TITLE = {Synchronization Algorithms For Shared-Memory Multiprocessors}, VOLUME = {23}, YEAR = {1990} } @inproceedings{HeMo91, author = {M. Herlihy and J. Moss}, title = {Lock-Free Garbage Collection for Multiprocessors}, booktitle = spaa91, month = jul, pages = {229--236}, year = 1991, annote = { See IEEE Trans. Par. Dist. Sys. paper. } } @unpublished{HerMos92b, author = {M. Herlihy and J. Moss}, title = {Transactional Memory: {Architectural} Support for Highly Concurrent Data Structures}, month = {April}, note = {unpublished draft}, year = {1992} } @techreport{HerWing86, author = {M. P. Herlihy and J. M. Wing}, title = {Axioms for Concurrent Objects}, institution = cmu, number = {CMU--CS--86--154}, year = 1986, annote = { See their POPL 87 paper. } } @article{HerWing90, author = {M. P. Herlihy and J. M. Wing}, title = {Linearizability: {A} Correctness Condition for Concurrent Objects}, journal = toplas, volume = 12, number = 3, pages = {463--492}, year = 1990, annote = { Definition of linearizability, techniques for proving things about linearizable histories and how to verify that an implementation of a concurrent object is linearizable. } } @inproceedings{Herlihy90, author = {M. Herlihy}, title = {A methodology for implementing highly concurrent data structures}, booktitle = ppopp90, pages = {197--206}, year = 1990, annote = { Herlihy's second universal method, using Compare-and-Swap. Converts a sequential implementation into one that is wait-free. Also called the ``copying'' method. } } @article{Herlihy91, author = {M. Herlihy}, title = {Wait-Free Synchronization}, journal = toplas, month = jan, number = 1, pages = {124--149}, volume = 11, year = 1991, annote = { Seminal paper that establishes the consensus hierarchy, impossibility results for non-blocking and wait-free implementation of objects from other objects lower in the hierarchy, and the universality of consensus. Contains the original ``logging'' universal method. } } @INPROCEEDINGS{Herlihy91b, AUTHOR = {M. Herlihy}, BOOKTITLE = {Proceddings of the 1991 Symposium on Parallel Algorithms and Architectures}, PAGES = {327--336}, TITLE = {Impossibility Results for Asynchronous {PRAM}}, YEAR = {1991} } @ARTICLE{HilLar90, AUTHOR = {M. Hill and J. Larus}, JOURNAL = {Communications of the ACM}, MONTH = {August}, NUMBER = {8}, PAGES = {97--102}, TITLE = {Cache Considerations for Multiprocessor Programmers}, VOLUME = {33}, YEAR = {1990} } @inbook{HwBr85, author = {K. Hwang and F. Briggs}, pages = {559--562}, publisher = mghill, title = {Computer Architecture and Parallel Processing}, year = 1985, annote = { Example of the usual uses of the Compare-and-Swap instruction, mostly to manipulate shared queues without mutual exclusion. } } @article{Johnson94, author = {T. Johnson}, title = {A Highly Concurrent Priority Queue}, pages = {367}, year = 1994, journal = jpdc, volume = {22}, month = aug, annote = { Revised version of tech report 007--91. Mostly uses locks; presents one variation that allows limited concurrency using F\&A. } } @techreport{Johnson93, author = {T. Johnson}, title = {Characterizing the Performance of Algorithms for Lock-Free Objects}, institution = ufl, number = {93--021}, type = tr, year = 1993, annote = { Develops analytical models for the performance of lock-free data structures. Shows that lock-free is better when all processes are approximately the same speed, but can sometimes suffer slowdowns, and that it is worse when some processors are always slower than others (because slow processes are discriminated against). } } @ARTICLE{KunLeh80, AUTHOR = {H. Kung and Q. Lehman}, JOURNAL = {ACM Transactions on Database Systems}, MONTH = {Sept}, NUMBER = {3}, PAGES = {354--382}, TITLE = {Concurrent Manipulation of Binary Search Trees}, VOLUME = {5}, YEAR = {1980} } @techreport{MaPu91, author = {H. Massalin and C. Pu}, title = {A Lock-Free Multiprocessor {OS} Kernel}, institution = columbia, type = tr, number = {CUCS--005--91}, year = 1991, annote = { Describes Synthesis, a multiprocessor OS built entirely using lock-free data structures in the kernel. The algorithms often rely on the powerful two word Compare-and-Swap instruction found on the Motorola~68020. } } @ARTICLE{ManLad84, AUTHOR = {U. Manber and P. Ladner}, JOURNAL = {ACM Transactions on Database Systems}, MONTH = {Sept}, NUMBER = {3}, PAGES = {439--455}, TITLE = {Concurrent Control in a Dynamic Search Structure}, VOLUME = {9}, YEAR = {1984} } @ARTICLE{Manber84a, AUTHOR = {U. Manber}, JOURNAL = {IEEE Transactions on Software Engineering}, MONTH = {Nov}, NUMBER = {6}, PAGES = {777-784}, TITLE = {Concurrent Maintenance of Binary Search Trees}, VOLUME = {10}, YEAR = {1984} } @inproceedings{Manber84b, author = {U. Manber}, pages = {273--278}, title = {On Maintaining Dynamic Information in a Concurrent Environment}, year = 1984, booktitle = stoc84, annote = { Early idea of concurrent objects. } } @article{Manber86, author = {U. Manber}, title = {On Maintaining Dynamic Information in a Concurrent Environment}, pages = {1130--1142}, year = 1986, journal = siamjc, volume = {15}, number = {4}, annote = { Journal version of 84 STOC paper. } } @article{MelSco91a, author = {J. Mellor-Crummey and M. Scott}, title = {Algorithms For Scalable Synchronization On Shared-Memory Multiprocessors}, journal = tocs, month = feb, pages = {21--65}, volume = 9, number = 1, year = 1991, annote = { Queue locks. } } @INPROCEEDINGS{MelSco91b, AUTHOR = {J. Mellor-Crummey and M. Scott}, BOOKTITLE = {Proceedings of the 3rd {ACM SIGPLAN} Symposium on Principles and Practice of Parallel Programming}, PAGES = {106--113}, TITLE = {Scalable Reader-Writer Synchronization for Shared-Memory Multiprocessors}, YEAR = {1991} } @inproceedings{Plotkin89, author = {S. A. Plotkin}, title = {Sticky Bits and Universality of Consensus}, pages = {159--175}, booktitle = podc89, year = 1989, annote = { Shows how a ``sticky bit'' primitive can be used to solve consensus, and to construct a universal method similar to Herlihy's original logging method. } } @inproceedings{PrLeJo91, author = {S. Prakash and Y. Lee and T. Johnson}, booktitle = icpp91, pages = {68--75}, title = {A Non-Blocking Algorithm for Shared Queues Using {Compare-and-Swap}}, year = 1991, annote = { They extend the evolution of the lock-free queue, and make it non-blocking by categorizing the indeterminite states that the queue can be in. Also includes some performance evaluation using simulations. } } @techreport{PrLeJo91b, author = {S. Prakash and Y.-H. Lee and T. Johnson}, title = {Non-Blocking Algorithms for Concurrent Data Structures}, institution = ufl, type = tr, number = {91--002}, year = 1991, annote = { Universal method for converting lock-based concurrent data structures into non-blocking objects using Compare-and-Swap. Underlying lock-based implementation must be free of deadlock. } } @TECHREPORT{Pugh89a, AUTHOR = {W. Pugh}, INSTITUTION = {Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland, College Park}, NUMBER = {CS-TR-2222.1}, TITLE = {Concurrent Maintenance of Skip Lists}, YEAR = {1989} } @BOOK{Raynal86, AUTHOR = {M. Raynal}, PUBLISHER = {MIT Press}, TITLE = {Algorithms for Mutual Exclusion}, YEAR = {1986} } @book{Stone80, editor = {H. Stone}, title = {Introduction to Computer Architecture}, publisher = {Science Research Associates, Inc.}, year = 1980, annote = { Contains chapter by Sites, which includes information on the use of Compare-and-Swap. } } @INPROCEEDINGS{Stone90, AUTHOR = {J. M. Stone}, BOOKTITLE = {Proceedings of Supercomputing '90}, PAGES = {495--504}, TITLE = {A Simple and Correct Shared-Queue Algorithm Using {Compare-and-Swap}}, YEAR = {1990} } @inproceedings{Stone92, author = {J. M. Stone}, title = {A Non-Blocking {Compare-and-Swap} Algorithm for a Shared Circular Queue}, booktitle = {Parallel and Distributed Computing in Engineering Systems}, editor = {S. Tzafestas and others}, publisher = {Elsevier Science Publishers}, pages = {147--152}, year = {1992}, annote = { Uses the ideas of Prakash et al.'s queue to make Stones original lock-free queue non-blocking. } } @ARTICLE{WheEva91, AUTHOR = {M. Wheat and D. Evans}, JOURNAL = pc, PAGES = {101--107}, TITLE = {Maintenance of Shared Data Structures on Tightly Coupled Multiprocessors}, VOLUME = {17}, YEAR = {1991} } @INPROCEEDINGS{YeLeBa90, AUTHOR = {I. Yen and D. Leu and F. Bastani}, BOOKTITLE = {Proceedings 1990 Fontiers of Massively Parallel Computation}, PAGES = {51--54}, TITLE = {Hash Table and Sorted Array: {A} Case Study of Multi-Entry Data Structures in Massively Parallel Systems}, YEAR = {1990} } @ARTICLE{Lamport79, AUTHOR = {L. Lamport}, JOURNAL = {IEEE Transactions on Computers}, MONTH = {September}, NUMBER = {9}, PAGES = {690}, TITLE = {How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs}, VOLUME = {C--28}, YEAR = {1979} } @ARTICLE{Papadimitriou79, AUTHOR = {C. Papadimitriou}, JOURNAL = {Journal of the ACM}, MONTH = {October}, NUMBER = {4}, PAGES = {631--653}, TITLE = {The Serializability of Concurrent Database Updates}, VOLUME = {26}, YEAR = {1979} } @article{ShaGoo88, author = {D. Shasha and N. Goodman}, title = {Concurrent Search Structures Algorithms}, journal = tods, month = mar, volume = 13, number = 1, pages = {53--90}, year = 1988 } @techreport{Treiber86, author = {R. K. Treiber}, title = {Systems Programming: {Coping} With Parallelism}, year = 1986, institution = ibmalmaden, number = {RJ 5118}, month = apr, annote = { Techniques for manipulating various types of data structures, such as counters, FIFO/LIFO lists, etc. Some techniques use Compare-and-Swap and are lock-free. } } @manual{IBM83, title = {{System/370 Principles of Operation}}, year = 1983, organization = ibm } @manual{IBM90, title = {{Enterprise Systems Architecture/390 Principles of Operation}}, year = 1990, organization = ibm, annote = { Information on the canonical use of Compare-and-Swap to implement counters, shared queues, locks, etc. } } @article{AndersonT90, author = {T. Anderson}, title = {The Performance of Spin Lock Alternatives for Shared Memory Multiprocessors}, journal = ieeepds, month = jan, number = 1, pages = {6--16}, volume = 1, year = 1990 } @techreport{Mellor-Crummey87, author = {J. M. Mellor-Crummey}, title = {Concurrent Queues: {Practical} {Fetch-and-$\Phi$} Algorithms}, institution = rochester, month = nov, number = 229, type = tr, year = 1987, annote = { Lock-free algorithms for concurrent queues using fetch-and-phi type operations. These algorithms are lock-free but cannot tolerate processes that halt, and are thus not non-blocking. } } @techreport{AndersonT89, author = {T. Anderson}, title = {The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors}, institution = washington, month = aug, number = {89--04--03}, type = tr, year = 1989, annote = { Shows naive spin locks can degrade overall performance. Suggests a "queue" lock, shows that this is better. Also suggests the use of Ethernet style backoff. } } @inproceedings{GoGrKrMcRuSn82, author = {A. Gottlieb and others}, title = {The {NYU Ultracomputer} --- {Designing} a {MIMD} Shared Memory Parallel Machine}, booktitle = isca82, year = 1982 } @ARTICLE{FoJiShWe90, AUTHOR = {R. Ford and M. Jipping and R. Shultz and B. Wenhardt}, JOURNAL = {Journal of Parallel and Distributed Computing}, PAGES = {253--266}, TITLE = {On the Performance of Concurrent Tree Algorithms}, VOLUME = {8}, YEAR = {1990} } @ARTICLE{RyuTho90, AUTHOR = {I. Ryu and A. Thomasian}, JOURNAL = {IEEE Transactions on Software Engineering}, MONTH = {July}, NUMBER = {7}, PAGES = {684--698}, TITLE = {Performance Analysis of Dynamic Locking with the No-Waiting Policy}, VOLUME = {16}, YEAR = {1990} } @techreport{AndersonT91, author = {T. Anderson}, title = {Operating System Support for High Performance Multiprocessing}, number = {91--08--10}, institution = washington, month = aug, type = tr, year = 1991 } @phdthesis{AndersonT91b, author = {T. Anderson}, title = {Operating System Support for High Performance Multiprocessing}, school = washington, address = {Seattle, WA}, year = 1991, note = {University of Washington Department of Computer Science and Engineering Technical Report 91--08--10}, annote = { Demonstrates the importance of efficient synchronization in a multiprocessor system. Shows that naive spin-locks are not efficient. Introduces the ideas of software queueing and Ethernet style backoff to manage lock contention. } } @article{KunRob81, author = {H. Kung and J. Robinson}, title = {On Optimistic Methods of Concurrency Control}, journal = tods, number = 2, pages = {213--226}, volume = 6, year = 1981 } @inproceedings{HsiWei92, author = {W. Hsieh and W. Weihl}, title = {Scalable Reader-Writer Locks For Parallel Systems}, booktitle = {Proceedings of the 1992 International Parallel Processing Symposium}, month = mar, year = 1992 } @inproceedings{CBDW91, author = {A. Colbrook and E. Brewer and C. Dellarocas and W. Weihl}, title = {An Algorithm For Concurrent Search Trees}, booktitle = icpp91, pages = {III138--III141}, year = 1991 } @incollection{Sites80, author = {R. Sites}, booktitle = {Introduction to Computer Architecture}, chapter = 12, edition = {2nd}, editor = {H. Stone}, publisher = {Science Research Associates}, title = {Operating Systems and Computer Architecture}, year = 1980, annote = { Another example of early, canonical use of Compare-and-Swap for manipulating a shared queue. } } @inproceedings{HerWing87, author = {M. P. Herlihy and J. M. Wing}, title = {Axioms for Concurrent Objects}, booktitle = popl87, pages = {13--26}, year = 1987, annote = { See their TOPLAS (1990) paper. } } @phdthesis{Valois95a, author = {J. D. Valois}, title = {Lock-Free Data Structures}, year = 1995, school = rpi } @article{TurSha92, author = {J. Turek and D. Shasha}, journal = ieeecomp, month = {June}, pages = {8--17}, title = {The Many Faces of Consensus in Distributed Systems}, year = 1992 } @phdthesis{Turek91, author = {J. Turek}, school = nyu, title = {Resilient Computation in the Presence of Slowdowns}, year = 1991, annote = { Among other things, presents a universal method for converting a lock-based implementation into one that is non-blocking using Compare-and-Swap. } } @techreport{WiGo90, author = {J. M. Wing and C. Gong}, title = {A Library of Concurrent Objects and Their Proofs of Correctness}, institution = cmu, number = {CMU--CS--90--151}, type = tr, year = 1990, annote = { Implementation and proof of several data structures for queue and set concurrent objects (some of which are lock-free). They use Larch for their specifications. } } @inproceedings{JaChTo92, author = {P. Jayanti and T. D. Chandra and S. Toueg}, title = {Fault-Tolerant Wait-Free Shared Objects}, booktitle = focs92, pages = {157--166}, year = 1992, annote = { Formal analysis of fault-tolerance of concurrent systems of objects, in which objects may fail in either responsive or non-responsive ways. } } @inproceedings{TuShPr92, author = {J. Turek and D. Shasha and S. Prakash}, title = {Locking Without Blocking: {Making} Lock Based Concurrent Data Strucuture Algorithms Nonblocking}, booktitle = pods92, year = 1992, annote = { Combination of the work by Prakash {\em et al.\/} and Turek's Phd thesis, shows how to construct a universal method for lock-free data structures based on a technique using locks. Universal primitive is Compare-and-Swap. } } @inproceedings{AtLySh90, author = {H. Attiya and N. Lynch and N. Shavit}, title = {Are Wait-Free Algorithms Fast?}, booktitle = focs90, pages = {55--64}, year = 1990, annote = { Gives lower bounds on the time to solve approximate agreement in wait-free case that are worse than using mutual exclusion. } } @INPROCEEDINGS{HeShWa91, AUTHOR = {M. Herlihy and N. Shavit and O. Waarts}, BOOKTITLE = {Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science}, PAGES = {526--535}, TITLE = {Low Contention Linearizable Counting}, YEAR = {1991}, annote = { Extend counting networks of Aspnes, Herlihy, and Shavit to be linearizable. } } @INPROCEEDINGS{AsWa92, AUTHOR = {J. Aspnes and O. Waarts}, BOOKTITLE = {Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science}, PAGES = {137--146}, TITLE = {Randomized Consensus in Expected $O(n \log^2 n)$ Operations Per Processor}, YEAR = {1992} } @INPROCEEDINGS{Ayani90, AUTHOR = {R. Ayani}, BOOKTITLE = {Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Computing}, PAGES = {22--25}, TITLE = {LR-algorithm: {Concurrent} Operations on Priority Queues}, YEAR = {1990} } @inproceedings{EdGoKrMcRuSnTeWi85, author = {J. Edler and others}, title = {Issues Related to {MIMD} Shared-memory Computers: {The} {NYU Ultracomputer} Approach}, booktitle = isca85, pages = {126--135}, year = 1985 } @article{AsHe90, author = {J. Aspnes and M. P. Herlihy}, title = {Fast Randomized Consensus Using Shared Memory}, journal = jalg, pages = {441--461}, volume = {11}, year = {1990}, annote = { Solving consensus with only read and write primitives using randomizatoin. } } @ARTICLE{Lamport77, AUTHOR = {L. Lamport}, JOURNAL = {Communications of the ACM}, NUMBER = {11}, PAGES = {806--811}, TITLE = {Concurrent Reading and Writing}, VOLUME = {20}, YEAR = {1977} } @ARTICLE{Denning91, AUTHOR = {P. J. Denning}, JOURNAL = {American Scientist}, PAGES = {111--114}, TITLE = {Mutual Exclusion}, VOLUME = {79}, YEAR = {1991} } @ARTICLE{Peterson81, AUTHOR = {G. Peterson}, JOURNAL = {Information Processing Letters}, NUMBER = {3}, PAGES = {115--116}, TITLE = {Myths About the Mutual Exclusion Problem}, VOLUME = {12}, YEAR = {1981} } @article{Lamport74, author = {L. Lamport}, title = {A New Solution of {Dijkstra's} Concurrent Programming Problem}, pages = {453--455}, year = 1974, journal = cacm, volume = {17}, number = {8}, annote = { How to solve mutex problem wihtout assuming it; Bakery algorithm. } } @article{Lamport85, author = {L. Lamport}, title = {The Mutual Exclusion Problem --- {Parts} {I} and {II}}, pages = {313--348}, year = 1985, journal = jacm, volume = {33}, number = {2} } @TECHREPORT{LyTu88, AUTHOR = {N. Lynch and M. Tuttle}, INSTITUTION = {MIT Laboratory for Computer Science}, NUMBER = {MIT/LCS/TM--373}, TITLE = {An Introduction to Input/Output Automata}, TYPE = {Technical Report}, YEAR = {1988} } @article{Sites93, author = {R. Sites}, title = {Alpha {AXP} Architecture}, journal = cacm, month = feb, volume = 36, number = 2, pages = {33--44}, year = 1993 } @BOOK{KaHe92, AUTHOR = {G. Kane and J. Heinrich}, ADDRESS = {Englewood Cliffs, New Jersey}, PUBLISHER = {Prentice-Hall}, TITLE = {{MIPS RISC} Architecture}, YEAR = {1992} } @ARTICLE{Herlhy89, AUTHOR = {M. Herlihy}, JOURNAL = {SIGPLAN Notices}, MONTH = {April}, NUMBER = {4}, PAGES = {32--33}, TITLE = {Taking Concurrency Seriously}, VOLUME = {24}, YEAR = {1989} } @techreport{Herlihy91c, author = {M. Herlihy}, title = {A Methodology for Implementing Highly Concurrent Data Objects}, institution = deccrl, number = {CRL 91/10}, type = tr, year = 1991 } @techreport{HerMos92, author = {M. Herlihy and J. Moss}, title = {Transactional Memory: {A}rchitectural Support for Lock-Free Data Structures}, number = {CRL 92/07}, type = tr, year = 1992, institution = deccrl } @inproceedings{Barnes93, author = {G. Barnes}, title = {A Method for Implementing Lock-Free Shared Data Structures}, pages = {261--270}, booktitle = spaa93, year = 1993, annote = { Universal method for converting a lock-based implementation into a wait-free one, using the Load-Linked/Store-Conditional pair of primitives. This uses the ``caching method'' in order to avoid the problem with deadlocks that the method of Turek {\em et al.\/} has. } } @TECHREPORT{AleFel92b, AUTHOR = {J. Alemany and E. Felten}, INSTITUTION = {University of Washington}, NUMBER = {92--02--01}, TITLE = {Performance Issues in Non-Blocking Synchronization on Shared-Memory Multiprocessors}, TYPE = {Tech report}, YEAR = {1992} } @ARTICLE{MerTau93, AUTHOR = {M. Merritt and G. Taubenfeld}, JOURNAL = {Information Processing Letters}, PAGES = {137--142}, TITLE = {Speeding Lamport's Fast Mutual Exclusion Algorithm}, VOLUME = {45}, YEAR = {1993} } @INPROCEEDINGS{AsHeSh91, AUTHOR = {J. Aspnes and M. Herlihy and N. Shavit}, BOOKTITLE = {Proceedings of the 23rd Annual ACM Symposium on Theory of Commputing}, PAGES = {348--358}, TITLE = {Counting Networks and Multi-Processor Coordination}, YEAR = {1991}, annote = { Introduces counting networks, a low-contention shared counting data structure. } } @BOOK{ManPnu92, AUTHOR = {Z. Manna and A. Pnueli}, PUBLISHER = {Springer-Verlag}, TITLE = {The Temporal Logic of Reactive and Concurrent Systems}, YEAR = {1992} } @inproceedings{DwHeWa93, author = {C. Dwork and M. Herlihy and O. Waarts}, title = {Contention in Shared Memory Algorithms}, booktitle = stoc93, year = 1993, pages = {174--183}, annote = { Introduces a formal model for measuring the contention of algorithms in shared memory. Gives bounds for the contention of problems such as consensus, counters, and one-shot mutual exclusion. } } @techreport{DwHeWa93b, author = {C. Dwork and M. Herlihy and O. Waarts}, title = {Contention in Shared Memory Algorithms}, year = 1993, number = {CRL 93/12}, institution = deccrl, type = tr, month = aug, annote = { Expanded version of the STOC paper. } } @inproceedings{IsRa93, author = {A. Israeli and L. Rappoport}, title = {Efficient Wait-Free Implementation of a Concurrent Priority Queue}, booktitle = wdag93, year = 1993, pages = {1--16}, annote = { Wait-free implementation of a priority queue using a heap data structure. The implementation is ``effectively parallel'' and uses a two word Load-Linked/Store-Conditional primitive. } } @inproceedings{Bershad93, author = {B. N. Bershad}, title = {Practical Considerations for Non-Blocking Concurrent Objects}, booktitle = icdcs93, year = 1993, annote = { Shows how to use OS support to provide syncrhonization primitives. } } @phdthesis{RJohnson93, author = {R. Johnson}, title = {Extending the {Scalable Coherent Interface} for Large-Scale Shared-Memory Multiprocessors}, school = {University of Wisconsin-Madison}, year = 1993, anote = { Discussion of how to implement the cache for SCI. Appendix discusses Swap-if-Zero synchronization primitive, which is both universal and combinable. } } @article{HumSch91, author = {S. Hummel and E. Schonberg}, title = {Low-Overhead Scheduling Of Nested Parallelism}, journal = {{IBM} Journal Of Research And Development}, volume = 35, pages = {743--765}, month = {Sep}, year = 1991, annote = { Description of run-time system for scheduling nested parallel constructs (which run to completion without blocking). Makes use of lock-free shared queue. } } @article{Herlihy93, author = {M. Herlihy}, title = {A Methodology For Implementing Highly Concurrent Data Objects}, journal = toplas, volume = 15, pages = {745--770}, month = nov, year = 1993, annote = { Gives a universal method for wait-free concurrent objects using the Load-Linked/Store-Conditional pair. Update of original paper which used Compare-and-Swap. } } @article{PrLeJo94, author = {S. Prakash and Y. Lee and T. Johnson}, title = {A Nonblocking Algorithm For Shared Queues Using Compare-And-Swap}, journal = ieeetoc, volume = 43, pages = {548--559}, month = may, year = 1994, annote = { Journal version of their 1991 conference paper. Adds some performance analysis. } } @techreport{Lamport88, author = {L. Lamport}, title = {Concurrent Reading and Writing of Clocks}, institution = {DEC SRC}, year = 1988, number = 27 } @article{ChWe94, author = {S. Chaudhuri and J. Welch}, title = {Bounds On The Costs Of Multivalued Register Implementations}, journal = {Siam Journal On Computing}, volume = 23, pages = {335--354}, year = 1994 } @article{Lamport87, author = {L. Lamport}, title = {A Fast Mutual Exclusion Algorithm}, journal = {tocs}, volume = 5, number = 1, pages = {1--11}, year = 1987 } @inproceedings{SeRu84, author = {Z. Segall and L. Rudolph}, title = {Dynamic Decentralized Cache Schemes for an {MIMD} Parallel Processor}, booktitle = isca84, pages = {340--347}, year = 1984, annote = { Introduced test and test-and-set locks. } } @article{Dijkstra65, author = {E. Dijkstra}, title = {Solution of a Problem in Concurrent Programming Control}, journal = cacm, pages = 569, volume = 8, number = 9, year = 1965, annote = { Introduces the problem of mutual exclusion; Dekker's algorithm. } } @techreport{JensenHB87, author = {E. H. Jensen and G. W Hagensen and J. M. Broughton}, title = {A New Approach to Exclusive Data Access in Shared Memory Multiprocessors}, institution = {Lawrence Livermore Laboratory}, year = 1987, type = tr, number = {212--157}, annote = { Propose the prototypical transactional synchronization primitive. }, kw = {have,read} } @inproceedings{IsR94, author = {A. Israeli and L. Rappoport}, title = {Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives}, booktitle = podc94, year = 1994, pages = {151--160} } @article{WingGong93, author = {J. M. Wing and C. Gong}, title = {Testing and Verifying Concurrent Objects}, journal = jpdc, volume = 17, pages = {164--182}, year = 1993, annote = { Proposes checking correctness through both verification and testing. Describe a simulator that attempts to find non-linearizable histories for implementations of concurrent objects. Includes formal verification of several queue type data structures (array based). } } @inproceedings{StVrSe89, author = {Per Stenstr\"{o}m and Dalibor Vrsalovic and Zary Segall}, title = {Shared Data Structures in a Distributed System --- Performance Evaluation and Practical Considerations}, booktitle = {Performance of Distributed and Parallel Systems}, year = 1989, pages = {15--30}, editor = {T. Hasegawa and H. Takagi and Y. Takahashi}, organization = {IFIP}, publisher = {Elsevier Science Publishers}, annote = { Experiences in providing shared memory abstraction on Unix workstations over Ethernet. } } @article{HerMoss92, author = {M. P. Herlihy and J. E. B. Moss}, title = {Lock-Free Garbage Collection for Multiprocessors}, pages = {304--311}, year = 1992, journal = ieeepds, volume = 3, annote = { Lock-free garbage collection, creates new "versions" much like Herlihy's universal copying method. } } @article{GiffSpec87, author = {D. Gifford and A. Spector}, title = {Case Study: {IBM's System} 360-370 Architecture}, journal = cacm, volume = 30, number = 4, pages = {291--307}, year = 1987, annote = { Describes how Compare-and-Swap was added to architecture in order to allow queue manipulation without critical section. } } @techreport{MichScott94, author = {M. M. Michael and M. L. Scott}, title = {Scalability of Atomic Primitives on Distributed Shared Memory Multiprocessors}, institution = rochester, year = 1994, type = tr, number = {}, annote = { Discussion of implementing C\&S, F\&A, LL/SC, and other types of atomic primitives on a distributed shared memory multiprocessor. } } @inproceedings{MiSco95, author = {M. M. Michael and M. L. Scott}, title = {Implementation of General-Purpose Atomic Primitives for Distributed Shared-Memory Multiprocessors}, year = 1995, booktitle = {First International Symposium on High Performance Computer Architecture}, month = jan, note = {Also Univ.\ of Rochester Computer Science Dept.\ TR~528} } @article{CasePadegs78, author = {R. P. Case and A. Padegs}, title = {Architecture of the {IBM System 370}}, pages = {73--96}, year = 1978, journal = cacm, volume = {21}, month = jan, annote = { Discussion of the System 370 architecture. Brief mention of Compare\&Swap instruction, and its purpose for implementing queues without mutex. } } @article{AndSch83, author = {G. R. Andrews and F. B. Schneider}, title = {Concepts and Notations for Concurrent Programming}, pages = {3--43}, year = 1983, journal = cs, volume = {15}, number = {1}, month = mar, annote = { Good (though dated) discussion of synchronization methods. } } @phdthesis{Hummel88, author = {S. Hummel}, title = {{SMARTS} --- {Shared} Memory Multiprocessor {Ada} Runtime Supervisor}, year = 1988, school = nyu, annote = { Study of runtime support for Ada, using the Fetch\&Add techniques of the Ultracomputer project. } } @phdthesis{Rudolph82, author = {L. Rudolph}, title = {Software Structures for Ultra Parallel Computing}, year = 1982, school = nyu, annote = { Includes material found in "Basic Techniques" paper. Manipulates linked list queues as an array of serialized linked lists using the Fetch-and-Phi operations. } } @phdthesis{Wilson88, author = {J. Wilson}, title = {Operating System Data Structures for Shared-Memory Machines with Fetch-and-Add}, year = 1988, school = nyu, annote = { Study of data structures (queues, multiqueues, memory management) needed for an operating system kernel, using the Fetch-and-Add techniques of the Ultracomputerb project. Also high level operating system and programming language constructs, such as semaphores and parallel loops. Also looks at memory management, including first-fit, good-fit, and binary budy system algorithms using the data structures. } } @inproceedings{KotzEllis89, author = {D. Kotz and C. Ellis}, title = {Evaluation of Concurrent Pools}, pages = {378--385}, year = 1989, booktitle = icdcs89 } @inproceedings{LimAgar94, author = {B. Lim and A. Agarwal}, title = {Reactive Synchronization Algorithms for Multiprocessors}, pages = {25--35}, year = 1994, booktitle = asplos94, annote = { Proposes new spin lock and fetch-and-op algorithms that dynamically choose between various locking algorithms (such as test-and-set and queue locks) to select the best choice based on the current contention. } } @article{MetBog76, author = {R. M. Metcalfe and D. R. Boggs}, title = {Ethernet: {Distributed} Packet Switching for Local Computer Networks}, pages = {395--404}, year = 1976, journal = cacm, volume = {19}, number = {7}, annote = { This is the original reference for exponential backoff. } } @article{Stone84, author = {H. S. Stone}, title = {Database Applications of the {Fetch-And-Add} Instruction}, pages = {604--612}, year = 1984, journal = ieeetoc, volume = {33}, number = {7}, annote = { Use of F\&A to implement locks and timestamps for database applications. } } @book{Dally87, author = {W. J. Dally}, title = {A {VLSI} Architecture for Concurrent Data Structures}, year = 1987, publisher = kluwer, annote = { Version of author's PhD thesis. Uses locks, Smalltalk, big OO orientation. Presents a "balanced cube" data structure for ordered sets. } } @article{Scratchley93, author = {W. C. Scratchley}, title = {Using {Smalltalk} for Wait-Free Implementations of Highly-Concurrent Objects}, pages = {44--53}, year = 1993, journal = {{OOPS} Messenger}, volume = 4, number = 4, month = oct, annote = { Implementation of Herlihy's universal ``logging'' method in Smalltalk. } } @inproceedings{LanSha88, author = {V. Lanin and D. Shasha}, title = {Concurrent Set Manipulation Without Locking}, pages = {211--220}, year = 1988, booktitle = pods88 } @article{Gustavson92, author = {D. B. Gustavson}, title = {The {Scalable Coherent Interface} and Related Standards Projects}, pages = {10--22}, year = 1922, journal = {{IEEE} Micro}, month = feb, annote = { Overview of SCI. Mention of usefulness of synchronization primitives like CSW and FAA, how they can be used to manipulate linked lists, and the fact that SCI provides them. } } @article{AtCo92, author = {M. S. Atkins and M. Y. Coady}, title = {Dynamic Concurrency Control for Shared Data Structures}, pages = {190--225}, year = 1992, journal = tocs, month = aug, annote = { Comparison of optimistic and pessimistic concurrency control using concurrent object servers. } } @article{MoTaYa92, author = {S. Moran and G. Taubenfeld and I. Yadin}, title = {Concurrent Counting}, pages = {59--70}, year = 1992, booktitle = podc92, annote = { Algorithms for wait-free counter objects. } } @inproceedings{IsSh92, author = {A. Israeli and A. Shaham}, title = {Optimal Multi-Writer Multi-Reader Atomic Register}, pages = {71--82}, year = 1992, booktitle = podc92, annote = { Optimal algorithms (linear time, logrithmic space) for atomic registers. } } @inproceedings{AleFel92, author = {J. Alemany and E. W. Felten}, title = {Performance Issues in Non-Blocking Synchronization on Shared-Memory Multiprocessors}, pages = {125--134}, year = 1992, booktitle = podc92, annote = { Uses OS support to support lock-free data structures. We are only concerned with long delays (e.g., page faults), of which the OS is aware; and hence the OS can take appropriate action when a process suffers from a long delay. Techniques do things such as limit the amount of concurrency (SOLO protocol) and OS restore of consistent state of object if process updating with exclusive access is delayed. } } @inproceedings{MaPu89, author = {H. Massalin and C. Pu}, title = {Threads and Input/Output in the {Synthesis} Kernel}, pages = {191--200}, year = 1989, booktitle = sosp89, month = dec, annote = { Gives algorithms for lock-free queues using Compare-and-Swap. } } @inproceedings{LaMarca94, author = {A. La{Marca}}, title = {A Performance Evaluation of Lock-Free Synchronization Protocols}, pages = {130--140}, year = 1994, booktitle = podc94, annote = { Study the performance of various universal methods, and develop a simple analytic performance model. Develop a new protocol (SOLO-cooperative) which combines the ideas of Barnes with Alemany and Felten. } } @inproceedings{TGH92, author = {J. Torellas and A. Gupta and J. Hennessy}, title = {Characterizing the Caching and Synchronization Performance of a Multiprocessor Operating System}, pages = {162--174}, year = 1992, booktitle = asplos92, annote = { Show that OS kernel data structures rarely suffer contention. } } @inproceedings{Valois94, author = {J. D. Valois}, title = {Implementing Lock-Free Queues}, pages = {64--69}, year = 1994, booktitle = {Proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems}, address = {Las Vegas, NV}, month = oct, note = {Available as RPI Dept. of Comp. Sci. Tech. Report \#94--17.} } @inproceedings{Valois95b, author = {J. D. Valois}, title = {Lock-Free Linked Lists Using Compare-and-Swap}, pages = {214--222}, year = 1995, booktitle = podc95 } @article{FLP85, author = {M. J. Fischer and N. A. Lynch and M. S. Paterson}, title = {Impossibility of Distributed Consensus with One Faulty Process}, pages = {374--382}, year = 1985, journal = jacm, annote = { Classic result that consensus cannot be solved in an asynchronous model if even one process is faulty. } } @book{Sites92, title = {Alpha Architecture Reference Manual}, year = 1992, editor = {R. L. Sites}, publisher = {Digital Press}, address = {Burlington, MA}, annote = { Description of the Alpha architecture. Includes caveats about using the LL/SC instruction pair. } } @inproceedings{Herlihy88, author = {M. P. Herlihy}, title = {Impossibility and Universality Results for Wait-Free Synchronization}, pages = {276--290}, year = 1988, booktitle = podc88, annote = { Seminal paper that shows consensus is universal. } } @article{PfiNor85, author = {G. F. Pfister and V. A. Norton}, title = {`Hotspot' Contention and Combining in Multistage Interconnection Networks}, pages = {}, year = 1985, journal = ieeetoc, volume = {C-34}, number = {10}, month = oct, annote = { Hotspot contention. } } @techreport{Gottlieb86, author = {A. Gottlieb}, title = {An Overview of the {NYU Ultracomputer} Project}, year = 1986, number = {100}, institution = nyu, type = {Ultracomputer Note}, month = oct } @incollection{Gottlieb87, author = {A. Gottlieb}, title = {An Overview of the {NYU Ultracomputer} Project}, pages = {25--95}, year = 1987, editor = {J. J. Dongarra}, booktitle = {Experimental Parallel Computing Architectures}, publisher = {North-Holland} } @article{SiAnGo94, author = {A. K. Singh and J. H. Anderson and M. G. Gouda}, title = {The Elusive Atomic Register}, pages = {311--339}, year = 1994, journal = jacm, volume = {41} } @article{HalVid92, author = {S. Haldar and K. Vidyasankar}, title = {Counterexamples to a One Writer Multireader Atomic Variable Construction of Burns and Peterson}, pages = {78--87}, year = 1992, journal = osrev, volume = {26}, number = {1}, month = jan } @techreport{LampSch89, author = {L. Lamport and F. B. Schneider}, title = {Pretending Atomicity}, year = 1989, number = {44}, institution = decsrc, type = {Research Report}, month = may, annote = { Formal justification for reducing sequences of atomic atomic actions that contain only one shared memory reference into a single atomic step. } } @article{Lamport90, author = {L. Lamport}, title = {A Theorem on Atomicity in Distributed Algorithms}, pages = {59--68}, year = 1990, journal = dc, volume = {4}, annote = { Gives conditions for applying and formally justifies a folk theorem for combining seuqneces of steps into a single atomic action in distributed systems. } } @inproceedings{BeReEl92, author = {B. N. Bershad and D. D. Redell and J. R. Ellis}, title = {Fast Mutual Exclusion for Uniprocessors}, pages = {223--233}, year = 1992, booktitle = asplos92, annote = { Use of restartable atomic sequences on uniprocessors for optimistic synchronization. } } @inproceedings{HuWe91, author = {Q. Huang and W. E. Weihl}, title = {An Evaluation of Concurrent Priority Queue Algorithms}, pages = {518--525}, year = 1991, booktitle = ieeepdcs91, annote = { Evaluation of different implementations of concurrent objects. } } @inproceedings{Crowl88, author = {L. A. Crowl}, title = {Concurrent Data Structures and Actor Programming Under the Matroshka Model}, pages = {79--80}, year = 1988, booktitle = {Proceedings of the ACM SIGPLAN Workshop on Object Oriented Based Concurrent Programming}, address = {San Diego}, month = sep, annote = { Shows how Herlihy's original universal construction can be implemented in the Actor model. } } @inproceedings{Easton72, author = {W. B. Easton}, title = {Process Synchronization Without Long-Term Interlock}, pages = {95--100}, year = 1972, booktitle = sosp72, annote = { An early paper than noted many of the problems mutual exclusion could have and anticipated many of the ideas of lock-free synchronization. } } @article{Collier73, author = {W. W. Collier}, title = {Asynchronous Interactions on Shared Data}, pages = {6--15}, year = 1973, journal = osrev, volume = {7}, number = {2}, annote = { Looks at types of operations and how they can interact in an asynchronous computation. } } @inproceedings{ZaLa89, author = {J. Zahorjan and E. D. Lazowska}, title = {Spinning Versus Blocking in Parallel Systems with Uncertainty}, pages = {455--472}, year = 1989, editor = {T. Hasegawa and H. Takagi and Y. Takahashi}, booktitle = {Performance of Distributed and Parallel Systems}, publisher = {Elsevier Science Publishers} } @inproceedings{Irani79, author = {K. B. Irani}, title = {Modelling of Conflicts, Priority Hierarchies and Reentrancy in Concurrent Synchronization Structures}, pages = {196--204}, year = 1979, booktitle = icpp79 } @techreport{Johnson93b, author = {T. Johnson}, title = {Interruptible Critical Sections for Real-Time Systems}, year = 1993, number = {93--017}, institution = ufl, type = tr } @techreport{JoHa94b, author = {T. Johnson and K. Harathi}, title = {Interruptible Critical Sections}, year = 1994, number = {94--007}, institution = ufl, type = tr } @incollection{KrLiAgYe94, author = {D. Kranz and others}, title = {Low-Cost Support for Fine-Grain Synchronization in Multiprocessors}, pages = {139--166}, year = 1994, editor = {R. A. Iannucci}, booktitle = {Multithreaded Computer Architecture}, chapter = {7}, publisher = kluwer, annote = { Describes support for fine-grain synchronization provided by the Alewife system, consisting of full/empty bits for every word. Recommends hardware support for fine-grain synchronization is a win. } } @incollection{AlAlCaKoPoSm94, author = {G. Alverson and others}, title = {Integrated Support for Heterogenous Parallelism}, pages = {253--283}, year = 1994, editor = {R. A. Iannucci}, booktitle = {Multithreaded Computer Architecture}, chapter = {11}, publisher = kluwer, annote = { Describes the components of the Tera approach. Supports a wide spectrum of parallelism, from course to fine grain. } } @incollection{EkGrHiIaRa94, author = {K. Ekanadham and others}, title = {An Architecture for Generalized Synchronization and Fast Switching}, pages = {285--316}, year = 1994, editor = {R. A. Iannucci}, booktitle = {Multithreaded Computer Architecture}, chapter = {12}, publisher = kluwer, annote = { More stuff on full/empty bits. } } @phdthesis{Danzig89, author = {P. B. Danzig}, title = {Optimally Selecting the Parameters of Adaptive Backoff Algorithms for Computer Networks and Multiprocessors}, year = 1989, school = berkeley, annote = { Studies exponential backoff in spin locks, plus two other network problems. Advocates setting a minimum backoff interval rather that a maximum one. } } @inproceedings{BeGo80, author = {P. A. Bernstein and N. Goodman}, title = {Timestamp-Based Algorithms for Concurrency Control in Distributed Database Systems}, pages = {285--300}, year = 1980, booktitle = {Proceedings of the International Conference on Very Large Databases}, annote = { Reference to timestamp-based, optimistic concurrency control in databases, which is very similar to lock-free algorithms. } } @inproceedings{ZhYe85, author = {C.-Q. Zhu and P.-C. Yew}, title = {A Synchronization Scheme and its Applications for Large Multiprocessor Systems}, pages = {486--493}, year = 1985, booktitle = dcs, annote = { Synchronization primtive similar to Compare-and-Swap and Fetch-and-Phi. } } @phdthesis{Massalin92, author = {H. Massalin}, title = {Synthesis: {An} Efficient Implementation of Fundamental Operating System Services}, year = 1992, school = columbia, annote = { Discusses the design of the Synthesis operating system kernel. Among other things, it uses lock-free synchronization. } } @book{Stone93, author = {H. S. Stone}, title = {High-Performance Computer Architecture}, year = 1993, edition = {3rd}, series = {Addison-Wesley Series in Electrical and Computer Engineering}, publisher = addwes, annote = { Overview of high-performance computer architecture. Contains information on combining networks and Fetch-and-Add, and overview of synchronization using various primitives, including lock-free queues using Compare-and-Swap. } } @inproceedings{SoSmGo89, author = {G. S. Sohi and J. E. Smith and J. R. Goodman}, title = {Restricted {Fetch\&$\Phi$} Operations for Parallel Processing}, pages = {410--416}, year = 1989, booktitle = {Proceedings of the Third International Conference on Supercomputing}, month = jun, annote = { Hardware implementation of Fetch-and-Increment/Decrement. } } @book{BHG87, author = {P. Bernstein and V. Hadzilacos and N. Goodman}, title = {Concurrency Control and Recovery in Database Systems}, year = 1987, publisher = addwes, annote = { Reference for timestamp protocols. } } @inproceedings{FreGot91, author = {E. Freudenthal and A. Gottlieb}, title = {Process Coordination with Fetch-and-Increment}, pages = {260--268}, year = 1991, booktitle = asplos91, annote = { Critical section-free solutions, using Fetch-and-Inc/Dec, to barrier, queue with multiplicity, reader/writer problems. } } @inproceedings{MelSco91, author = {J. M. Mellor-Crummey and M. L. Scott}, title = {Synchronization Without Contention}, pages = {269--278}, year = 1991, booktitle = asplos91, annote = { Contention-free mutual exclusion, reader/writer, barriers. Queue locks. } } @inproceedings{AADGMS90, author = {Y. Afek and others}, title = {Atomic Snapshots of Shared Memory}, pages = {1--13}, year = 1990, booktitle = podc90, annote = { Introduces (independently from Anderson) atomic snapshot memory. } } @inproceedings{AndersonJ90, author = {J. H. Anderson}, title = {Composite Registers}, pages = {15--29}, year = 1990, booktitle = podc90, annote = { Introduces (independently from Afek et al.) atomic snapshot memory, with bounded algorithms. } } @inproceedings{Styer92, author = {E. Styer}, title = {Improving Fast Mutual Exclusion}, pages = {159--168}, year = 1992, booktitle = podc92 } @inproceedings{AndMoi94, author = {J. H. Anderson and M. Moir}, title = {Using $k$-Exclusion to Implement Resilent, Scalable Shared Objects}, pages = {141--150}, year = 1994, booktitle = podc94 } @inproceedings{DoGaSh88, author = {D. Dolev and E. Gafni and N. Shavit}, title = {Towards a Non-Atomic Era: $l$-Exclusion as a Test Case}, pages = {78--92}, year = 1988, booktitle = stoc88 } @inproceedings{FiLyBuBo79, author = {M. Fischer and N. Lynch and J. Burns and A. Borodin}, title = {Resource Allocation with Immunity to Process Failure}, pages = {234--254}, year = 1979, booktitle = focs79 } @article{Lamport83, author = {L. Lamport}, title = {Specifying Concurrent Program Modules}, pages = {190--222}, year = 1983, journal = toplas, volume = 5, number = 2, annote = { A method of specifying concurrent programs, which may have liveness and safety properties. Does not use just pre- and post-conditions, but temporal logic, since we may have to specify that programs wait for certain events. Contains a wait-free queue for 2 processes. } } @inproceedings{Herlihy91d, author = {M. Herlihy}, title = {Randomized Wait-Free Concurrent Objects}, pages = {11--21}, year = 1991, booktitle = podc91, annote = { Randomized wait-free construction for any RMW primitive from Read and Write. } } @inproceedings{SakZah91, author = {M. Saks and F. Zaharoglou}, title = {Optimal Space Distributed Move-To-Front Lists}, pages = {65--73}, year = 1991, booktitle = podc91 } @inproceedings{Lazowska93, author = {E. D. Lazowska}, title = {Recent Trends in Experimental Operating Systems Research}, pages = {13--19}, year = 1993, booktitle = podc93, annote = { Mentions lock-free synchronization, and the need for experimental analysis. } } @inproceedings{AttRac93, author = {H. Attiya and O. Rachman}, title = {Atomic Snapshots in $O(n \log n)$ Operations}, pages = {29--40}, year = 1993, booktitle = podc93 } @inproceedings{KleMul93, author = {J. Kleinberg and S. Mullainathan}, title = {Resource Bounds and Combinations of Consensus Objects}, pages = {133--143}, year = 1993, booktitle = podc93 } @inproceedings{YanAnd93, author = {J.-H. Yang and J. H. Anderson}, title = {Fast, Scalable Synchronization with Minimal Hardware Support}, pages = {171--182}, year = 1993, booktitle = podc93 } @inproceedings{ChoSin93, author = {M. Choi and A. K. Singh}, title = {Adaptive Solutions to the Mutual Exclusion Problem}, pages = {183--194}, year = 1993, booktitle = podc93 } @inproceedings{AgaChe89, author = {A. Agarwal and M. Cherian}, title = {Adaptive Backoff Synchronization Techniques}, pages = {396--406}, year = 1989, booktitle = isca89, annote = { Simulations of using adaptive backoff on barrier problems. } } @book{WeiSmi94, author = {S. Weiss and J. E. Smith}, title = {{POWER} and {PowerPC}}, year = 1994, publisher = morgank, annote = { Description of the PowerPC architecture. Shows how to use LL/SC to implement Fetch-and-Add and locks. } } @book{LeoBha87, title = {{VAX} Architecture Reference Manua}, year = 1987, editor = {T. E. Leonard}, publisher = {{DECbooks}}, address = {Bedford, MA}, annote = { Discusses synchronization primitives on VAX architecture, including the queue primitives. } } @book{Intel90a, author = {Intel Corporation}, title = {{i860} 64-Bit Microprocessor Programmer's Reference Manual}, year = 1990, publisher = {Intel}, address = {Mt.\ Prospect, IL}, annote = { Describes synchronization primitives on the i860 architecture, including the LOCK and UNLOCK atomic sequence. } } @book{Intel90b, author = {Intel Corporation}, title = {{i486} Processor Programmer's Reference Manual}, year = 1990, publisher = {Intel}, address = {Santa Clara, CA}, annote = { Describes synchronization primitives on the i486 architecture. } } @book{Motorola86, author = {Motorola}, title = {{MC68020} 32-Bit Microprocessor User's Manual}, year = 1986, edition = {2nd}, publisher = {Prentice-Hall}, annote = { Description of CAS and CAS2 synchronization primitives on 68020. } } @book{Motorola89, author = {Motorola}, title = {{MC68030} User's Manual}, year = 1989, publisher = {Prentice-Hall}, annote = { Description of CAS and CAS2 synchronization primitives on 68030, also supposedly how to manipulate a list using them. } } @book{MSSW94, title = {The {PowerPC} Architecture}, year = 1994, editor = {C. May and E. Silha and R. Simpson and H. Warren}, edition = {2nd}, publisher = morgank, annote = { Description of PowerPC architecture, including their version of LL/SC, and how to use it to do CSW, FAA, etc. } } @misc{Barnes95a, author = {G. Barnes}, title = {Implementing Asynchronous Data Structures Using Suboperations}, year = 1995, note = {Manuscript}, annote = { Proposes implementing lock-free objects using suboperations, in order to increase effective parallelism. Uses nested LL/SC. } } @techreport{Barnes94, author = {G. Barnes}, title = {Wait-Free Algorithms for Heaps}, year = 1994, number = {94--12--07}, institution = washington, type = tr } @techreport{IsRa93b, author = {A. Israeli and L. Rappoport}, title = {Efficient Wait-Free Implementation of a Concurrent Prority Queue}, year = 1993, number = {781}, institution = technion, type = tr } @inproceedings{HerMos93, author = {M. Herlihy and J. E. B. Moss}, title = {Transactional Memory: {Architectural} Support For Lock-Free Data Structures}, year = 1993, booktitle = isca93, annote = { Presentation of transactional memory. } } @inbook{Motorola89a, author = {Motorola}, title = {{MC68020} 32-Bit Microprocessor User's Manual}, pages = {3-194--3-197}, year = 1989, edition = {3rd}, publisher = {Prentice Hall}, annote = { Description of how to use CAS and CAS2 primitives to implement counters, stacks, singly- and doubly-linked lists. } } @book{Heinrich93, author = {J. Heinrich}, title = {{MIPS R4000} User's Manual}, year = 1993, publisher = {Prentice Hall}, annote = { Description of how to use LL/SC pair on that architecture, how to implenent semaphores and counters. } } @book{Margulis90, author = {N. Margulis}, title = {{i860} Microprocessor Architecture}, year = 1990, publisher = mghill, annote = { How to use the LOCK/UNLOCK sequence to do synchronization, in particular how to implement standard synch. primitives like TAS, CAS, etc. } } @techreport{MichScott93, author = {M. M. Michael and M. L. Scott}, title = {Fast Mutual Exclusion, Even With Contention}, year = 1993, number = {460}, institution = rochester, type = tr, month = jun, annote = { Fast mutual exclusion algorithm, using only read and write. Performance results; faster than using hardware support. Uses ability to read and wrtie both full and half words. } } @misc{BaIsRa95, author = {G. Barnes and A. Israeli and L. Rappoport}, title = {Efficient Wait-Free Implementation of a Concurrent Priority Queue}, year = 1995, month = feb, note = {Manuscript}, annote = { Use Barnes' idea of suboperations to implement a concurrent priority queue as a heap, extending Israeli and Rappoport's previous algorithm. Does not use SC2 like the previous algorithm, but appears to require nested LL/SC. } } @techreport{GlewHwu91, author = {A. Glew and W.-M. Hwu}, title = {A Feature Taxonomy and Survey of Synchronization Primitive Implementations}, year = 1991, number = {CRHC-91-7}, institution = {Center for Reliable and High-Performance Computing, University of Illinois at Urbana-Champaign}, type = tr, month = feb, annote = { Good survey of various synchronization primitives. } } @inproceedings{Ellis79, author = {C. S. Ellis}, title = {Concurrent Search and Insertion in {AVL} Trees}, pages = {250-256}, year = 1979, booktitle = icpp79, annote = { Implements concurrent AVL trees using various types of read and write locks. } } @inproceedings{GoVeWo89, author = {J. R. Goodman and M. K. Vernon and P. J. Woest}, title = {Efficient Synchronization Primitives for Large-Scale Cache-Coherent Multiprocessors}, pages = {64--75}, year = 1989, booktitle = asplos89, annote = { Hardware queue locks (QOLB?), software combining trees. } } @article{LLGWGHHL92, author = {D. Lenoski and others}, title = {The {Stanford DASH} Multiprocessor}, pages = {63--79}, year = 1992, journal = ieeecomp, volume = 25, number = 3, annote = { Describes hardware queue locks? } } @article{ElOl88, author = {C. S. Ellis and T. J. Olson}, title = {Algorithms for Parallel Memory Allocation}, pages = {303--345}, year = 1988, journal = ijpp, volume = 17, number = 4, annote = { Analyze four different algorithms for first-fit allocation, inlcuding experiments. One of the algorithms allows lock-free searching of the free-list, but not insertion or deletion. } } @article{Peterson83, author = {G. L. Peterson}, title = {Concurrent Reading While Writing}, pages = {46--55}, year = 1983, journal = toplas, volume = 5, number = 1, annote = { Seminal atomic register paper. } } @techreport{Stone82, author = {H. Stone}, title = {Parallel Memory Allocation Using the {FETCH-AND-ADD} Instruction}, year = 1982, number = {RC 9674}, institution = ibmwatson, type = tr, month = nov } @article{Ford88, author = {R. Ford}, title = {Concurrent Algorithms for a Real Time Memory Management System}, pages = {10--23}, year = 1988, journal = ieeesoft, month = sep, annote = { Use of optimisitc concurrency control (via small critical sections) for memory management. } } @techreport{HMPS94, author = {G. C. Hunt and M. M. Michael and S. Parthasarathy and M. L. Scott}, title = {An Efficient Algorithm for Concurrent Priority Queue Heaps}, year = 1994, number = {560}, institution = rochester, type = tr, month = dec } @inproceedings{ShaTou95, author = {N. Shavit and D. Touitou}, title = {Software Transactional Memory}, pages = {204--213}, year = 1995, booktitle = podc95 } @inproceedings{ShaTou95b, author = {N. Shavit and D. Touitou}, title = {Elimination Trees and the Construction of Pools and Stacks}, pages = {}, year = 1995, booktitle = spaa95 } @inproceedings{AndMoi95, author = {J. H. Anderson and M. Moir}, title = {Universal Constructions for Multi-Object Operations}, pages = {184--193}, year = 1995, booktitle = podc95 } @article{Anderson94, author = {J. H. Anderson}, title = {Multi-Writer Composite Registers}, pages = {175--}, year = 1994, journal = dc, volume = {7}, month = May } @article{Merritt94, author = {M. Merritt}, title = {Atomic M-Register Operations}, pages = {213--}, year = 1994, journal = dc, volume = {7}, month = May } @article{Skudlarek95, author = {J. P. Skudlarek}, title = {A Methodology for Implementing Highly Concurrent Data Objects --- {Note}}, pages = {45--}, year = 1995, journal = toplas, volume = {17}, month = Jan } @article{Herlihy95, author = {M. Herlihy}, title = {Scalable Concurrent Counting}, pages = {343--364}, year = 1995, journal = tocs, volume = 13, month = nov }