What Makes a Concurrent Algorithm Correct?
May 17, 2015
First of all one must ask themselves what makes any algorithm correct? The answer is the algorithm does as it is required by a specification or set of interested properties. For example a specification which states the algorithm will sort as list of unsorted numbers in ascending order, is correct if it does just that.
This brings us onto defining what makes a correct concurrent algorithm. As with any algorithm or computer program, we require that it produces the expected output from the data that is input into the system. Additionally when concurrency is brought into the mix there are two more properties we are concerned with. The first is mutual exclusion of shared resources, in order to prevent the problematic results race conditions can produce. Secondly we want to be sure the algorithm doesn’t result in deadlock or livelock.
To conclude we can say that a concurrent algorithm is correct if it meets the following requirements:
- It is safe – shared resources are suitably protected
- The required result eventually happens – free from deadlock and livelock