Concurrent algorithm

An example of a sequential algorithm not working correctly concurrently: two nodes, i and i+1, being removed simultaneously result in node i+1 not being removed

In computer science, a concurrent algorithm is one that can be executed concurrently. Most standard computer algorithms are sequential algorithms, and assume that the algorithm is run from start to finish without any other processes executing. These often do not behave correctly when run concurrently, as demonstrated at right, and are often nondeterministic, as the actual sequence of computations is determined by the external scheduler. Concurrency often adds significant complexity to an algorithm, requiring concurrency control such as mutual exclusion to avoid problems such as race conditions.

Many parallel algorithms are run concurrently, particularly distributed algorithms, though these are distinct concepts in general.

References