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.


Publié dans:
DISC
Présenté à:
DISC 2011
Année
2011
Publisher:
Berlin, Springer-Verlag Berlin
ISBN:
978-3-642-24099-7
Laboratoires:




 Notice créée le 2011-07-14, modifiée le 2019-12-05

n/a:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)