@misc{68000man, 
		  author = {{}},
		  title = {M68000 Family Programmer's Reference Manual,
Motorola, Inc.},
		  year = 1989
}

@misc{ALPHAman,
		  author = {R. Sites, ed.},
		  title = {DEC Alpha Architecture, Digital
Press}, 
		  address = {Burlington, Massachussets},
		  year = 1992
}
		  
@misc{PowerPC,
		  author = {},
		  title = {PowerPC 601 RISC Mircroprocessor User's Manual,
%Motorola Inc, 1993}
}
		  
@misc{R4000,
		  author = {Joseph Heinrich},
		  title = {MIPS R4000 User's Manual,  PTR
Prentice Hall, Englewood Cliffs NJ}, 
		  year = 1993
}
		  
@misc{Sparcman,
		  author = {},
		  title = {Sparc Architecture Manual V9 v8}
}
		  
@misc{Sparcman,
		  author = {},
		  title = {The SPARC Architecture Manual Version 9, Sun Inc.}
}
		  
@misc{VAXman,
		  author = {},
		  title = {VAX11 Architecture Handbook, Digital Equipment
Corporation  1979
		  }
		  }

@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}
}

@misc{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
}
		  
@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.
		  }}
		  
@InProceedings{Mogul:1996:ERL,
  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",
  year =         "1996",
  ISBN =         "1-880446-76-6",
  series =       "USENIX Conference Proceedings 1996",
  pages =        "99--111 (or 99--112??)",
  day =          "22--26",
  month =        jan,
  year =         "1996",
  bibdate =      "Fri Oct 18 07:24:24 MDT 1996",
  acknowledgement = ack-nhfb,
  affiliation =  "Digital Equipment Corporation Western Research
                 Laboratory (author \#1). AT\&T Bell Laboratories
                 (author \#2)",
  keywords =     "USENIX",
  searchkey =    "su:usenix, cn:usenix",

@Article{SALTZER84,
  key =          "Saltzer et al.",
  author =       "J. H. Saltzer and D. P. Reed and D. 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",
  keywords =     "design; data communication; protocol design; design
                 principles",
  abstract =     "This paper presents a design principle that helps
                 guide placement of functions among the modules of a
                 distributed computer system. The principle, called the
                 end-to-end argument, suggests that functions placed at
                 low levels of a system may be redundant or of little
                 value when compared with the cost of providing them at
                 that low level. Examples discussed in the paper include
                 bit-error recovery, security using encryption,
                 duplicate message suppression, recovery from system
                 crashes, and delivery acknowlegement. Low-level
                 mechanisms to support these functions are justified
                 only as performed enhancements.",
  bibdate =      "Wed Mar 6 11:12:06 1985",
}@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}

@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 = {??-??},
	month = {February}}


@misc{lispm:atomic-ops87,
		  author={Symbolics},
		  title={Genera 7.4 Documentation Set},
		  year=1989,
		  volume=8,
		  pages={38-39},
		  institution={Symbolics, Inc.}}
		  
		  
@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{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{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}
	}
		  
@misc{booch:components87,
		  author = {G. Booch},
		  title = {{\em Software Components with Ada},
Benjamin/Cummings, 1987.
}}
		  
@misc{cher:mem-based-msg93,
		  author = {D.R. Cheriton and R. Kutter},
		  title ={Optimizing
memory-based messaging for scalable shared memory multiprocessor
architectures.  To appear in {\em USENIX Computer Systems Journal} 1996.
(available as Stanford Computer Science Technical Report CS-93-123,
December 1993.)
}}
		  
@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
}
		  
@misc{druschel:osiris94,
		  author = {P. Druschel and L.L.Peterson and  B.S.Davies},
		  title = {Experiences
with a High Speed Network Adaptor: A Software Perspective, {\em
Proceedings of ACM SIGCOMM '94}, pp. 2--13, London, September 1994.
}}

@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}
		  }
		  
@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
}

@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
		  }
@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}


@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}
		  }
		  
@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)"}
		  
@article{saltzer:end2end84,
  author =       "J. H. Saltzer and D. P. Reed and D. 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{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
		  }
		  
		  
