BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Test and Set in Optimal Space Higham, Lisa


Several new and existing components and techniques are used to achieve two new results. - A obstruction-free implementation of test&set from O(log n) registers, thus establishing that the existing lower bound is asymptotically tight. - A randomized wait-free implementation of test and set from O(log n) registers and having O(log*n) solo step complexity under the oblivious adversary. I will describe these techniques, present details of 3 of them, and show how they are combined to provide these two algorithms.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International