A More Precise Implementation Relation for Distributed Testing
Robert M. Hierons · The Computer Journal · 2015
There has been significant interest in distributed testing from an input–output transition system. Previous work introduced an implementation relation $\\bf{dioco}$ that was defined in terms of an equivalence relation on traces (sequences of observations). This paper considers an alternative approach in which an observation made in testing is a tuple of local traces, one for each tester. This paper defines such an implementation relation $\\bf{dioco}_{o}$ in terms of the possible observations regarding the system under test and the specification. It shows that $\\bf{dioco}_{o}$ is strictly weaker than $\\bf{dioco}$ but is equivalent to $\\bf{dioco}$ if processes cannot be output-divergent. Interestingly, this shows that the previous definition of $\\bf{dioco}$ is too strong for output-divergent processes. We also prove that the Oracle problem is NP-complete but can be solved in polynomial time if there is an upper bound on the number of local testers.