@string{columbia        = "Columbia University"}
@string{tr              = "Technical Report"}

@string{proc            = "Proceedings of the "}
@string{proc1           = "Proceedings of "}

@string{spaa            = " Symposium on Parallel Algorithms 
                                and Architectures"}
@string{spaa98          = proc # "Tenth" # spaa}

@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
}

@misc{cher:V88,
		  author = {D.R. Cheriton},
		  title = {The V Distributed System.  {\em
Communications of the ACM}, 31(3), pp 314-333, March 1988
}}
		  
@misc{cher:V,
		  author = {D.R. Cheriton},
		  title = {The V. distributed operating system.
{\em Comm. ACM}, 31(2):105-115, February 1988}
}
		  
@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.
  }
}
		  
		  
@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. 
}
		  }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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{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{sosp89		= proc # "Twenty-First" # 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{spaa90          = proc # "Second" # spaa}
@string{spaa91          = proc # "Third" # spaa}
@string{spaa92          = proc # "Fourth" # spaa}
@string{spaa93          = proc # "Fifth" # spaa}
@string{spaa98          = proc # "Tenth" # spaa}

@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. Felton},
		  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 ??? can't
		  read photocopy}, 
		  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-uni94,
		  author = {Srikanth Ramamurthy and Mark Moir and James H. Anderson},
		  title = {Real-time Object Sharing with Minimal
		  System Support}, 
		  booktitle = {PODC 94?? guessing the year here.},
		  year = 1994
		  }
		  
@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{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{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 C.N. Dellarocas and A. 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}
		  }
		  
@misc{chesson:note96,
		  author = {G. Chesson},
		  title = {Personal Communication, December,
1996.
		  }}
		  
@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{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 = {Proceedings of the 7th Symposium on
		  Principles of Distributed Computing},
 		  pages = {276-290}, 
		  note = {Toronto, Ont., Canada}, 
		  month = {August 15-17}, 
		  year = 1988
}
		  
@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,
}

@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 = {123--149}, 
		  month = {January}, 
		  year = 1991
		  }
		  
@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{israeli:heap93,
		  author = {A. Israeli and L. 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 = {A. Israeli and L. 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}
}
		  
@misc{johnson:spinlock93,
		  author = {T. Johnson and K. Harathi},
		  title = {A Prioritized
Multiprocessor Spin Lock, Technical Report 93-??? (postscript doesn't
		  have TR number on it, look up on web), Dept. of Computer
and Information Science, University of Florida, 1993. 
		  }}
		  
@techreport{johnson:performance93,
	author = {T. Johnson},
	title = {Characterizing the Performance of Algorithms for
Lock-Free Objects}, 
	type = {Technical Report},
	number = {93-021}, 
	institution = {Dept. of Computer and Information Science,
Univ. of Florida},  
	year = 1993}
		  
@techreport{johnson:ics94,
	author = {T. Johnson and K. Harathi},
	title = {Interruptible Critical Sections}, 
	type = {Technical Report},
	number = {94-007}, 
	institution = {Dept. of Computer and Information Science,
University of Florida},  
	year = 1994}
		  
@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{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{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}
		  }
		  
@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 = {5??}, 
	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}
}
		  
@misc{michael:primitives94,
		  author = {Maged M. Michael and Michael L. Scott},
		  title = {Scalability of
		  Atomic Primitives on Distributed Shared Memory
		  Multiprocessors}, 
		  month = {July}, 
		  year = {1994}
		  }
		  
@inproceeedings{michael:primitives95,
		  author = {Maged M. Michael and Michael L. Scott},
		  title = {Implementation of General-purpose atmic
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 = {??--??},
		  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 = {??--??},
	note = {Saarbrucken, Germany, also published as
		  {\em Lecture Notes in Computer Science ???}},
	month = {September 24--26}, 
	year = {1997}
		  }
		  
@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{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{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}}
		  
		  
		  
@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}
		  
@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}
}

@misc{treiber:stack86,
	author = {R.K.Treiber},
	title = {Systems Programming: Coping with Parallelism. 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
}}
		  
@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
}