Dekker's algorithm

Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming where processes only communicate via shared memory. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in an unpublished paper on sequential process descriptions[1] and his manuscript on cooperating sequential processes.[2] It allows two threads to share a single-use resource without conflict, using only shared memory for communication.

It avoids the strict alternation of a naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be invented.

  1. ^ Dijkstra, Edsger W. Over de sequentialiteit van procesbeschrijvingen (EWD-35) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription) (undated, 1962 or 1963); English translation About the sequentiality of process descriptions
  2. ^ Dijkstra, Edsger W. Cooperating sequential processes (EWD-123) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription) (September 1965)