Brief Announcement: Abortable and Query-Abortable Objects

摘要

The setting for this paper is a distributed system in which asynchronous processes interact by accessing linearizable, wait-free shared objects [2]. The typical task in such a system is to design an implementation of a target object given certain "base objects". The complexity of such implementations is mostly due to the fact that multiple processes may access the target object concurrently. It has been observed that in some systems contention on shared objects is rare [3]. It is therefore tempting to try to simplify the task of implementing shared objects by allowing them to exhibit degraded behaviour in the (hopefully rare) event of contention.