A complexity measure for the specifications of distributed systems.

Abstract

In software engineering, complexity measurement is a quantitative approach to estimating the degree of complication, organization and coding style of a computer program or system specification. Existing complexity metrics are mostly for non-distributed systems. This thesis extends them to distributed systems. It includes three contributions. Firstly, it proposes a Petri net model, called Interacting Petri nets (I-PN), for representing the behavior of distributed systems. This model provides a graph-based representation for LOTOS, which is necessary in order to derive methods for estimating the complexity of LOTOS. Secondly, a metric, called cyclomatic complexity, is proposed for measuring the complexity of I-NPs and LOTOS specifications. Two approaches are proposed for calculating such complexity. In the first approach, a LOTOS expression is first transformed to an I-PN and then Berge's formula in graph theory is applied to determine the cyclomatic complexity of the I-PN and the corresponding LOTOS specification. In the second approach, a set of formulas for calculating the cyclomatic complexity of all the primitive LOTOS operations is derived. Based on them, the complexity of any LOTOS expression can be calculated directly from the expression itself without going through any transformation. Thirdly, as an application of our I-PN model and complexity measure, a path-testing coverage criterion, called basis set coverage, is proposed. As an illustration, the above results are applied to the Transport Protocol (Class 0).