2014 | OriginalPaper | Chapter
Solo-Fast Universal Constructions for Deterministic Abortable Objects
Authors : Claire Capdevielle, Colette Johnen, Alessia Milani
Published in: Distributed Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we study efficient implementations for deterministic abortable objects. Deterministic abortable objects behave like ordinary objects when accessed sequentially, but they may return a special response
abort
to indicate that the operation failed (and did not take effect) when there is contention.
It is impossible to implement deterministic abortable objects only with read/write registers [3]. Thus, we study
solo-fast
implementations. These implementations use stronger synchronization primitives, e.g., CAS, only when there is contention. We consider interval contention.
We present a non-trivial solo-fast universal construction for deterministic abortable objects. A universal construction is a method for obtaining a concurrent implementation of any object from its sequential code. The construction is
non-trivial
since in the resulting implementation a failed process can cause only a finite number of operations to abort. Our construction guarantees that operations that do not modify the object always return a legal response and do not use CAS. Moreover in case of contention, at least one writing operation succeeds. We prove that our construction has asymptotically optimal space complexity for objects whose size is constant.