= Concurrent algorithm
A <concurrent algorithm> coordinates activities whose execution steps can overlap in time or be interleaved. Correctness must cover the allowed <thread interleavings>, including executions in which one activity pauses while another continues. Merely testing one convenient schedule does not establish the required property.
Suppose two activities increment a shared counter initially zero by separately reading, adding one and writing. Both can read zero before either writes, so the final value is one rather than two. An <atomic read-modify-write> can make each increment indivisible; <mutual exclusion> can instead protect a larger <critical section>. The appropriate choice depends on which shared-state invariant must survive each permitted execution step.
<Leslie Lamport>'s <Lamport's bakery algorithm> illustrates the distinction between a coordination rule and assumptions about hardware. Its <mutual exclusion> argument orders ticket/process-number pairs, and the original proof explicitly treats reads overlapping writes rather than silently assuming every shared-memory access behaves atomically.<A New Solution of Dijkstra's Concurrent Programming Problem by Leslie Lamport>[Printed pp.453–454, algorithm and correctness assertions]{ref} Concurrent correctness can include <safety property>[safety], such as never entering two <critical sections> together, and <liveness property>[progress], such as a waiting activity eventually proceeding under stated <process scheduling>[scheduling] assumptions.
Back to article page
