research-article

On the time and space complexity of randomized test-and-set

Authors:

George Giakkoupis,

Philipp WoelfelAuthors Info & Claims

PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

Pages 19 - 28

https://doi.org/10.1145/2332432.2332436

Published: 16 July 2012 Publication History

Get Access

Abstract

We study the time and space complexity of randomized Test-And-Set (TAS) implementations from atomic read/write registers in asynchronous shared memory models with n processes. We present an adaptive TAS algorithm with an expected (individual) step complexity of O(log^* k), for contention k, against the oblivious adversary, improving a previous (non-adaptive) upper bound of O(log log n) (Alistarh and Aspnes, 2011). We also present a modified version of the adaptive RatRace TAS algorithm (Alistarh et al., 2010), which improves the space complexity from O(n³) to O(n), while maintaining logarithmic expected step complexity against the adaptive adversary. We complement this upper bound with an Ω(log n) lower bound on the space complexity of any TAS algorithm that has the nondeterministic solo-termination property (which is a weaker progress condition than wait-freedom). No non-trivial lower bounds on the space requirements of TAS were known prior to this work.

References

[1]

Y. Afek, E. Gafni, J. Tromp, and P. M. B. Vitányi. Wait-free test-and-set. In Proc. of 6th WDAG, pages 85--94, 1992.

Digital Library

Google Scholar

[2]

D. Alistarh and J. Aspnes. Sub-logarithmic test-and-set against a weak adversary. In Proc. of 25th DISC, pages 97--109, 2011.

Digital Library

Google Scholar

[3]

D. Alistarh, H. Attiya, S. Gilbert, A. Giurgiu, and R. Guerraoui. Fast randomized test-and-set and renaming. In Proc. of 24th DISC, pages 94--108, 2010.

Digital Library

Google Scholar

[4]

J. Aspnes. A modular approach to shared-memory consensus, with applications to the probabilistic-write model. In Proc. of 20th PODC, pages 460--467, 2010.

Digital Library

Google Scholar

[5]

J. Aspnes. Faster randomized consensus with an oblivious adversary. In Proc. of 31st PODC, 2012. To appear.

Digital Library

Google Scholar

[6]

H. Attiya and K. Censor-Hillel. Lower bounds for randomized consensus under a weak adversary. SIAM J. on Comp., 39(8):3885--3904, 2010.

Digital Library

Google Scholar

[7]

H. Attiya, F. Kuhn, C. G. Plaxton, M. Wattenhofer, and R. Wattenhofer. Efficient adaptive collect using randomization. Distr. Comp., 18(3):179--188, 2006.

Digital Library

Google Scholar

[8]

J. E. Burns and N. A. Lynch. Bounds on shared memory for mutual exclusion. Inf. Comput., 107(2):171--184, 1993.

Digital Library

Google Scholar

[9]

W. Eberly, L. Higham, and J. Warpechowska-Gruca. Long-lived, fast, waitfree renaming with optimal name space and high throughput. In Proc. of 12th DISC, pages 149--160, 1998.

Digital Library

Google Scholar

[10]

F. E. Fich, M. Herlihy, and N. Shavit. On the space complexity of randomized synchronization. J. of the ACM, 45(5):843--862, 1998.

Digital Library

Google Scholar

[11]

W. Golab, D. Hendler, and P. Woelfel. An $o(1)$ RMRs leader election algorithm. SIAM J. on Comp., 39:2726--2760, 2010.

Digital Library

Google Scholar

[12]

M. Moir and J. H. Anderson. Fast, long-lived renaming. In Proc. of the 8th WDAG pages 141--155, 1994.

Digital Library

Google Scholar

[13]

J. Tromp and P. M. B. Vitányi. Randomized two-process wait-free test-and-set. Distr. Comp., 15(3):127--135, 2002.

Digital Library

Google Scholar

[14]

A. C.-C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. of the 17th FOCS, pages 222--227, 1977.

Digital Library

Google Scholar

Cited By

View all

