Partial-order validation for multi-process protocols modeled as communicating finite state machines
Hong Sheng Lin, Raymond E. Miller · 2002
We adapt the partial order state reduction techniques developed for Petri nets and labeled transition systems to the validation of multi-process protocols modeled as communicating finite state machines. We identify two specific partial order reduction methods in this context: (1) maximal partial order reachability analysis, which is a generalization of maximal reachability analysis to protocols with n/spl ges/2 processes; and (2) simultaneous partial order reachability analysis, which is a counterpart of fair reachability analysis for protocols with n/spl ges/2 processes and arbitrary communication topologies. We study the logical error detection capabilities of each method and show that these two methods, when used together, provide complete logical error coverage for bounded multi-process protocols.