A Lock-Free Algorithm for Concurrent Bags

A lock-free bag data structure supporting unordered buffering is presented in this paper. The algorithmsupports multiple producers and multiple consumers, as well as dynamic collection sizes. To handle concurrencyefficiently, the algorithm was designed to thrive for disjoint-access-parallelism for the supportedsemantics. Therefore, the algorithm exploits a distributed design combined with novel techniques for handlingconcurrent modifications of linked lists using double marks, detection of total emptiness, and efficientmemory management. Experiments on a 24-way multi-core platform show significantly better performancefor the new algorithm compared to previous algorithms of relevance.Keywords: concurrent; data structure; non-blocking; shared memory