BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Analysing the Average Time Complexity of Lock-Free Data Structures Ruppert, Eric


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International