direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Eirini Spartinou's Publications

Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated
Citation key AHGKMV-LOESCACBE-11
Author Attiya, Hagit and Hendler, Danny and Guerraoui, Rachid and Kuznetsov, Petr and Michael, Maged M. and Vechev, Martin
Title of Book Proceedings of Symposium on Principles of Programming Languages (POPL '11)
Pages 487–498
Year 2011
ISBN 978-1-4503-0490-0
DOI http://dx.doi.org/10.1145/1926385.1926442
Location Austin, TX, USA
Address New York, NY, USA
Month January
Publisher ACM
Organization SIGACT / SIGPLAN
Abstract Building correct and efficient concurrent algorithms is known to be a difficult problem of fundamental importance. To achieve efficiency, designers spend significant time trying to remove unnecessary and costly synchronization. However, not only is this manual trial-and-error process ad-hoc and error-prone, but it often leaves designers pondering the question of: is it inherently impossible to eliminate certain synchronization, or is it that I was unable to eliminate it on this attempt and I should keep trying? In this paper we respond to this question. We prove that it is impossible to build correct concurrent implementations of classic and ubiquitous specifications such as sets, queues, stacks, mutual exclusion and read-modify-write operations, that completely eliminate certain expensive synchronization. More specifically, we prove that one cannot avoid the use of: i) read-after-write (RAW), where a write to shared variable A is followed by a read to a different shared variable B or ii) atomic write-after-read (AWAR), where an atomic operation reads and then writes to shared locations. Unfortunately, enforcing any of these two patterns is expensive on virtually all mainstream processor architectures today. To enforce RAW, memory ordering–also called fence or barrier–instructions must be used. To enforce AWAR, atomic instructions such as compare-and-swap (or equivalent) are required. However, fences and atomic instructions are typically substantially slower–around 50 times–than regular instructions! Although designers of concurrent algorithms frequently struggle to avoid RAW and AWAR, their attempts are often futile. Our result explains exactly in which cases avoiding RAWand AWAR is impossible. Failure to use such synchronization will mean that the algorithm is incorrect and there is no need to even attempt to verify its correctness. On the flip side, our result indicates on which data structures designers can focus their efforts on.
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe