Progress Guarantees When Composing Lock-Free Objects

Highly concurrent and reliable data objects are vital for parallel programming. Lock-free shared data objects are highly concurrent and guarantee that at least one operation, from a set of concurrently executed operations, finishes after a finite number of steps regardless of the state of the other operations. Lock-free data objects provide progress guarantees on the object level. In this paper, the authors first examine the progress guarantees provided by lock-free shared data objects that have been constructed by composing other lock-free data objects.