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.


Published in:
DISC
Presented at:
DISC 2011
Year:
2011
Publisher:
Berlin, Springer-Verlag Berlin
ISBN:
978-3-642-24099-7
Laboratories:




 Record created 2011-07-14, last modified 2018-09-13

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)