Eliminate a Parallelization Technique to Implement Expandable Lock-Free Deques

Abstract: The data Structures used in concurrent systems need to be modified. Modifications of shared data structures are done in several steps. If these steps are interleaved with modifications from other tasks, this can result in inconsistency of the data structure. Therefore the data structure needs to be protected from other tasks modifying it while the operation is executing. This can either be done using mutual exclusion or non-blocking methods. The focus of this paper is to give a review on efficient and practical non-blocking implementations of shared data structure and suggest alternative scheme in this direction.

Keywords:   Concurrency, Lock-Free Deques, Non-Blocking, Memory Management, Compare and Swap, Elimination