Sub-Logarithmic Test-and-Set Against a Weak Adversary

Alistarh, DanAspnes, James2011-07-142011-07-142011-07-14201110.1007/978-3-642-24100-0_7https://infoscience.epfl.ch/handle/20.500.14299/69589WOS:000306943200007A randomized implementation is given of a test-and-set register with O(log log it) individual step complexity and O(n) total step complexity against an oblivious adversary. The implementation is linearizable and multi-shot, and shows an exponential complexity improvement over previous solutions designed to work against a strong adversary.Sub-Logarithmic Test-and-Set Against a Weak Adversarytext::conference output::conference proceedings::conference paper