We describe two improvements to introspective sorting and selection algorithms: a simple rule for fine-grained introspection that detects potential worst-case performance after only a small constant number of partitioning steps, and the use of remedial randomization as an intervention strategy in order to reduce the performance penalty for false positives. We present experimental results showing that these techniques provide significant improvements in the running time for worst-case and other troublesome inputs, without sacrificing performance on well-behaved inputs. Copyright © 2000 John Wiley & Sons, Ltd.

No abstract available.

Lock-free data structures implement concurrent objects without the use of mutual exclusion. This approach can avoid performance problems due to unpredictable delays while processes are within critical sections. Although universal methods are known that give lock-free data structures for any abstract data type, the overhead of these methods makes them inefficient when compared to conventional techniques using mutual exclusion, such as spin locks. We give lock-free data structures and algorithms for implementing a shared singly-linked list, allowing concurrent traversal, insertion, and deletion by any number of processes. We also show how the basic data structure can be used as a building block for other lock-free data structures. Our algorithms use the single word Compare-and-Swap synchronization primitive to implement the linked list directly, avoiding the overhead of universal methods, and are thus a practical alternative to using spin locks. 1 Introduction A concurrent object is an...