Sub-Logarithmic Test-and-Set Against a Weak Adversary
A 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.
- View record in Web of Science
Record created on 2011-07-14, modified on 2016-08-09