Chung KChan TWen TShi E(2021)Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader ElectionAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_1(3-32)Online publication date: 11-Aug-2021
https://doi.org/10.1007/978-3-030-84245-1_1
Giakkoupis GWoelfel P(2019)Efficient randomized test-and-set implementationsDistributed Computing10.1007/s00446-019-00349-z32:6(565-586)Online publication date: 1-Jun-2019
https://doi.org/10.1007/s00446-019-00349-z
Aspnes JCensor-Hillel KYaakobi E(2018)Concurrent use of write-once memoryJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.12.001113(250-260)Online publication date: Mar-2018
https://doi.org/10.1016/j.jpdc.2017.12.001
Show More Cited By

Index Terms

On the time and space complexity of randomized test-and-set

Recommendations

Sublinear bounds for randomized leader election

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O ( 1 ) rounds and (with high probability) uses only O ( n log 3 / 2 n ) ...
An $O\sqrt n$ Space Bound for Obstruction-Free Leader Election
DISC 2013: Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205

We present a deterministic obstruction-free implementation of leader election from $O\sqrt n$ atomic O log n -bit registers in the standard asynchronous shared memory system with n processes. We provide also a technique to transform any deterministic ...
Randomized mutual exclusion with sub-logarithmic RMR-complexity

Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. Attiya, Hendler, and Woelfel (40th STOC, 2008) established ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

July 2012

410 pages

ISBN:9781450314503

DOI:10.1145/2332432

General Chair:
Darek Kowalski
U. of Liverpool, UK and IMDEA Networks, Spain
,
Program Chair:
Alessandro Panconesi
Sapienza, University of Rome, Italy

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '12

Sponsor:

SIGOPS
SIGACT
INESC-ID

PODC '12: ACM Symposium on Principles of Distributed Computing

July 16 - 18, 2012

Madeira, Portugal

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
313
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chung KChan TWen TShi E(2021)Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader ElectionAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_1(3-32)Online publication date: 11-Aug-2021
https://doi.org/10.1007/978-3-030-84245-1_1
Giakkoupis GWoelfel P(2019)Efficient randomized test-and-set implementationsDistributed Computing10.1007/s00446-019-00349-z32:6(565-586)Online publication date: 1-Jun-2019
https://doi.org/10.1007/s00446-019-00349-z
Aspnes JCensor-Hillel KYaakobi E(2018)Concurrent use of write-once memoryJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.12.001113(250-260)Online publication date: Mar-2018
https://doi.org/10.1016/j.jpdc.2017.12.001
Aspnes JCensor-Hillel KYaakobi E(2016)Concurrent Use of Write-Once MemoryStructural Information and Communication Complexity10.1007/978-3-319-48314-6_9(127-142)Online publication date: 4-Nov-2016
https://doi.org/10.1007/978-3-319-48314-6_9
Alistarh DGelashvili RVladu AGeorgiou CSpirakis P(2015)How To Elect a Leader Faster than a TournamentProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767420(365-374)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767420
Giakkoupis GHelmi MHigham LWoelfel PServedio RRubinfeld R(2015)Test-and-Set in Optimal SpaceProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746627(615-623)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746627
Anceaume ECastella FMostefaoui ASericola B(2015)A Message-Passing and Adaptive Implementation of the Randomized Test-and-Set ObjectProceedings of the 2015 IEEE 14th International Symposium on Network Computing and Applications (NCA)10.1109/NCA.2015.27(167-175)Online publication date: 28-Sep-2015
https://dl.acm.org/doi/10.1109/NCA.2015.27
Berenbrink PBrinkmann AElsässer RFriedetzky TNagel L(2015)Randomized Renaming in Shared Memory SystemsProceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium10.1109/IPDPS.2015.77(542-549)Online publication date: 25-May-2015
https://dl.acm.org/doi/10.1109/IPDPS.2015.77
Aspnes J(2015)Faster randomized consensus with an oblivious adversaryDistributed Computing10.1007/s00446-013-0195-y28:1(21-29)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1007/s00446-013-0195-y
Gelashvili R(2015)On the Optimal Space Complexity of Consensus for Anonymous ProcessesProceedings of the 29th International Symposium on Distributed Computing - Volume 936310.1007/978-3-662-48653-5_30(452-466)Online publication date: 7-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-662-48653-5_30
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Sublinear bounds for randomized leader election

An $O\sqrt n$ Space Bound for Obstruction-Free Leader Election

Randomized mutual exclusion with sub-logarithmic RMR-complexity