^November December – 2011 ^January

Two key synchronization paradigms for the construction of scalable concurrent data-structures are software combining and elimination.Elimination-based concurrent data-structures allow operations with reverse semantics (such as push and pop stack operations) to "collide" and exchange values without having to access a central location. Software combining, on the other hand, is effective when colliding operations have identical semantics: when a pair of threads performing operations with identical semantics collide, the task of performing the combined set of operations is delegated to one of the threads and the other thread waits for its operation(s) to be performed. Applying this mechanism iteratively can reduce memory contention and increase throughput. We present DECS, a novel Dynamic Elimination-Combining Stack algorithm,that scales well for all workload types. While maintaining the simplicity and low-overhead of an elimination-based stack, DECS manages to benefit from collisions of both identical- and reverse-semantics operations. Our empirical evaluation shows that DECS scales significantly better than both blocking and non-blocking best prior stack algorithms. This is joint work with Gal Bar-Nissan and Danny Hendler.