In a shared-memory system, asynchronous processes communicate via typed shared objects, such as registers, test&sets, and queues. The need to implement an object of one type from objects of other types arises often in such systems. Recent research has focussed mostly on wait-free implementations. Such an implementation guarantees that every process can complete every operation on the implemented object in a finite number of its own steps, regardless of whether other processes are fast, slow, or have crashed. From now on, we write "implementation" and "implement" as abbreviations for "wait-free implementation" and "wait-free implement", respectively. If an implementation is not wait-free, we will explicitly state so.
展开▼
