A Component-Based Approach to Verification of Formal Software Models to Check Safety Properties of Distributed Systems

In this paper, we model a distributed system consisting of n processes by a respective set of n Communicating Finite State Machines (CFSMs). The processes run concurrently and communicate with each other to accomplish a common goal. As opposed to the traditional product automaton built from the specified CFSMs, whose state-space explodes, we build a compressed model of what are defined as Communicating Minimal Prefix Machines (CMPMs) by simulating the CFSMs concurrently in parallel. The states of CMPMs form a well-founded, partial order. This model can be used to perform reachability analysis of the given system to check the safety properties such as communication deadlocks. The algorithm to generate the CMPMs model from CFSMs is presented in pseudo-code and its complexity discussed