Synchronization paradigm for protocol testing under multiparty configuration

Abstract

Protocol testing leads to the synchronization problem should test sequences be applied to multiple distanced testers, namely under the multiparty configuration. This paper presents a novel synchronization paradigm which seamlessly unifies two synchronization techniques, self-synchroniable sequences and external synchronization operations, by means of the state expansion transformation. In the paradigm, the protocol specification is first transformed into a state expansion digraph with two pieces of datum augmented. They are: (a) a zero cost assigned to each synchronization-problem-free crossing from one transition to another transition, and (b) a weighted cost assigned to each external synchronization operation whenever the synchronization is deemed necessary. On the basis of the state expansion transformation, synchronizable, optimal sequences for testing can be efficiently derived. To demonstrate the viability of the proposed paradigm, we present the generations of two synchronizable sequences, namely the synchronizable preamble and the synchronizable distinguishing sequence, which have previously been used for the testing of the correctness of a protocol's transition. The paper also shows that the complexities of the two sequences generations are also polynomial-bounded, i.e., O((np(2))log(np)) and O((n(2)p(2)) log(np)), respectively, where n and p are the numbers of states and input symbols of the protocol specification. (C) 1999 Elsevier Science Ltd. All rights reserved.