Non-blocking Synchronization made Practical
			  Michael Greenwald
		      Distributed Systems Group
			 Stanford University

Non-blocking synchronization (NBS) guarantees that at least one
process is always making progress.  Thus no process, even if stalled
or failed while holding a lock, can delay other processes, and
deadlock is impossible.  Non-blocking synchronization has significant
advantages over blocking synchronization; however it has not been
widely deployed to date.

This talk presents techniques used to build a multi-processor
operating system kernel, the CacheKernel, where synchronization was
done exclusively with NBS.  We discuss the key features (both hardware
and software) that made this possible, describe the techniques and
algorithms we used that took advantage of these features, and explain
how these same techniques can be applied to other systems.

Finally, we briefly discuss how NBS can be used to support
synchronized methods in JAVA by simplifying implementation, and
increasing system robustness.