Solution of a Problem in Concurrent Programming Control.

Dijkstra, E. W. (1965). Solution of a Problem in Concurrent Programming Control. Communications of the ACM, 8(9), 569-570.

Type

Journal article

Intellectual base

Primary research

Year

1965

DOI

10.1145/365559.365617

Link

https://doi.org/10.1145/365559.365617

Cited from

computer_science

Cited by

4 citations across 4 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Concurrency
  • Explicit or implicit synchronization and coordination mechanisms

    This sourceFormalizes the mutual-exclusion problem and gives the first software solution using only atomic reads/writes. SUPPORTS marker 047 (explicit/implicit synchronization and coordination mechanisms). DOI verified. concurrent programming control." Communications of the ACM, 8(9), 569–570. [^herlihy-wing-1990]: Herlihy, M. P., & Wing, J. M. (1990). "Linearizability: a correctness condition for concurrent objects." ACM Transactions on Programming Languages and Systems, 12(3), 463–492. [^brewer-2000]: Brewer, E. A. (2000). Towards Robust Distributed Systems. Keynote, ACM Symposium on Principles of Distributed Computing. Formalization of CAP theorem (Consistency, Availability, Partition tolerance); showed that distributed systems cannot simultaneously guarantee all three. CAP theorem formal constraint on distributed systems.

• Interference and Contention
  • Interference and contention is the structural phenomenon whereby multiple simultaneous demands or processes compete for access to a single limited resource, pathway, or facility, causing mutual interference and degraded throughput or quality for all competing processes, a pattern Dijkstra (1965) formalized in his foundational treatment of mutual exclusion among cooperating sequential processes.
• Mutual Exclusion
  • The failure of any one of these names a recognizable family of bugs — races (a safety failure), deadlock (a liveness failure, a cycle of mutual waits), livelock (both parties back off forever), starvation (a fairness failure) — and naming the property that has broken is the first step to the fix.

    This sourceOriginal statement of the mutual-exclusion problem and a software solution guaranteeing at-most-one process in the critical section.

• Starvation
  • Concurrency and operating systems — the origin: a low-priority thread that never gets the processor because higher-priority threads are always ready; a writer waiting on a lock that never sees zero readers.

    This sourceFoundational concurrency work framing mutual exclusion and the liveness requirement that no eligible process is indefinitely denied progress (starvation).

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:edac2aa25017 · see in the full table