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.^[ref] Concurrent correctness can include safety, such as never entering two critical sections together, and progress, such as a waiting activity eventually proceeding under stated scheduling assumptions.