Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
Publications by Type: Conference and Workshop Publications
see also conference papers, workshop papers, demos, and posters. (under construction)
|Autor||Attiya, Hagit and Guerraoui, Rachid and Hendler, Danny and Kouznetsov, Petr|
|Buchtitel||Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC 06)|
|Ort||Denver, CO, USA|
|Zusammenfassung||It has been considered bon ton to blame locks for their fragility, especially since researchers identified obstruction-freedom: a progress condition that precludes locking while being weak enough to raise the hope for good performance. This paper attenuates this hope by establishing lower bounds on the complexity of obstruction-free implementations in contention-free executions: those where obstruction-freedom was precisely claimed to be effective. Through our lower bounds, we argue for an inherent cost of concurrent computing without locks. We first prove that obstruction-free implementations of a large class of objects, using only overwriting or trivial primitives in con-tention-free executions, have Ω(n) space complexity and Ω(log2 n) (obstruction-free) step complexity. These bounds apply to implementations of many popular objects, including variants of fetch&add, counter, compare&swap, and LL/SC. When arbitrary primitives can be applied in contention-free executions, we show that, in any implementation of binary consensus, or any perturbable object, the number of distinct base objects accessed and memory stalls incurred by some process in a contention free execution is Ω(√n). All these results hold regardless of the behavior of processes after they become aware of contention. We also prove that, in any obstruction-free implementation of a perturbable object in which processes are not allowed to fail their operations, the number of memory stalls incurred by some process that is unaware of contention is Ω(n).|