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

An Ω (n log n) lower bound on the cost of mutual exclusion

Published: 23 July 2006 Publication History

Abstract

We prove an Ω(n log n) lower bound on the number of non-busywaiting memory accesses by any deterministic algorithm solving n process mutual exclusion that communicates via shared registers. The cost of the algorithm is measured in the state change cost model, a variation of the cache coherent model. Our bound is tight in this model. We introduce a novel information theoretic proof technique. We first establish a lower bound on the information needed by processes to solve mutual exclusion. Then we relate the amount of information processes can acquire through shared memory accesses to the cost they incur. We believe our proof technique is flexible and intuitive, and may be applied to a variety of other problems and system models.

References

[1]
R. Alur and G. Taubenfeld. Results about fast mutual exclusion. In Proceedings of the 13th IEEE Real-time Systems Symposium, pages 12--21. IEEE, 1992.
[2]
James H. Anderson and Yong-Jik Kim. An improved lower bound for the time complexity of mutual exclusion. In PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, pages 90--99, New York, NY, USA, 2001. ACM Press.
[3]
James H. Anderson and Yong-Jik Kim. Nonatomic mutual exclusion with local spinning. In PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing, pages 3--12, New York, NY, USA, 2002. ACM Press.
[4]
James H. Anderson, Yong-Jik Kim, and Ted Herman. Shared-memory mutual exclusion: major research trends since 1986. Distributed Computing, 2003.
[5]
Hagit Attiya and Danny Hendler. Time and space lower bounds for implementations using -cas. In DISC, pages 169--183, 2005.
[6]
James E. Burns and Nancy A. Lynch. Bounds on shared memory for mutual exclusion. Information and Compututation, 107(2):171--184, 1993.
[7]
Robert Cypher. The communication requirements of mutual exclusion. In SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, pages 147--156, New York, NY, USA, 1995. ACM Press.
[8]
G. Graunke and S. Thakkar. Synchronization algorithms for shared-memory multiprocessors. IEEE Computer, 1990.
[9]
Prasad Jayanti. A time complexity lower bound for randomized implementations of some shared objects. In PODC '98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pages 201--210, New York, NY, USA, 1998. ACM Press.
[10]
Patrick Keane and Mark Moir. A simple local-spin group mutual exclusion algorithm. In PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, pages 23--32, New York, NY, USA, 1999. ACM Press.
[11]
J. Mellor-Crummey and M. Scott. Algorithms for scalable sychronization on shared-memory multicomputers. ACM Transations on Computer Systems, 1991.
[12]
Michael Raynal. Algorithms for Mutual Exclusion. The MIT Press, Cambridge, Massachusetts, 1986.
[13]
Y.-H. Yang and J. Anderson. A fast, scalable mutual exclusion algorithm. Distributed Computing, 1995.

Cited By

View all

Index Terms

  1. An Ω (n log n) lower bound on the cost of mutual exclusion

    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. information theory
    2. lower bound techniques
    3. mutual exclusion
    4. time complexity

    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)3
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Prior WorkRecoverable Mutual Exclusion10.1007/978-3-031-20002-1_3(11-15)Online publication date: 18-Apr-2023
    • (2023)IntroductionRecoverable Mutual Exclusion10.1007/978-3-031-20002-1_1(1-5)Online publication date: 18-Apr-2023
    • (2019)Recoverable mutual exclusionDistributed Computing10.1007/s00446-019-00364-032:6(535-564)Online publication date: 5-Nov-2019
    • (2018)Recoverable Mutual Exclusion Under System-Wide FailuresProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212755(17-26)Online publication date: 23-Jul-2018
    • (2017)Recoverable Mutual Exclusion in Sub-logarithmic TimeProceedings of the ACM Symposium on Principles of Distributed Computing10.1145/3087801.3087819(211-220)Online publication date: 25-Jul-2017
    • (2016)On the Complexity of Reader-Writer LocksProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933099(315-324)Online publication date: 25-Jul-2016
    • (2016)Recoverable Mutual ExclusionProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933087(65-74)Online publication date: 25-Jul-2016
    • (2015)Trading Fences with RMRs and Separating Memory ModelsProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767427(173-182)Online publication date: 21-Jul-2015
    • (2012)Brief announcementProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332479(239-240)Online publication date: 16-Jul-2012
    • (2012)A tight RMR lower bound for randomized mutual exclusionProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214066(983-1002)Online publication date: 19-May-2012
    • Show More Cited By

    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