Synchronization and concurrency measures for distributed computations

Several qualitative measures that quantify the degree of concurrency in a distributed computation are presented. The measures characterize the synchronization constraints inherent in a distributed computation and are independent of the underlying system running the computation. The measures are defined by two well defined abstractions, called cone and cylinder, to which simple measures can be associated: volume, weight, and height. Simple ways to compute the measures are proposed. The mechanism uses two types of vector clocks that trace the history of the computation. It is shown that the measures can be easily incorporated into any system to analyze distributed executions