Campus Event Calendar
Event Entry
New for: D1, D2, D3, D4, D5
What and Who
Latest news about lock-free object implementations
Petr Kouznetsov
EPFL
SWS Colloquium
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
Expert Audience
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 8 July 2005
10:00
-- Not specified --
46.1 - MPII
024
Saarbrücken
Abstract
Lock-free implementations of shared data objects do not rely on any form of mutual exclusion, and thereby allow processes to overcome adverse operating system affects. Wait-free implementations provide the strongest form of lock-freedom and guarantee that every process can complete its operation, regardless of the execution speeds of other processes. They are in this sense very appealing, but turn out to be impossible or very expensive to achieve in many practical settings. Recently, researchers suggested a weaker liveness property, called obstruction-freedom, that guarantees progress only when there is no contention, which is argued to be the most common case in practice. However, the notion of contention was very widely interpreted, and, as a result, the limitations of implementations ensuring only these weaker properties remained unclear.
We formally define an adequate measure of contention, which we call step contention, and present a generic obstruction-free implementation that ensures progress for step contention-free operations. Our implementation is linear in time and space with respect to the number of concurrent processes. We show that these complexities are asymptotically optimal, and hence generic obstruction-free implementations are inherently expensive.
Contact
Brigitta Hansen
0681 - 9325203
--email hidden
passcode not visible
logged in users only
Carina Schmitt, 05/15/2006 10:34
Brigitta Hansen, 06/29/2005 13:54 -- Created document.
Brigitta Hansen, 06/29/2005 13:54 -- Created document.