Sub-logarithmic test-and-set against a weak adversary

Dan Alistarh and James Aspnes. Sub-logarithmic test-and-set against a weak adversary. Distributed Computing: 25th International Symposium, DISC 2011. Lecture Notes in Computer Science 6950, Springer-Verlag, September 2011, pp. 97–109.

Abstract

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.

• DISC 2011 proceedings version: PDF.

BibTeX

@inproceedings{AlistarhA2011,
author = {Dan Alistarh and James Aspnes},
title = {Sub-logarithmic test-and-set against a weak adversary},
month = sep,
year = 2011,
booktitle="Distributed Computing: 25th International Symposium, DISC 2011",
series="Lecture Notes in Computer Science",
volume=6950,
publisher="Springer-Verlag",
pages={97--109},
}