(An) improved protocol validation technique by generating the group perturbation tree

Abstract

The network topology of a communication system is often represented by a directed labeled graph in which there exists one and only one elementary path from one node to any other node. Nodes and arcs in this graph represent the processes in the communication system and the links between the processes, respectively. In this thesis, we propose an algorithm for validation of the protocols in the restricted class of communication systems with such a network topology. For this algorithm, protocols are represented by $N(N\geq 2)$ communicating finite state machines. The algorithm can detect deadlocks and unspecified receptions with savings in computation time and/or storage space in comparison with the conventional perturbation technique.