Analysing the Average Time Complexity of Lock-Free Data Structures

Lock-free implementations of shared data structures guarantee that some operation eventually completes. However, individual operations may not complete, as long as other operations continue to be completed. Thus, worst-case time complexity of individual operations may not be defined. Thus, an amortized analysis of the time complexity is more suitable. This talk will survey some results and techniques used to analyse the average time required to perform operations on lock-free implementations in shared-memory systems.Non UBCUnreviewedAuthor affiliation: York UniversityFacult