An implementation of a shared data object is wait-free if the operations of the data object are implemented without any unbounded busy-waiting loops or idle-waiting primitives. Wait-free shared data objects are inherently resilient to fail-stop faults: a process that fails (i.e., stops its execution) while accessing such a data object cannot block the progress of any other process; intuitively, a faulty process has the same effect on other processes as a very slow one. Two research projects are contained herein, both of which extend previous work on wit-free shared data objects. The first project considers the implementation of wait-free shared data objects with read-modify-write operations. Such operations lie at the heart of many transaction processing applications; thus, because wait-free shared data objects are inherently fault tolerant, this work offers an attractive alternative to more traditional transaction processing schemes, such as checkpointing, logging, timeouts, etc. The second project considers the construction of wait-free shared data objects in message-passing systems. Such data objects provide the illusion of a fault-tolerant, virtual shared memory machine, and thus allow programmers to think in terms of shared memory when designing fault- tolerant algorithms for message-passing systems.
