Advertisement
Published in:
2011 | OriginalPaper | Chapter
Sub-logarithmic Test-and-Set against a Weak Adversary
Authors : Dan Alistarh, James Aspnes
Published in: Distributed Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A randomized implementation is given of a test-and-set register with
O
(log log
n
) 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.