Analysis of Concurrent Algorithms

Abstract

Analyzing the running time of a concurrent algorithm can be as important as verifying its partial correctness or termination. A simple technique for analyzing the running time of a concurrent algorithm is presented. To analyze an algorithm with concurrent processes, the interaction between the processes must be considered. This is done by using the communication sequences of the processes as the basis of the analysis. The technique is used for analyzing and comparing three concurrent algorithms for finding the root of a real function.