Test and Set in Optimal Space

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.Non UBCUnreviewedAuthor affiliation: University of CalgaryFacult