000161286 001__ 161286
000161286 005__ 20190316235004.0
000161286 0247_ $$2doi$$a10.1145/1925844.1926442
000161286 02470 $$2ISI$$a000286472700041
000161286 037__ $$aCONF
000161286 245__ $$aLaws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated
000161286 269__ $$a2011
000161286 260__ $$c2011
000161286 336__ $$aConference Papers
000161286 520__ $$aBuilding correct and efficient concurrent algorithms is known to be a difficult problem of fundamental importance. To achieve ef- ficiency, designers try to remove unnecessary and costly synchro- nization. However, not only is this manual trial-and-error process ad-hoc, time consuming and error-prone, but it often leaves design- ers pondering the question of: is it inherently impossible to elimi- nate 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 im- possible to build concurrent implementations of classic and ubiqui- tous specifications such as sets, queues, stacks, mutual exclusion and read-modify-write operations, that completely eliminate the use of expensive synchronization. We prove that one cannot avoid the use of either: i) read-after- write (RAW), where a write to shared variable A is followed by a read to a different shared variable B without a write to B in between, or ii) atomic write-after-read (AWAR), where an atomic operation reads and then writes to shared locations. Unfortunately, enforcing RAW or AWAR is expensive on all current mainstream processors. To enforce RAW, memory ordering–also called fence or barrier– instructions must be used. To enforce AWAR, atomic instructions such as compare-and-swap are required. However, these instruc- tions are typically substantially slower than regular instructions. Although algorithm designers frequently struggle to avoid RAW and AWAR, their attempts are often futile. Our result characterizes the cases where avoiding RAW and AWAR is impossible. On the flip side, our result can be used to guide designers towards new algorithms where RAW and AWAR can be eliminated.
000161286 6531_ $$aAlgorithms
000161286 6531_ $$aConcurrency
000161286 6531_ $$aLower Bounds
000161286 700__ $$aAttiya, Hagit
000161286 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000161286 700__ $$aHendler, Danny
000161286 700__ $$aKuznetsov, Petr
000161286 700__ $$aMichael, Maged M.
000161286 700__ $$aVechev, Martin
000161286 7112_ $$dJanuary 26–28, 2011$$cAustin, Texas, USA$$aACM POPL 2011
000161286 773__ $$tProceedings of the ACM POPL'11
000161286 8564_ $$uhttps://infoscience.epfl.ch/record/161286/files/popl168gf-attiya.pdf$$zn/a$$s206307$$yPublisher's version
000161286 909C0 $$xU10407$$0252114$$pDCL
000161286 909CO $$ooai:infoscience.tind.io:161286$$qGLOBAL_SET$$pconf$$pIC
000161286 917Z8 $$x166927
000161286 917Z8 $$x166927
000161286 937__ $$aEPFL-CONF-161286
000161286 973__ $$rNON-REVIEWED$$sPUBLISHED$$aEPFL
000161286 980__ $$aCONF