Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated

Building 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.