Edsger W. Dijkstra

Record year1960

summaryDeveloped formal expressions and reasoning tools for semaphores, mutual exclusion, and deadlock problems. EWD 554 uses ghost variables, shared variables, and critical sections to demonstrate a mutual-exclusion proof and compares Dekker’s scheme; operating-system implementation, parallel formal methods, and pedagogical transmission were jointly advanced by other teams and researchers.

M rationaleConcurrency control is a basic coordination problem of computing systems; organizing mutual exclusion, semaphores, and deadlock as general primitives and problem frameworks that can be designed and proved has broad system-level reuse, so take M6.2.

attribution rationaleDijkstra 0.45; Dekker and prior work in concurrency research 0.15; operating-system implementation team 0.15; parallel formal methods 0.15; adoption, education, and unknown 0.05 each. The original mixed pool of parallel and successor researchers has not yet been allocated to named individuals; unknown inputs are retained.

overlap boundaryProgram primitives and formal reasoning methods for semaphores, mutual exclusion, and deadlock problems in the 1960s. The mutual-exclusion proof in EWD554 belongs to the same concurrency-method family; Dekker, Gries–Owicki, Hoare, and subsequent distributed/self-stabilizing theory are retained.

Evidence gapsThe original P/V definitions, the 1965 article, and implementation of the first operating system still require calibration, affecting a and confidence in scope.

Record year1968

summaryAdvocated addressing complexity through program structure and provable correctness. EWD 249 treats program understanding and correctness proof as core problems; other manuscripts discuss concurrent programs and formal conditions for valid proofs; work by Dahl, Hoare, Gries, Owicki, and others belongs to parallel or subsequent methodological development.

M rationaleThis method places comprehensibility and provable correctness in the process of program construction, forming a design discipline transferable across languages and systems; take M6.0. M reflects methodological coverage and foundational role; not reading every original work enters only the attribution gap for details.

attribution rationaleDijkstra 0.42; Dahl/Hoare 0.18; prior traditions of logic and language 0.15; Gries/Owicki and other concurrent or later researchers 0.12; programmers, educators, and tool implementation 0.08; unknown 0.05. The original mixed pool of parallel and successor researchers has not yet been allocated to named individuals; unknown inputs are retained.

overlap boundaryA long method family from EWD249 structured programming to organizing program design with invariants, specifications, and proofs. Structured programming and program correctness share the same goal and toolchain and are valued together; it does not add separately by manuscript count, goto articles, guarded commands, or weakest-precondition terms, nor claim all software engineering.

Evidence gapsPriority for details such as guarded commands and weakest precondition, and the scope of industrial adoption, require calibration.

Record year1956

summaryProposed the nonnegative-weighted-graph algorithm usually called Dijkstra’s shortest-path algorithm. Existing archives place it among foundational work in algorithm design; the prior tradition of graph theory and optimization, early computer implementation, and subsequent textbook and system adoption each constitute distinct contributions.

M rationaleThe algorithm reduces a broad class of network-optimization problems to clear, repeatable general steps and is reused across fields; take M5.5 for a general foundational algorithmic method. The lack of the original publication affects only confidence and exact conditions, and does not directly lower M.

attribution rationaleDijkstra 0.55; graph-theory and optimization prior tradition 0.20; early implementation colleagues 0.10; textbook and system adoption 0.10; unknown 0.05.

overlap boundaryA shortest-path selection method for nonnegative weighted graphs around 1956 to 1959. Counts only the abstract algorithm and its general reusability; subsequent priority-queue implementations, routing systems, map services, and all route-planning applications are excluded.

Evidence gapsThe 1959 article is needed to confirm conditions, expression, and the early implementation division of work; this gap is not an M discount.

Record year1973

summaryUnder stipulated ring-system and scheduling conditions, local decisions can make a system recover from any initial state and retain lawful synchronization.

M rationaleMakes recovery from any initial state a constructible and arguable distributed problem; take M5.2. The scope is a new conditional method, while actual industrial deployment has other actors.

attribution rationaleIndividual and shared inputs are revisable research budgets, allocated according to original-work authorship, team accounts, and specific system dependencies; shares are not inferred backward from citation counts or later market scale.

overlap boundaryConstruction and argument for convergence from any initial state to a lawful synchronized state; counts only the method’s existence for a ring finite-state system and stated conditions such as fair scheduling. It adds a post-failure recovery problem distinct from mutual-exclusion primitives that maintain an initially lawful state; it does not claim all later fault-tolerant systems.

Evidence gapsThe original conditions and conclusion have been read, but the entire proof has not been checked by program enumeration; the original text did not claim delivery of industrial fault-tolerant services.

Record year1968

summaryImplemented and tested memory, processor, and input/output in layers, with explicit layer interfaces; testing was still incomplete when reported.

M rationaleOn the specific EL X8, carried layered abstraction into system construction and testing; take M4.3. The bounded system integration by a six-person team differs from a general method and is not a complete commercial operating system or long-term service.

attribution rationaleIndividual and shared inputs are revisable research budgets, allocated according to original-work authorship, team accounts, and specific system dependencies; shares are not inferred backward from citation counts or later market scale.

overlap boundaryCounts only the engineering delivery described in the 1968 report, in which layered software had been programmed and tested by layer; testing was still incomplete at the time of the report. Primitives and general correctness methods are already accounted for in two existing families; this item claims only the residual of interface integration and actual testing for memory, processor, input/output, and so forth, and does not treat planned university service as already long-running.

Evidence gapsThe original report confirms that testing was unfinished at the time of writing and does not prepay long-term operational results; the six members’ internal work items have not been decomposed, so a team budget is retained.