Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

Technical Reports

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Click here for full text: Postscript PDF

Strict Linearizability and the Power of Aborting

Aguilera, Marcos K.; Frolund, Svend


Keyword(s): shared objects; concurrency; linearizability; aborting; correctness condition; specification

Abstract: 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.

25 Pages

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.