🚀 go-pugleaf

I posted something liek this recently, but would like to repeat it. I have
been working with Maurice Herlihy for a little while now on problems such as
lock-free garbage collection (that work will be presented at the next SPAA and
will appear in an IEEE journal next year). I have a firm belief (but no proof
yet) that CAS2, which allows atomic compare and swap of TWO, ARBITRARY memory
locations is strictly more powerful than CAS, in the sense that it allows
implementation of EFFICIENT lock-free (and wait-free) algorithms that CAS is
not strong enought to implement efficiently. In particular, to update many
elements of a shared structure atomically with CAS appears to require building
a copy of the ENTIRE structure and then using CAS to swing a pointer to the
new version. CAS2 supports a reasonable, atomic, update-in-place of any number
of elements of a shared data structure. I hope to have firm results and proofs
before too long. Meanwhile, it is something hardware designers may wish to
start thinking about ....					Eliot Moss
--

		J. Eliot B. Moss, Assistant Professor
		Department of Computer and Information Science
		Lederle Graduate Research Center
		University of Massachusetts
		Amherst, MA  01003
		(413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu