Article

Free access

The communication requirements of mutual exclusion

Author:

Robert CypherAuthors Info & Claims

SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures

Pages 147 - 156

https://doi.org/10.1145/215399.215434

Published: 20 July 1995 Publication History

PDF eReader

References

[1]

A. Agarwal, R. Simoni, J. Hennessy, and M. Horowitz, "An Evaluation of Directory Schemes for Cache Coherence", in Proc. 15th Intl. Syrup. on Computer Architecture, pp. 280-289, 1988.

Digital Library

Google Scholar

[2]

T.E. Anderson, "The Performance of Spin Lock Alternatives for Shared Memory Multiprocessors", IEEE Trans. on Parallel and D,stributed Systems, vol. 1, no. 1, pp. 6-16, 1990.

Digital Library

Google Scholar

[3]

H. Attiya and R. Friedman, "Programming DEC-Alpha Based Multiprocessors the Easy Way", in Proc. A CM Syrup. on Parallel Algorithms and Architectures, pp. 157-166, 1994.

Digital Library

Google Scholar

[4]

D. Chaiken, J. Kubiatowicz, and A. Agarwal, "LimitLESS Directories: A Scalable Cache Coherence Scheme", in Proc. gth Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 224-234, 1991.

Digital Library

Google Scholar

[5]

G. Chartrand and L. Lesniak, Graphs # Digraphs, Wadsworth & Brooks/Cole Advanced Books 8z Software, Monterey, CA, second edition, 1986.

Digital Library

Google Scholar

[6]

T.S. Craig, "Queuing Spin Lock Algorithms to Support Timing Predictability", in Proc. Real-Time Systems Syrup., pp. 148-157, 1993.

Google Scholar

[7]

T.S. Craig, "Building FIFO and Priority-Queuing Spin Locks from Atomic Swap", Tech. Rep. 93-02-02, Dept. of Comp. Sci. and Eng., U. of Washington. 1993.

Google Scholar

[8]

(",ray Research Inc., "SHMEM Technical Note for C", Tech. Rep., Cray Research Inc., Eagan, MN, October 25, 1994.

Google Scholar

[9]

Digital Equipment Corporation, The Alpha Architecture Handbook, 1992.

Google Scholar

[10]

E.W. Dijkstra, "Solution of a Problem in Concurrent Programming Control", Communications of the ACM, vol. 8, no. 9, p. 569, 1965.

Digital Library

Google Scholar

[11]

M. Dubois, C. Scheurich, and F.A. Briggs, "Synchronization, Coherence, and Event Ordering in Multiprocessor#", IEEE Computer, pp. 9-21, Feb. 1988.

Digital Library

Google Scholar

[12]

J.R. Goodman, M.K. Vernon, and P.J. Woest, "Efficient Synchronization Primitives for Large-Scale Cache- Coherent Multiprocessors", in Proc. Intl. Conj. on Architectural Support for Programming Languages and Operating Systems, pp. 64-75, 1989.

Digital Library

Google Scholar

[13]

A. Gottfieb, R. Grishman, C.P. Kruskal, K.P. McAuliffe, L. Rudolph, and M. Snir, "The NYU Ultracomputer - Designing an MIMD, Shared Memory Parallel Machine", IEEE Trans. on Computers, vol. 32, pp. 175-189, 1983.

Digital Library

Google Scholar

[14]

International Business Machines Corp., PowerPC Architecture (First Edzt, on), May 1993.

Google Scholar

[15]

D.E. Knuth, "Additional Comments on a Problem in Concurrent Programming Control", Communications of the ACM, vol. 9, no. 5, pp. 321-322, 1966.

Digital Library

Google Scholar

[16]

C.P. Kruskal, L. Rudolph, and M. Snir, "Efficient Synchronization on Multiprocessors with Shared Memory", in Proc. A CM Syrup. on Principles of Distributed Computing, pp. 218-228, 1986.

Digital Library

Google Scholar

[17]

D. Lenoski, J. Laudon, K. Gharachorloo, A. Gupta, and J. tlennessy, "The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor", in Proc. Intl. Syrup. on Computer Architecture, pp. 148-159, 1990.

Digital Library

Google Scholar

[18]

J.M. Mellor-Crummey and M.L. Scott, "Algorithms for Scalable Synchronization on Shared Memory Multiprocessors', A CM Trans. on Computer Systems, vol. 9, no. 1, pp. 21-65, 1991.

Digital Library

Google Scholar

[19]

M. Merritt and G. Taubenfeld, "Knowledge in Shared Memory Systems", in Proc. ACM Syrup. on Principle5 o} Distmbuted Computing, pp. 189-200, 1991.

Digital Library

Google Scholar

[20]

G. Pfister and V.A. Norton, "Hot Spot Contention and Combining in Multistage Interconnection Networks", IEEE Trans. on Computers, vol. 34, no. 10, pp. 943- 948, 1985.

Crossref

Google Scholar

[21]

M. Raynal, Algorithms }or Mutual Exclusion, MIT Press, Cambridge, MA, 1986.

Digital Library

Google Scholar

[22]

A. Segall and L. Rudolph, "Dynamic Decentralized Cache Schemes for an MIMD Parallel Processor", in Proc. Intl. Symp. on Computer Architecture, pp. 340- 347, 1984.

Digital Library

Google Scholar

[23]

J-H. Yang and J.H. Anderson, "Fast, Scalable Synchronization with Minimal Hardware Support", in Proc. ACM Syrup. on Principles of Distributed Computing, pp. 171-182, 1993.

Digital Library

Google Scholar

[24]

J-H. Yang and J.H. Anderson, "Time Bounds for Mutual Exclusion and Related Problems", in Proc. A CM Syrup. on Theory o} Computing, pp. 224-233, 1994.

Digital Library

Google Scholar

[25]

P-C. Yew, N-F. Tzeng, and D.tt. Lawrie, "Distributing Hot-Spot Addressing in Large-Scale Multiprocessors", IEEE Trans. on Computers, vol. 36, no. 4, pp. 388-395, 1987.

Digital Library

Google Scholar

Cited By

View all

Dhoked SGolab WMittal NDhoked SGolab WMittal N(2023)Prior WorkRecoverable Mutual Exclusion10.1007/978-3-031-20002-1_3(11-15)Online publication date: 18-Apr-2023
https://doi.org/10.1007/978-3-031-20002-1_3
Dhoked SGolab WMittal NDhoked SGolab WMittal N(2023)IntroductionRecoverable Mutual Exclusion10.1007/978-3-031-20002-1_1(1-5)Online publication date: 18-Apr-2023
https://doi.org/10.1007/978-3-031-20002-1_1
Jayanti PJayanti S(2021)Deterministic Constant-Amortized-RMR Abortable Mutex for CC and DSMACM Transactions on Parallel Computing10.1145/34905598:4(1-26)Online publication date: 9-Dec-2021
https://dl.acm.org/doi/10.1145/3490559
Show More Cited By

Index Terms

The communication requirements of mutual exclusion

Recommendations

Fair group mutual exclusion
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

In the group mutual exclusion problem [6], which generalizes mutual exclusion [2], a process chooses a session when it requests entry to the Critical Section. A group mutual exclusion algorithm must ensure that the mutual exclusion property holds: If ...
Space-efficient FCFS group mutual exclusion

In the group mutual exclusion problem [Y. Joung, Asynchronous group mutual exclusion, Distrib. Comput. 13 (2000) 189], which generalizes mutual exclusion [E. Dijkstra, Solution of a problem in concurrent programming control, Comm. ACM 8 (9) (1965) 569], ...
A note on group mutual exclusion
PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing

Group mutual exclusion is a natural problem, formulated by Joung in 1998, that generalises the classical mutual exclusion problem. In group mutual exclusion a process requests a “session” before entering its critical section; processes are allowed to be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures

July 1995

320 pages

ISBN:0897917170

DOI:10.1145/215399

Chairman:
Charles E. Leiserson
Massachussets Institute of Technology, Cambridge

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: 20 July 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

7SPAA95

Sponsor:

European Theoretical
IEEE
SIGACT
SIGARCH

7SPAA95: 7th Annual ACM Symposium on Parallel Algorithms and Architectures

June 24 - 26, 1995

California, Santa Barbara, USA

Acceptance Rates

SPAA '95 Paper Acceptance Rate 31 of 101 submissions, 31%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
508
Total Downloads

Downloads (Last 12 months)87
Downloads (Last 6 weeks)13

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dhoked SGolab WMittal NDhoked SGolab WMittal N(2023)Prior WorkRecoverable Mutual Exclusion10.1007/978-3-031-20002-1_3(11-15)Online publication date: 18-Apr-2023
https://doi.org/10.1007/978-3-031-20002-1_3
Dhoked SGolab WMittal NDhoked SGolab WMittal N(2023)IntroductionRecoverable Mutual Exclusion10.1007/978-3-031-20002-1_1(1-5)Online publication date: 18-Apr-2023
https://doi.org/10.1007/978-3-031-20002-1_1
Jayanti PJayanti S(2021)Deterministic Constant-Amortized-RMR Abortable Mutex for CC and DSMACM Transactions on Parallel Computing10.1145/34905598:4(1-26)Online publication date: 9-Dec-2021
https://dl.acm.org/doi/10.1145/3490559
Jayanti PJayanti SJayanti S(2020)Towards an Ideal Queue LockProceedings of the 21st International Conference on Distributed Computing and Networking10.1145/3369740.3369784(1-10)Online publication date: 4-Jan-2020
https://dl.acm.org/doi/10.1145/3369740.3369784
Jayanti PJayanti SRobinson PEllen F(2019)Constant Amortized RMR Abortable Mutex for CC and DSMProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331592(167-176)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331592
Golab WRamaraju A(2019)Recoverable mutual exclusionDistributed Computing10.1007/s00446-019-00364-032:6(535-564)Online publication date: 5-Nov-2019
https://doi.org/10.1007/s00446-019-00364-0
Golab WHendler DNewport CKeidar I(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
https://dl.acm.org/doi/10.1145/3212734.3212755
Acar UBen-David NRainey M(2017)Contention in Structured ConcurrencyACM SIGPLAN Notices10.1145/3155284.301876252:8(75-88)Online publication date: 26-Jan-2017
https://dl.acm.org/doi/10.1145/3155284.3018762
Karanikolas CDimitroulakos GMasselos K(2017)Early Evaluation of Implementation Alternatives of Composite Data Structures Toward MaintainabilityACM Transactions on Software Engineering and Methodology10.1145/313273126:2(1-44)Online publication date: 5-Oct-2017
https://dl.acm.org/doi/10.1145/3132731
Golab WHendler DSchiller ESchwarzmann A(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
https://dl.acm.org/doi/10.1145/3087801.3087819
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

Fair group mutual exclusion

Space-efficient FCFS group mutual exclusion

A note on group mutual exclusion