skip to main content
10.1145/1146381.1146427acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Synchronizing without locks is inherently expensive

Published: 23 July 2006 Publication History

Abstract

It has been considered bon ton to blame locks for their fragility, especially since researchers identified obstruction-freedom: a progress condition that precludes locking while being weak enough to raise the hope for good performance. This paper attenuates this hope by establishing lower bounds on the complexity of obstruction-free implementations in contention-free executions: those where obstruction-freedom was precisely claimed to be effective. Through our lower bounds, we argue for an inherent cost of concurrent computing without locks.We first prove that obstruction-free implementations of a large class of objects, using only overwriting or trivial primitives in con-tention-free executions, have Ω(n) space complexity and Ω(log2 n) (obstruction-free) step complexity. These bounds apply to implementations of many popular objects, including variants of fetch&add, counter, compare&swap, and LL/SC. When arbitrary primitives can be applied in contention-free executions, we show that, in any implementation of binary consensus, or any perturbable object, the number of distinct base objects accessed and memory stalls incurred by some process in a contention free execution is Ω(√n). All these results hold regardless of the behavior of processes after they become aware of contention. We also prove that, in any obstruction-free implementation of a perturbable object in which processes are not allowed to fail their operations, the number of memory stalls incurred by some process that is unaware of contention is Ω(n).

References

[1]
H. Attiya, R. Guerraoui, and P. Kouznetsov. Computing with reads and writes in the absence of step contention. In Proceedings of the 19th International Symposium on Distributed Computing (DISC'05), 2005.
[2]
B. N. Bershad. Practical considerations for non-blocking concurrent objects. In Proceedings of the 14th IEEE International Conference on Distributed Computing Systems (ICDCS'93), pages 264--273, 1993.
[3]
T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225--267, March 1996.
[4]
D. Dolev, C. Dwork, and L. J. Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77--97, January 1987.
[5]
C. Dwork, M. Herlihy, and O. Waarts. Contention in shared memory algorithms. Journal of the ACM, 44(6):779--805, 1997.
[6]
F. Fich, M. Herlihy, and N. Shavit. On the space complexity of randomized synchronization. J. ACM, 45(5):843--862, 1998.
[7]
F. E. Fich, D. Hendler, and N. Shavit. Linear lower bounds on real-world implementations of concurrent objects. In Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS), 2005.
[8]
M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(3):374--382, April 1985.
[9]
D. Hendler and N. Shavit. Operation-valency and the cost of coordination. In Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 84--91, 2003.
[10]
M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124--149, January 1991.
[11]
M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. Software transactional memory for dynamic-sized data structures. In Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 92--101, 2003.
[12]
M. Herlihy, V. Luchango, and M. Moir. Obstruction-free synchronization: Double-ended queues as an example. In Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems (ICDCS'03), pages 522--529, 2003.
[13]
P. Jayanti, K. Tan, and S. Toueg. Time and space lower bounds for nonblocking implementations. SIAM Journal on Computing, 30(2):438--456, 2000.
[14]
A. LaMarca. A performance evaluation of lock-free synchronization protocols. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 130--140, 1994.
[15]
M. C. Loui and H. H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, pages 163--183, 1987.
[16]
V. Luchangco, M. Moir, and N. Shavit. On the uncontended complexity of consensus. In Proceedings of the 17th International Symposium on Distributed Computing (DISC'03), pages 45--59, 2003.
[17]
E. Ruppert. Determining consensus numbers. SIAM Journal of Computing, 30(4):1156--1168, 2000.
[18]
M. L. Scott and W. N. Scherer III. Contention management in dynamic software transactional memory. In PODC Workshop on Concurrency and Synchronization in Java Programs, July 2004.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. lock-free implementations
  2. lower bound
  3. memory contention
  4. obstruction-freedom
  5. perturbable objects
  6. step contention

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Wait-Free SynchronizationEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_472(2345-2351)Online publication date: 22-Apr-2016
  • (2011)Yet Another Simple Solution for the Concurrent Programming Control ProblemIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2010.17222:6(1056-1063)Online publication date: 1-Jun-2011
  • (2010)Principles of Transactional MemorySynthesis Lectures on Distributed Computing Theory10.2200/S00253ED1V01Y201009DCT0041:1(1-193)Online publication date: Jan-2010
  • (2010)Approximate shared-memory counting despite a strong adversaryACM Transactions on Algorithms10.1145/1721837.17218416:2(1-23)Online publication date: 6-Apr-2010
  • (2009)Approximate shared-memory counting despite a strong adversaryProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496819(441-450)Online publication date: 4-Jan-2009
  • (2008)On obstruction-free transactionsProceedings of the twentieth annual symposium on Parallelism in algorithms and architectures10.1145/1378533.1378587(304-313)Online publication date: 1-Jun-2008
  • (2008)Distributed computing and the multicore revolutionACM SIGACT News10.1145/1360443.136045839:1(62-72)Online publication date: 1-Mar-2008
  • (2008)Wait-Free SynchronizationEncyclopedia of Algorithms10.1007/978-0-387-30162-4_472(1015-1020)Online publication date: 2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media