SYNCHRONIZABLE TEST SEQUENCE FOR MULTI-PARTY PROTOCOL CONFORMANCE TESTING

The finite state machine （FSM） model is commonly used for specifying communication protocols and other types of distributed systems. For an FSM with multiple ports, multiple testers are needed. Testing whether a multi party protocol implementation conforms to the specification can be achieved by a testing system with K testers （where K ≥2）, among which synchronization problems are encountered. A synchronizble test sequence of an FSM is a test sequence for which the synchroniztion problem does not exist. Now external synchronization operations are added to test sequence to solve this problem. For each type of testing, a necessary and sufficient condition is defined, under which a test sequence of an FSM is synchronizable. In this paper a new model—synchroniable digraph is proposed, which can judge whether there exist any synchronizable test sequence for a given specification without synchronization operation, and which can transform its nonsynchronizable test sequence to synchronizable test sequence if the answer is true. A method to judge how to add external synchronization operations in a nonsynchronizable test sequence to change it to synchroniable one is also proposed.