An improved protocol validation technique for a class of communication models (Q1821089)

The topology of a communication network 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, where nodes and arcs in the graph represent the processes in the communication network and the links between the processes, respectively. In this paper, we propose an algorithm for the validation of the protocols, represented by N (N\(\geq 2)\) communicating finite state machines, in the restricted class of the communication networks with such topology. The algorithm can detect deadlocks and unspecified receptions, and saves time and/or storage in comparison with the conventional perturbation technique.