Traditional centralized network management solutions do not scale to present-day large-scale computer/communication networks. Decentralization/distributed solutions can solve some of these problems (Goldszmidt, G. and Yemini, Y., 1995), and thus there is considerable interest in distributed/decentralized network management applications. We present the design and evaluation of an SNMP-based distributed network fault detection/monitoring system. We integrate into the SNMP framework our ML-ADSD algorithm (Su, M.-S. et al., Proc. 39th Annual Allerton Conf. on Commun., Control, and Computers, 2001; Su, "Multilevel distributed diagnosis and the design of a distributed network fault detection system based on the SNMP protocol", Ph.D. Thesis, School of Computer Science, University of Oklahoma, 2002) for fault diagnosis in a distributed processor system. The algorithm uses the multilevel paradigm and requires only minor modifications to be scalable to networks of varying sizes. The system is fault tolerant, allowing processor failure and/or recovery during the diagnosis process. We have implemented the system on an Ethernet network of 32 machines. Our results show that the diagnosis latency (or time to termination) is much better than that of earlier solutions. Also, the system's bandwidth utilization is insignificant, demonstrating the practicality of its deployment in a real network. We have successfully integrated three modern disciplines: network management, distributed computing and system level diagnosis.

The minimum length test sequence generation method proposed previously (1988) for conformance testing of a protocol uses Unique Input Sequences (UIS) for state identification. This method, called the U-method, requires that the test graph, a graph derived from the protocol, be connected. This requirement also needs to be satisfied in the case of the MU-method, which assumes that the multiple UISs are available for each state. Thus, the U-method and the MU-method may not provide minimum length test sequences in cases where the test graph is not connected. Nevertheless, these methods generate minimum length test sequences with high fault coverage whenever the test graph is connected. This raises an important problem: Does there exist an assignment of UISs to the transitions such that the resulting test graph is connected? In this paper, we formulate this problem as a maximum cardinality two matroid intersection problem and discuss an efficient algorithmic solution. We also point out the role of the work in the minimum length test sequence generation problem.

A number of test sequence generation methods proposed for protocols represented as extended finite state machines (EFSMs) use state identification sequences for checking the states. However, neither a formal definition nor a method of computation of these sequences for an EFSM state is known. We define a new type of state identification sequence, called context independent unique sequence (CIUS) and present an algorithm for computing it. A unified method based on CIUSes is developed for automatically generating executable test cases for both control flow and data flow aspects of an EFSM. In control flow testing, CIUSes are very useful in confirming the tail state of the transitions. In data flow testing, CIUSes improve the observability of the test cases for the def-use associations of different variables used in the EFSM. Unlike general state identification sequences, the use of CIUSes does not increase the complexity of the already intractable feasibility problem in the test case generation.

A classic PMC (Preparata, Metze, and Chien) multiprocessor system [F. P Preparata, G. Metze, and R. T. Chien, IEEE Trans. Electr. Comput., EC-16 (1967), pp. 848–854] composed of n units is said to be ${t / {(t + 1)}}$ diagnosable [A. D. Friedman, A new measure of digital system diagnosis, in Dig. 1975 Int. Symp. Fault-Tolerant Comput., 1975, pp. 167–170] if, given a syndrome (complete collection of test results), the set of faulty units can be isolated to within a set of at most $t + 1$ units, assuming that at most t units in the system are faulty. This paper presents a methodology for determining when a unit $\upsilon $ can belong to an allowable fault set of cardinality at most t. Based on this methodology, for a given syndrome in a ${t / {(t + 1)}}$-diagnosable system, the authors establish a necessary and sufficient condition for a vertex v to belong to an allowable fault set of cardinality at most t and certain properties of ${t / {(t + 1)}}$-diagnosable systems. This condition leads to an ${{O(n^{3.5} )t} / {(t + 1)}}$-diagnosis algorithm. This ${t / {(t + 1)}}$-diagnosis algorithm complements the ${t / {(t + 1)}}$-diagnosability algorithm of Sullivan [The complexity of system-level fault diagnosis and diagnosability, Ph.D. thesis, Yale University, New Haven, CT, 1986].

The signal save construct is one of the features distinguishing SDL from traditional high-level specification and programming languages. However, this feature increases the difficulties of testing SDL-specified software. We present a testing approach consisting of the following three phases: SDL specifications are first abstracted into finite state machines with save constructs, called SDL-machines; the resulting SDL-machines are then transformed into equivalent finite state machines without save constructs if this is possible; and, finally, test cases are selected from the resulting finite state machines. Since there are many existing methods for the first and third phases, we mainly concentrate upon the second phase and come up with a method of transforming SDL-machines into equivalent finite state machines, which preserve the same input/output relationship as in the original SDL-machines. The transformation method is useful not only for testing but also for verifying SDL-specified software.>

A model and a formal specification of the personal communication service obtained by the application of an object-oriented system design methodology is presented and described using the executable object-oriented specification language Mondel. The goal of developing a specification of PCS is primarily to introduce some structure and formalism in its description, which has so far been done informally, and also to provide a better understanding of its constituent elements and their interrelationships. As Mondel is an executable specification language, simulation is used to verify the basic functionality defined in this specification of PCs. Simulation using various scenarios also provides a means of presenting the different concepts of PCS.>

The authors study the fault diagnosis of multiprocessor systems when fault constraints in the local domain of each processor are specified. They use the comparison-based model. A multiprocessor system S is t-in-L diagnosable if, given a syndrome, all faulty processors can be uniquely identified provided there are at most t faulty processors in the local domain L(u/sub i/) union (u/sub i/) of every processor, u/sub i/ in S, where L (u/sub i/) denotes the set of processors adjacent to u/sub i/. Certain basic results that lead to efficient conditions for unique diagnosis of a system when certain fault constraints are satisfied in the local domain of each processor in the system are presented. The t-in-L diagnosability of certain regular interconnected systems is examined under the assumption that less than half of the processors in the system are faulty. Diagnosis algorithms for these systems are presented.>