article

Open access

A New Solution to Lamport's Concurrent Programming Problem Using Small Shared Variables

Editor: Susan L. Graham Author:

Gary L. PetersonAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 5, Issue 1

Pages 56 - 65

https://doi.org/10.1145/357195.357199

Published: 01 January 1983 Publication History

PDF eReader

References

[1]

BURNS, J. Complexity of Communication among Asynchronous Parallel Processes. Ph.D. dissertation, Georgia Inst. of Technology, Atlanta, Ga., 1981.

Crossref

Google Scholar

[2]

BURNS, J.E., JACKSON, P., LYNCH, N.A., FISCHER, M.J., AND PETERSON, G.L. Data requirements for implementation of N-process mutual exclusion using a single shared variable. J. ACM 29, 1 (Jan. 1982), 183-205.

Crossref

Google Scholar

[3]

DEBRUIJN, N.G. Additional comments on a problem in concurrent programming control. Corn. rnun. ACM 10, 3 (Mar. 1967), 137-138.

Crossref

Google Scholar

[4]

DIJKSTRA, E.W. Solution of a problem in concurrent programming control. Cornmun. ACM 8, 9 (Sept. 1965), 569.

Crossref

Google Scholar

[5]

EISENSERG, M.A., AND McGmRE, M.R, Further comments on Dijkstra's concurrent programming control problem. Commun. ACM 15, 11 (Nov. 1972), 999.

Crossref

Google Scholar

[6]

KATSEFF, H.P. A new solution to the critical section problem. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, San Diego, Calif., May 1-3, 1978, pp. 86-88.

Crossref

Google Scholar

[7]

KNUTH, D.E. Additional comments on a problem in concurrent programming control. Commun. ACM 9, 5 (May 1966), 321-322.

Crossref

Google Scholar

[8]

LAMPORT, L. The mutual exclusion problem. SRI International, Menlo Park, Calif., Oct. 1980.

Google Scholar

[9]

LAMPORT, L. A new solution of Dijkstra's concurrent programming problem. Commun. ACM 17, 8 (Aug. 1974), 453-455.

Crossref

Google Scholar

[10]

PETERSON, G.L. New bounds on mutual exclusion problems. Tech. Rep. TR68, Computer Science Dep., Univ. of Rochester, Rochester, N.Y., Feb. 1980.

Google Scholar

[11]

PRTERSON, G.L. Concurrency and complexity. Tech. Rep. TR59, Computer Science Dep., Univ. of Rochester, Rochester, N.Y., Aug. 1979.

Google Scholar

[12]

PETERSON, G.L., AND FISCX4ER, M.J. Economical solutions for the critical section problem in a distributed system. In Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, Boulder, Colo., May 2-4, 1977, pp. 91-97.

Crossref

Google Scholar

[13]

RIVEST, R.L., ANO PRATT, V.R. The mutual exclusion problem for unreliable processes: Preliminary report. In Proceedings, 17th Annual Symposium on Foundations of Computer Science, Houston, Tex., 1976, pp. 1-8.

Google Scholar

Cited By

View all

Maurer CMaurer C(2021)LocksNonsequential and Distributed Programming with Go10.1007/978-3-658-29782-4_3(49-96)Online publication date: 20-Jan-2021
https://doi.org/10.1007/978-3-658-29782-4_3
Lamport L(2019)The mutual exclusion problemConcurrency10.1145/3335772.3335938(247-276)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3335772.3335938
Maurer CMaurer C(2019)SchlösserNichtsequentielle und Verteilte Programmierung mit Go10.1007/978-3-658-26290-7_3(51-100)Online publication date: 24-Oct-2019
https://doi.org/10.1007/978-3-658-26290-7_3
Show More Cited By

Index Terms

A New Solution to Lamport's Concurrent Programming Problem Using Small Shared Variables
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
    2. Extra-functional properties
      1. Software fault tolerance

Recommendations

A simple solution to Lamport's concurrent programming problem with linear wait
ICS '88: Proceedings of the 2nd international conference on Supercomputing

A new simple solution to the Lamport's concurrent programming problem is presented. The algorithm uses five distinct values of shared memory per process. The shared values can be stored either in a single variable or in three one-bit Boolean variables ...
Concurrent programming vs. concurrency control: shared events or shared data
Proceedings of the ACM SIGPLAN Workshop on Object-Based Concurrent Programming

Two views of concurrency in an object system exist. Those pursuing concurrent programming believe that activities in the real world are inherently concurrent and therefore objects are themselves active. Objects engage in shared events by sending and ...
Concurrent programming vs. concurrency control: shared events or shared data
OOPSLA/ECOOP '88: Proceedings of the 1988 ACM SIGPLAN workshop on Object-based concurrent programming

Two views of concurrency in an object system exist. Those pursuing concurrent programming believe that activities in the real world are inherently concurrent and therefore objects are themselves active. Objects engage in shared events by sending and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 5, Issue 1

Jan. 1983

125 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/357195

Editor:
Susan L. Graham

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1983

Published in TOPLAS Volume 5, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
852
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)11

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Maurer CMaurer C(2021)LocksNonsequential and Distributed Programming with Go10.1007/978-3-658-29782-4_3(49-96)Online publication date: 20-Jan-2021
https://doi.org/10.1007/978-3-658-29782-4_3
Lamport L(2019)The mutual exclusion problemConcurrency10.1145/3335772.3335938(247-276)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3335772.3335938
Maurer CMaurer C(2019)SchlösserNichtsequentielle und Verteilte Programmierung mit Go10.1007/978-3-658-26290-7_3(51-100)Online publication date: 24-Oct-2019
https://doi.org/10.1007/978-3-658-26290-7_3
Maurer CMaurer C(2018)SchlösserNichtsequentielle und Verteilte Programmierung mit Go10.1007/978-3-658-21153-0_2(35-79)Online publication date: 29-May-2018
https://doi.org/10.1007/978-3-658-21153-0_2
Singla ADesai KPurini SChoppella V(2016)Distributed Safety Verification Using Vertex Centric Programming Model2016 15th International Symposium on Parallel and Distributed Computing (ISPDC)10.1109/ISPDC.2016.23(114-120)Online publication date: 2016
https://doi.org/10.1109/ISPDC.2016.23
Vitányi P(2016)RegistersEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_338(1808-1812)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_338
Aravind AHesselink W(2011)Nonatomic dual bakery algorithm with bounded tokensActa Informatica10.1007/s00236-011-0132-048:2(67-96)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1007/s00236-011-0132-0
Jones CPierce K(2011)Elucidating concurrent algorithms via layers of abstraction and reificationFormal Aspects of Computing10.1007/s00165-010-0156-123:3(289-306)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1007/s00165-010-0156-1
Kluge FYu CMische JUhrig SUngerer T(2009)Implementing AUTOSAR scheduling and resource management on an embedded SMT processorProceedings of th 12th International Workshop on Software and Compilers for Embedded Systems10.1145/1543820.1543828(33-42)Online publication date: 23-Apr-2009
https://dl.acm.org/doi/10.1145/1543820.1543828
Vitányi P(2008)RegistersEncyclopedia of Algorithms10.1007/978-0-387-30162-4_338(761-764)Online publication date: 2008
https://doi.org/10.1007/978-0-387-30162-4_338
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

A simple solution to Lamport's concurrent programming problem with linear wait

Concurrent programming vs. concurrency control: shared events or shared data

Concurrent programming vs. concurrency control: shared events or shared data

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations