conference paper
Sub-Logarithmic Test-and-Set Against a Weak Adversary
2011
Distributed Computing. DISC 2011
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.
Type
conference paper
Web of Science ID
WOS:000306943200007
Author(s)
Aspnes, James
Date Issued
2011
Publisher
Publisher place
Berlin
Published in
Distributed Computing. DISC 2011
ISBN of the book
978-3-642-24099-7
Total of pages
13
Series title/Series vol.
Lecture Notes in Computer Science; 6950
Start page
97
End page
109
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
| Event name | Event place | Event date |
Rome, Italy | September 20-22, 2011 | |
Available on Infoscience
July 14, 2011
Use this identifier to reference this record