Communications of the ACM
A Linearizability-based Hierarchy for Concurrent Specifications
Credit: Creativeneko
In the early 2000s, the multicore revolution began, when it became difficult to increase the clock speed of microprocessors, and manufacturers shifted to the approach of increasing performance through multiple processing cores per chip. The "free lunch" of relying on increasing clock speed to obtain faster programs was over. Unfortunately, developing multi-process programs can be dramatically more difficult. The difficulty of reasoning about many things happening at the same time is compounded by the fact that processes are executed in a highly asynchronous and unpredictable way, possibly even crashing, and furthermore, affected by low-level architectural details. An approach strongly advocated to cope with these difficulties was elegantly presented by Shavit:36
Key Insights
"It is infinitely easier and more intuitive for us humans to specify how abstract data structures behave in a sequential setting, where there are no interleavings. Thus, the standard approach to arguing the safety properties of a concurrent data structure is to specify the structure's properties sequentially."
No entries found