Strict Linearizability and the Power of Aborting

Aguilera, Marcos K. ; Frolund, Svend

HP Development Company

关键词: shared objects;    concurrency;    linearizability;    aborting;    correctness condition;    specification;   

RP-ID  :  HPL-2003-241

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Linearizability is a popular way to define the concurrent behavior of shared objects. However, linearizability allows operations that crash to take effect at any time in the future. This can be disruptive to systems where crashes are externally visible. In such systems, an operation that crashes should either not happen or happen within some limited time frame -- preferably before the process crashes. We define strict linearizability to achieve this semantics. Strict linearizability and wait-freedom are difficult to achieve simultaneously. For example, we show that it is impossible to obtain a strictly- linearizable wait-free implementation of objects as simple as multi-reader registers from single-reader ones. To address this problem, we augment our shared objects by allowing them to abort their operations in the presence of concurrency. An aborted operation behaves like an operation that crashes: it may or may not take effect (but if it does, it does before the abort). We show that with abortable operations, there are strictly-linearizable wait-free implementations of consensus and hence of any object.