Article

Efficient multi-word locking using randomization

Authors:

Phuong Hoai Ha,

Philippas Tsigas,

Mirjam Wattenhofer,

Rogert WattenhoferAuthors Info & Claims

PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

Pages 249 - 257

https://doi.org/10.1145/1073814.1073862

Published: 17 July 2005 Publication History

Get Access

Abstract

In this paper we examine the general multi-word lock problem, where processes are allowed to multilock arbitrary registers. Aiming for a highly efficient solution we propose a randomized algorithm which successfully breaks long dependency chains, the crucial factor for slowing down an execution. In the analysis we focus on the 2-word lock problem and show that in this special case an execution of our algorithm takes with high probability at most time O(Δ³ log n /log log n), where n is the number of registers and Δ the maximal number of processes interested in the same register (the contention). Furthermore, we implemented our algorithm for the general multi-word lock problem on an SGI Origin2000 machine, demonstrating that our algorithm is not only of theoretical interest.

References

[1]

J. H. Anderson and M. Moir. Universal constructions for large objects. Proc. of the International Workshop on Distributed Algorithms, pages 168--182, 1995.

Digital Library

Google Scholar

[2]

H. Attiya, F. Kuhn, M. Wattenhofer, and R. Wattenhofer. Efficient adaptive collect using randomization. Proc. of the Intl. Symp. on Distributed Computing (DISC), pages 159--173, 2004.

Crossref

Google Scholar

[3]

G. Barnes. A method for implementing lock-free shared-data structures. Proc. of the ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 261--270, 1993.

Digital Library

Google Scholar

[4]

M. Choy and A. K. Singh. Efficient fault tolerant algorithms for resource allocation in distributed systems. Proc. of ACM Symp. on Theory of Computing (STOC), pages 593--602, 1992.

Digital Library

Google Scholar

[5]

P. H. Ha and P. Tsigas. Reactive multi-word synchronization for multiprocessors. The Journal of Instruction-Level Parallelism, page http://www.jilp.org/vol6/v6paper3.pdf, 2004.

Google Scholar

[6]

T. L. Harris, K. Fraser, and I. A. Pratt. A practical multi-word compare-and-swap operation. Proc. of the Intl. Symp. on Distributed Computing (DISC), pages 265--279, 2002.

Digital Library

Google Scholar

[7]

A. Israeli and L. Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. Proc. of Symp. on Principles of Distributed Computing (PODC), pages 151--160, 1994.

Digital Library

Google Scholar

[8]

N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computation, 21(1):193--201, 1992.

Digital Library

Google Scholar

[9]

N. A. Lynch. Upper bounds for static resource allocation in a distributed system. Journal for Computer and System Sciences, 23(2):254--278, 1981.

Crossref

Google Scholar

[10]

M. Moir. Transparent support for wait-free transactions. Proc. of the Intl. Workshop on Distributed Algorithms, pages 305--319, 1997.

Digital Library

Google Scholar

[11]

M. Naor and L. Stockmeyer. What can be computed locally? SIAM Journal on Computation, 24(6):1259--1277, 1995.

Digital Library

Google Scholar

[12]

N. Shavit and D. Touitou. Software transactional memory. Proc. of Symp. on Principles of Distributed Computing (PODC), pages 204--213, 1995.

Digital Library

Google Scholar

[13]

E. Styer and G. L. Peterson. Improved algorithms for distributed resource allocation. Proc. of Symp. on Principles of Distributed Computing (PODC), pages 615--628, 1988.

Digital Library

Google Scholar

Cited By

View all

Umar IAnshus OHa P(2016)GreenBSTProceedings of the 22nd International Conference on Euro-Par 2016: Parallel Processing - Volume 983310.1007/978-3-319-43659-3_37(502-517)Online publication date: 24-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-319-43659-3_37
Frigo MHalpern PLeiserson CLewin-Berlin SMeyer auf der Heide FBender M(2009)Reducers and other Cilk++ hyperobjectsProceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures10.1145/1583991.1584017(79-90)Online publication date: 11-Aug-2009
https://dl.acm.org/doi/10.1145/1583991.1584017
Attiya HHillel E(2008)Highly-concurrent multi-word synchronizationProceedings of the 9th international conference on Distributed computing and networking10.5555/1785854.1785867(112-123)Online publication date: 5-Jan-2008
https://dl.acm.org/doi/10.5555/1785854.1785867
Show More Cited By

Recommendations

Partially effective randomization in simulations between arbitrary and common PRAMs

It is known that Θ(log n/log log n) steps are needed to simulate one step of ARBITRARY CRCW PRAMs by COMMON CRCW PRAMs, but it was open whether there is a faster simulation when randomization is allowed. This paper gives both positive and negative ...
RMR-efficient randomized abortable mutual exclusion
DISC'12: Proceedings of the 26th international conference on Distributed Computing

Recent research on mutual exclusion for shared-memory systems has focused on local spin algorithms. Performance is measured using the remote memory references (RMRs) metric. As common in recent literature, we consider a standard asynchronous shared ...
On the time and space complexity of randomized test-and-set
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

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 ...

Comments

Information & Contributors

Information

Published In

PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

July 2005

364 pages

ISBN:1581139942

DOI:10.1145/1073814

General Chair:
Marcos Aguilera
HP Labs
,
Program Chair:
James Aspnes
Yale University

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: 17 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC05

Sponsor:

PODC05: ACM Symposium on Principles of Distributed Computing

July 17 - 20, 2005

NV, Las Vegas, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
245
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Umar IAnshus OHa P(2016)GreenBSTProceedings of the 22nd International Conference on Euro-Par 2016: Parallel Processing - Volume 983310.1007/978-3-319-43659-3_37(502-517)Online publication date: 24-Aug-2016
https://dl.acm.org/doi/10.1007/978-3-319-43659-3_37
Frigo MHalpern PLeiserson CLewin-Berlin SMeyer auf der Heide FBender M(2009)Reducers and other Cilk++ hyperobjectsProceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures10.1145/1583991.1584017(79-90)Online publication date: 11-Aug-2009
https://dl.acm.org/doi/10.1145/1583991.1584017
Attiya HHillel E(2008)Highly-concurrent multi-word synchronizationProceedings of the 9th international conference on Distributed computing and networking10.5555/1785854.1785867(112-123)Online publication date: 5-Jan-2008
https://dl.acm.org/doi/10.5555/1785854.1785867
Attiya HHillel E(2008)Highly-Concurrent Multi-word SynchronizationDistributed Computing and Networking10.1007/978-3-540-77444-0_9(112-123)Online publication date: 2008
https://doi.org/10.1007/978-3-540-77444-0_9
Attiya H(2007)Concurrency and the Principle of Data LocalityIEEE Distributed Systems Online10.5555/1304038.13040848:9(3)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.5555/1304038.1304084
Attiya H(2007)Concurrency and the Principle of Data LocalityIEEE Distributed Systems Online10.1109/MDSO.2007.43700998:9(3-3)Online publication date: Sep-2007
https://doi.org/10.1109/MDSO.2007.4370099

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Cited By

Index Terms

Recommendations

Partially effective randomization in simulations between arbitrary and common PRAMs

RMR-efficient randomized abortable mutual exclusion

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

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Partially effective randomization in simulations between arbitrary and common PRAMs

RMR-efficient randomized abortable mutual exclusion

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

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations