ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Tight bounds for shared memory symmetric mutual exclusion problems
Full text PdfPdf (1.74 MB)
Source Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the eighth annual ACM Symposium on Principles of distributed computing table of contents
Edmonton, Alberta, Canada
Pages: 177 - 191  
Year of Publication: 1989
ISBN:0-89791-326-4
Authors
E. Styer  School of Information and Computer Science, Georgia Institute of Technology, Atlanta, Ga
G. L. Peterson  School of Information and Computer Science, Georgia Institute of Technology, Atlanta, Ga
Sponsors
SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 12,   Citation Count: 5
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/72981.72993
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
Hagit Attiya, Amotz Bar-Noy, Danny Dolev, Daphne Koller, David Peleg, and Rfidiger Reischuk. Acheivable cases in an asychronous enviroment. in ~8~h Annual Syrup. on Found. o} Comp. Sci., pages 337-345, IEEE, 1987.
2
Hagit Attiya , Marc Snir , Manfred K. Warmuth, Computing on an anonymous ring, Journal of the ACM (JACM), v.35 n.4, p.845-875, Oct. 1988  [doi>10.1145/48014.48247]
 
3
James E. Burns and Nancy A. Lynch. Mutual exclusion using indivisible reads and writes. In 18th Annual Aller~on Conf. on Communicalion, Control, aud Computing, pages 833-842, 1980.
 
4
James E. Burns. Symmetry in systems of asynchronous processes. In 22rid FOCS, pages 169-174, IEEE, 1981.
5
James E. Burns , Paul Jackson , Nancy A. Lynch , Michael J. Fischer , Gary L. Peterson, Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable, Journal of the ACM (JACM), v.29 n.1, p.183-205, Jan. 1982  [doi>10.1145/322290.322302]
6
Ralph E. Johnson , Fred B. Schneider, Symmetry and similarity in distributed systems, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.13-22, August 1985, Minaki, Ontario, Canada  [doi>10.1145/323596.323598]
7
Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987  [doi>10.1145/7351.7352]
8
Gary L. Peterson, A New Solution to Lamport's Concurrent Programming Problem Using Small Shared Variables, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.56-65, Jan. 1983  [doi>10.1145/357195.357199]
9
Eugene W. Stark, Semaphore primitives and starvation-free mutual exclusion, Journal of the ACM (JACM), v.29 n.4, p.1049-1072, Oct. 1982  [doi>10.1145/322344.322352]

CITED BY  5
M. Herlihy , Mark R. Tuttle, Lower bounds for wait-free computation in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.347-362, August 22-24, 1990, Quebec City, Quebec, Canada
Hagit Attiya , Alla Gorbach , Shlomo Moran, Computing in totally anonymous asynchronous shared memory systems, Information and Computation, v.173 n.2, p.162-183, March 15, 2002
James H. Anderson , Yong-Jik Kim, Nonatomic mutual exclusion with local spinning, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
James H. Anderson , Yong-Jik Kim, An improved lower bound for the time complexity of mutual exclusion, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.90-99, August 2001, Newport, Rhode Island, United States
James H. Anderson , Yong-Jik Kim, An improved lower bound for the time complexity of mutual exclusion, Distributed Computing, v.15 n.4, p.221-253, December 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling


General Terms:
Algorithms, Design, Performance, Theory

Collaborative Colleagues:
E. Styer: colleagues
G. L. Peterson: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player