Sub-logarithmic test-and-set against a weak adversary
Alistarh D-A, Aspnes J. 2011. Sub-logarithmic test-and-set against a weak adversary. DISC: Distributed Computing, LNCS, vol. 6950 LNCS, 97–109.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Author
Alistarh, Dan-AdrianISTA 
;
Aspnes, James
;
Aspnes, JamesSeries Title
LNCS
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.
Publishing Year
Date Published
2011-01-01
Acknowledgement
The work of Dan Alistarh was supported by the NCCR MICS Project. The work of James Aspnes was supported in part by NSF grant CCF-0916389.
Volume
6950 LNCS
Page
97 - 109
Conference
DISC: Distributed Computing
IST-REx-ID
Cite this
Alistarh D-A, Aspnes J. Sub-logarithmic test-and-set against a weak adversary. In: Vol 6950 LNCS. Springer; 2011:97-109. doi:10.1007/978-3-642-24100-0_7
Alistarh, D.-A., & Aspnes, J. (2011). Sub-logarithmic test-and-set against a weak adversary (Vol. 6950 LNCS, pp. 97–109). Presented at the DISC: Distributed Computing, Springer. https://doi.org/10.1007/978-3-642-24100-0_7
Alistarh, Dan-Adrian, and James Aspnes. “Sub-Logarithmic Test-and-Set against a Weak Adversary,” 6950 LNCS:97–109. Springer, 2011. https://doi.org/10.1007/978-3-642-24100-0_7.
D.-A. Alistarh and J. Aspnes, “Sub-logarithmic test-and-set against a weak adversary,” presented at the DISC: Distributed Computing, 2011, vol. 6950 LNCS, pp. 97–109.
Alistarh D-A, Aspnes J. 2011. Sub-logarithmic test-and-set against a weak adversary. DISC: Distributed Computing, LNCS, vol. 6950 LNCS, 97–109.
Alistarh, Dan-Adrian, and James Aspnes. Sub-Logarithmic Test-and-Set against a Weak Adversary. Vol. 6950 LNCS, Springer, 2011, pp. 97–109, doi:10.1007/978-3-642-24100-0_7.
Google Scholar