Staff shortages and an increasingly aging population are straining the ability of emergency departments to provide high quality care. At the same time, there is a growing concern about hospitals' ability to provide effective care during disaster events. For these reasons, tools that automate patient monitoring have the potential to greatly improve efficiency and quality of health care. Towards this goal, we have developed MEDiSN , a wireless sensor network for monitoring patients' physiological data in hospitals and during disaster events. MEDiSN comprises Physiological Monitors (PMs), which are custom-built, patient-worn motes that sample, encrypt, and sign physiological data and Relay Points (RPs) that self-organize into a multi-hop wireless backbone for carrying physiological data. Moreover, MEDiSN includes a back-end server that persistently stores medical data and presents them to authenticated GUI clients. The combination of MEDiSN's two-tier architecture and optimized rate control protocols allows it to address the compound challenge of reliably delivering large volumes of data while meeting the application's QoS requirements. Results from extensive simulations, testbed experiments, and multiple pilot hospital deployments show that MEDiSN can scale from tens to at least five hundred PMs, effectively protect application packets from congestive and corruptive losses, and deliver medically actionable data.

Although Voice over IP (VoIP) is rapidly being adopted, its security implications are not yet fully understood. Since VoIP calls may traverse untrusted networks, packets should be encrypted to ensure confidentiality. However, we show that it is possible toidentify the phrases spoken within encrypted VoIP callswhen the audio is encoded using variable bit rate codecs. To do so, we train a hidden Markov model using only knowledge of the phonetic pronunciations of words, such as those provided by a dictionary, and search packet sequences for instances of specified phrases. Our approach does not require examples of the speaker’s voice, or even example recordings of the words that make up the target phrase. We evaluate our techniques on a standard speech recognition corpus containing over 2,000 phonetically rich phrases spoken by 630 distinct speakers from across the continental United States. Our results indicate that we can identify phrases within encrypted calls with an average accuracy of 50%, and with accuracy greater than 90% for some phrases. Clearly, such an attack calls into question the efficacy of current VoIP encryption standards. In addition, we examine the impact of various features of the underlying audio on our performance and discuss methods for mitigation.

Despite the rapid adoption of Voice over IP (VoIP), its security implications are not yet fully understood. Since VoIP calls may traverse untrusted networks, packets should be encrypted to ensure confidentiality. However, we show that when the audio is encoded using variable bit rate codecs, the lengths of encrypted VoIP packets can be used to identify the phrases spoken within a call. Our results indicate that a passive observer can identify phrases from a standard speech corpus within encrypted calls with an average accuracy of 50%, and with accuracy greater than 90% for some phrases. Clearly, such an attack calls into question the efficacy of current VoIP encryption standards. In addition, we examine the impact of various features of the underlying audio on our performance and discuss methods for mitigation.

In an effort to make robust traffic classification more accessible to human operators, we present visualization techniques for network traffic. Our techniques are based solely on network information that remains intact after application-layer encryption, and so offer a way to visualize traffic "in the dark". Our visualizations clearly illustrate the differences between common application protocols, both in their transient (i.e., time-dependent)and steady-state behavior. We show how these visualizations can be used to assist a human operator to recognize application protocols in unidentified traffic and to verify the results of an automated classifier via visual inspection. In particular, our preliminary results show that we can visually scan almost 45,000 connections in less than one hour and correctly identify known application behaviors. Moreover, using visualizations together with an automated comparison technique based on Dynamic Time Warping of the motifs, we can rapidly develop accurate recognizers for new or previously unknown applications.

Several fundamental security mechanisms for restricting access to network resources rely on the ability of a reference monitor to inspect the contents of traffic as it traverses the network. However, with the increasing popularity of cryptographic protocols, the traditional means of inspecting packet contents to enforce security policies is no longer a viable approach as message contents are concealed by encryption. In this paper, we investigate the extent to which common application protocols can be identified using only the features that remain intact after encryption---namely packet size, timing, and direction. We first present what we believe to be the first exploratory look at protocol identification in encrypted tunnels which carry traffic from many TCP connections simultaneously, using only post-encryption observable features. We then explore the problem of protocol identification in individual encrypted TCP connections, using much less data than in other recent approaches. The results of our evaluation show that our classifiers achieve accuracy greater than 90% for several protocols in aggregate traffic, and, for most protocols, greater than 80% when making fine-grained classifications on single connections. Moreover, perhaps most surprisingly, we show that one can even estimate the number of live connections in certain classes of encrypted tunnels to within, on average, better than 20%.

We present techniques for building HMM profiles for network applications using only the packet-level information that remains intact and observable after encryption, namely, packet size and arrival time. Using less information than previously thought possible, we demonstrate classification accuracy close to that of other recent techniques, and show success in classifying a variety of common network applications as observed from real Internet traffic traces.

This paper introduces a conferencing server design based on an innovative configurable computing architecture to support the information transmission and distributed processing associated with creating and maintaining simultaneous disjoint conferences among sets of N conferees, where r-dimensional meshes can be used as the conferencing components. An r-dimensional conferencing mesh network is strictly nonblocking if, regardless of the existing conferences implemented, a new conference among any subset of the idle conferees can be implemented using a connected set of idle processing elements without any disturbance to the existing conferences. Using arguments employing the isoperimetric ratios of the sizes of edge and node sets in a graph, we give necessary and sufficient conditions such that an r-dimensional conferencing mesh of M nodes provides strictly nonblocking conferencing to N conferees. We show that a necessary and sufficient condition for r-dimensional meshes to be strictly nonblocking, when dimension r is fixed, is that M = O(N(r+1)/r). For general r-dimensional meshes, M = O(r(r−1)/rN(r+1)/r) nodes are sufficient to support strictly nonblocking capabilities. A fundamental relationship is established between the requirements on M for strictly nonblocking conferencing among N conferees using certain graph structures and the isoperimetric ratios for those structures. © 1999 John Wiley & Sons, Inc. Networks 33: 293–308, 1999

Efficient interconnection networks are critical in providing low latency, high bandwidth communication in parallel and distributed computing systems with hundreds or thousands of processors. The well-known Clos network or v(m, n, r) network can be extended to provide full one-to-many or multicast capability. In this paper, we consider several typical routing control strategies for Clos-type nonblocking multicast networks and derive the necessary conditions under which this type of network is nonblocking for arbitrary multicast assignments in the strict sense as well as under these control strategies. The necessary conditions obtained are represented as the number of middle stage switches m/spl ges//spl Theta/(n[log r/log log r]). These results match the sufficient nonblocking condition for the currently best available explicitly constructed, constant stage nonblocking multicast network, and provide a basis for the optimal design of this type of multicast network.

A general technique to detect and control congestion status for high speed packet networks is formulated and analyzed. The technique is based on the notion of detection interval, which represents the time to complete a basic congestion detecting interaction between a packet source and destination. The congestion detection consists of having the source send special probe packets during a specified period of time and then await the return of a feedback packet from the destination, which conveys the result of analysis performed by the destination upon receiving the probe packets. The source would adjust its behavior to accommodate the network status reported by the feedback packet. We measure the performance of our congestion detecting scheme in terms of the detecting accuracy. Our analysis is based on a two-state model of network operation wherein a hypoexponential distribution is used for congestion durations. Analyses of our model have resulted in strategies to enhance the detecting accuracy for network congestion. An easily calculated approximation to determine the probe packet delay for optimal performance is provided, which can be employed by the destination to set probe waiting time in the detection interval to enhance the detecting accuracy.

In this paper, we describe the use of the certification-trail technique as the basis of a hybrid framework for building formally verified software systems. Our technique involves formally verifying only a part of a software system; however, the technique yields a software system which still satisfies the most important correctness properties. Substantial savings in the overhead of software verification, and also in program running time, are shown to be possible in comparison to traditional methods. We apply our technique to the problem of sorting, since sorting represents one of the most basic operations in computer science, and a formally verified sorting certifier should have significant applicability. The results presented in this paper represent an enhancement of the certification-trail technique relative to the detection of incorrect computational output caused by software faults.

We describe a conceptually novel and powerful technique to achieve fault detection and fault tolerance in hardware and software systems. When used for software fault detection, this new technique uses time and software redundancy and can be outlined as follows. In the initial phase, a program is run to solve a problem and store the result. In addition, this program leaves behind a trail of data which we call a certification trail. In the second phase, another program is run which solves the original problem again. This program however, has access to the certification trail left by the first program. Because of the availability of the certification trail, the second phase can be performed by a less complex program and can execute more quickly. In the final phase, the two results are compared and if they agree the results are accepted as correct; otherwise an error is indicated. An essential aspect of this approach is that the second program must always generate either an error indication or a correct output even when the certification trail it receives from the first program is incorrect. We formalize the certification trail approach to fault tolerance and illustrate realizations of it by considering algorithms for the following problems: convex hull, sorting, and shortest path. We compare the certification trail approach to other approaches to fault tolerance.>

In this paper we present a constructive design of a new class of cascaded network structures for broadcast applications called ring sandwich networks. These ring sandwich networks are rearrangeable in the sense that a request for a connection between a sender and a receiver can sometimes be realized only by first rearranging other existing connection paths through the network. We present analytical results which permit the average rearrangeability of ring sandwich networks to be evaluated on the basis of fundamental structural parameters associated with the ring sandwich design so that the trade-off between the network rearrangeability and the network cost can be determined. It is shown that the average number of rearrangements to satisfy a broadcast connection request relative to the subnetwork of the cascaded ring sandwich structure providing fanout can be reduced to O(1); this is in contrast to O(N) for other existing cascaded designs. We give detailed connecting algorithms that can be used to satisfy connection requests. We also support our analytically derived results with corroborating simulation data. This work provides an analytical framework for a class of low-cost broadcast networks currently being employed by government and industry in both broadcasting and conferencing applications wherein only a limited degree of rearrangements can be tolerated.>

This paper investigates design techniques which may be applied to make program testing easier. We present methods for modifying a program to generate additional data which we refer to as a certification trail. This additional data is designed to allow the program output to be checked more quickly and effectively. Certification trails have heretofore been described primarily from a theoretical perspective. In this paper, we report on a comprehensive attempt to assess experimentally the performance and overall value of the certification trail method. The method has been applied to nine fundamental, well-known algorithms for the following problems: convex hull, sorting, huffman tree, shortest path, closest pair, line segment intersection, longest increasing subsequence, skyline, and voronoi diagram. Run-time performance data for each of these problems is given, and selected problems are described in more detail. Our results indicate that there are many cases in which certification trails allow for significantly faster overall program execution time than a two-version programming approach, and also give further evidence of the breadth of applicability of this method.>

The authors report on an attempt to assess the performance of algorithms utilizing certification trails on abstract data types. Specifically, they have applied this method to the following problems: heapsort, Huffman tree, shortest path, and skyline. Previous results used certification trails specific to a particular problem and implementation. The approach allows certification trails to be localized to data structure modules making the use of this technique transparent to the user of such modules.>

The problem of fault diagnosis in multiprocessor systems is considered under a probabilistic fault model. The focus is on minimizing the number of tests that must be conducted to correctly diagnose the state of every processor in the system with high probability. A diagnosis algorithm that can correctly diagnose these states with probability approaching one in a class of systems performing slightly greater than a linear number of tests is presented. A nearly matching lower bound on the number of tests required to achieve correct diagnosis in arbitrary systems is proved. Lower and upper bounds on the number of tests required for regular systems are presented. A class of regular systems which includes hypercubes is shown to be correctly diagnosable with high probability. In all cases, the number of tests required under this probabilistic model is shown to be significantly less than under a bounded-size fault set model. These results represent a very great improvement in the performance of system-level diagnosis techniques.>

The authors present and analyze a probabilistic model for the self-diagnosis capabilities of a multiprocessor system. In this model an individual processor fails with probability p and a nonfaulty processor testing a faulty processor detects a fault with probability q. This models the situation where processors can be intermittently faulty or the situation where tests are not capable of detecting all possible faults within a processor. An efficient algorithm that can achieve correct diagnosis with high probability in systems of O(n log n) connections, where n is the number of processors, is presented. It is the first algorithm to be able to diagnose a large number of intermittently faulty processors in a class of systems that includes hypercubes. It is shown that, under this model, no algorithm can achieve correct diagnosis with high probability in regular systems which conduct a number of tests dominated by n log n. Examples of systems which perform a modest number of tests are given in which the probability of correct diagnosis for the algorithm is very nearly one.>

Results are presented for nonblocking multistage broadcast networks wherein a request from an idle input port to be connected to some set of idle output ports can be satisfied without any disturbance of other broadcast connections already existing in the network. Furthermore, a linear network control algorithm for realizing such a broadcast connection request is given. These results represent the best known explicit constructions with limited numbers of stages relative to both crosspoint and control algorithm complexity. Thus, these networks are highly useful for practical applications involving the movement of and collaboration with voice/video/text/graphics information that require broadcast capability. These networks are also useful for the interconnection of processor and memory units in parallel processing systems.>

A general procedure for error detection in complex systems, called the data block capture and analysis monitoring process, is described and analyzed. It is assumed that, in addition to being exposed to potential external fault sources, a complex system will in general always contain embedded hardware and software fault mechanisms which can cause the system to perform incorrect computations and/or produce incorrect output. Thus, in operation, the system continuously moves back and forth between error and no-error states. These external fault sources or internal fault mechanisms are extremely difficult to detect. The data block capture and analysis monitoring process is concerned with detecting deviations from the normal performance of the system, known as errors, which are symptomatic of fault conditions. The process consists of repeatedly recording a fixed amount of data from a set of predetermined observation lines of the system being monitored (i.e. capturing a block of data) and then analyzing the captured block in an attempt to determine whether the system is functioning correctly.>

The problem of diagnosis of soft failures at the system level in large and fully distributed networks of processors (or units) is considered. A system model in which each of the network's units is assumed to possess the ability to test (or evaluate) certain other units for the presence of failures is employed. Using this model and assuming that the total number of faulty units does not exceed a given bound, a distributed algorithm is presented which allows all the fault-free units to independently converge to correct and consistent diagnoses of the system status. This algorithm is also shown to be applicable to bounded fault situations where both units and communication links can be faulty.>

Hybrid fault diagnosability in distributed multiprocessor systems is considered for the case in which, in addition to units being faulty, communication links among units can also be faulty. A hybrid fault situation is a (bounded) combination of hard and soft failing units. A novel hybrid fault diagnosability, denoted (t/t/sub s/-unit: sigma -link)-diagnosability is introduced (a total of t or fewer units can be faulty with at most t/sub s/ of them soft-failing; sigma is the number of incorrect test outcomes caused by unreliable links)., This diagnosability is compatible with the previously known t/t/sub s/-diagnosability and can additionally tolerate up to sigma incorrect test outcomes to give always-correct diagnosis for any hybrid-fault (HF)-compatible syndrome from a hybrid fault situation. It is shown that an O( mod E mod ) algorithm, proposed originally by the authors (see ibid., vol.C-35, p.503-10, 1986) for faulty unit identification in t/sub s/-diagnosable systems, can be used to analyze a syndrome from a (t/sub s/-unit sigma -link)-diagnosable system efficiently without any preclassification of the syndrome in terms of HF-compatibility. It is shown that this algorithm not only identifies all the faulty units associated with an HF-compatible syndrome but also produces nonempty, always-correct diagnosis for many HF-incompatible syndromes.>

A hybrid fault situation in a PMC system is a (bounded) combination of permanently and intermittently faulty units. Mallela and Masson [8] have given a general characterization of PMC systems for the diagnosis of hybrid fault situations. For this so-called th/thidiagnosability, when a syndrome takes on a form that is compatible with an allowable permanent fault situation, diagnosis can always be performed that is correct but perhaps incomplete. However, for general hybrid fault situations, syndromes that are compatible with permanent fault situations are exceedingly rare. Hence, th/thidiagnosability makes very limited use of the set of all syndromes that can result from application(s) of the test set. In this paper, a new, broader type of diagnosability for hybrid fault situations is defined and fully characterized. With this new type of diagnosability, at least all the permanently faulty units in a hybrid fault situation can be diagnosed from any syndrome that can result from an application of the test set. Thus, the usefulness of the syndrome space is dramatically increased. Special forms of this diagnosability are presented. Finally, relationships to other diagnosabilities are described.

Using the PMC model of a multiprocessor system, a new, general quality of hybrid fitult (combinations of hard anid soft failing units) diagnosability is characterized which encompasses previously known results as well as provides a major extension. This new diagnosability, called t/ts/τ-diagnosability, serves as a measure of the extent to which collections of test results, called syndromes, contain information relative to faulty unit identification for various testing assignments. By analyzing a system's test assignment over tahges of the parameter values t, ts, and τ, the spectrum of diagnosis quality achievable in that system can be established. Fundamental interrelationships among these parameters are developed. Optimal designs of t/ts/τ-diagnosable systems are presented. The main result of this correspondence can be viewed as a master fault diagnosability characterization which from the perspective of usefulness of the syndrome space for correct diagnosis both unifies and expands the domain of hybrid fault diagnosabilities.

In this paper, a new approach to identifying faulty units in ti-diagnosable systems is described. This approach exploits special properties of the highly structured ti-diagnosable systems to produce a faulty unit identification algorithm which is shown to be of time complexity O(|E|) where |E| corresponds to the number of tests in the system. The diagnosis quality of the algorithm is as follows: 1) if the algorithm identifies a unit as faulty, it is always correct; 2) if the collection of test outcomes takes on a form that is compatible with a permanent fault situation, the algorithm identifies all of the corresponding faulty units; and 3) the algorithm identifies at least one faulty unit over collections of test outcomes significantly larger than those that are compatible with permanent fault situations.

Consider a classical PMC system composed of n units [1] where it is assumed that at most t1 of these units are faulty. Such a system is said to be t1/t1-diagnosable [3] if, given any complete collection of test results, the set of faulty units can be isolated to within a set of at most t1 units. This paper exposes some new, important properties of general t1/t1-diagnosable systems to present an O(n2.5) algorithm by which all the faulty units except at most one can be correctly identified and all the faulty units can be isolated to within a set of t1 or fewer units in which at most one can possibly be fault free.

In this paper, a new class of diagnosable systems, called tp-self-implicating systems, which is a special case of the well-known tp-diagnosable systems introduced by Preparata et al. [1], is described. If there are no more than tp faulty units and the faults are assumed to be permanent, then the faulty units in a tp-self-implicating system can always be identified using at least one of two straight forward criteria associated with test outcomes. In each case, the given faulty unit in effect implicates itself as faulty. Necessary and sufficient conditions are given on the structures of PMC models for self-implication. Finally, an algorithm for identifying the set of faulty units in a tp-self-implicating system is given which is linear in the number of tests in the system, rendering it more efficient than the most efficient known algorithm for the general class of tp-diagnosable systems.

Consider a system composed of n independent processors, each of which tests a subset of the others. It is assumed that at most tp of these processors are permanently faulty and that the outcome of a test is reliable if and only if the processor which performed the test is fault free. Such a system is said to be tp-diagnosable if, given any complete collection of test results, the set of faulty processors can be uniquely identified. In this paper, it is shown that tp-diagnosable systems, due to their robust interconnection structure, possess heretofore unknown graph theoretic properties relative to vertex cover sets and maximum matchings. An 0(n2.5) algorithm is given which exploits these properties to identify the set of faulty processors in a tp-diagnosable system. The algorithm is shown to be correct, complete, not based on any conjecture, and superior to any other known fault identification algorithm for the general class of tp-diagnosable systems.

For hybrid fault situations (that is, bounded combinations of permanent and intermittent faults) in a classical PMC diagnosable system [1], the identification of faulty units has heretofore required that testing be patiently and perhaps unrealistically repeated until the test results obtained are consistent with permanent fault situations. As a consequence, intermediate test results go unused. Moreover, the occurrence of test results consistent with permanent fault situations will, in generaL, be a rare event.

Multiple-unit computer systems which are to be tolerant of intermittently faulty units or transiently upset units are considered in this paper. Designs for such systems, which exploit a new so-called greedy diagnosis theory, are developed. Using greedy diagnosis, assessments on the condition of a unit (intermittent-fault case) or the integrity of data (transient-upset case) can be made on the basis of syndromes formed from comparisons of the results of jobs performed by pairs of units. Greedy diagnosis avoids the requirement that for such syndromes to be useful, they must be interpretable from a permanent-fault/continuous-upset perspective.

A concentrator is an interconnection network with n inputs and m outputs, n > m, wherein any specified subset of inputs of size less than or equal to some number, called the network's actual capacity, can always be simultaneously connected to some equal-sized but unspecifiable subset of outputs. Guaranteed throughput as described by actual capacity has heretofore been the principle measure for evaluating concentrator performance. In many applications, however, a more practical measure of a concentrator's capability is a probabilistic measure of its throughput in the following sense: given an input subset of size k, k ≤ m, what is the average number of inputs that can be connected to outputs? This measure will be called expected capacity. This paper considers the expected capacity of a special class of sparse crossbar concentrators called ( m 2 ) networks. It is seen that the expected capacity values for ( m 2 ) networks are usually quite close to k.

Fault analysis of digital systems is highly dependent upon the fault model employed. Much previous work utilizes fault models known to contain inaccuracies in order to permit mathematically tractable analysis. In this correspondence a new approach is taken which combines faults, hardware, and software together into one overall model. This new model is shown to be useful for the consideration of intermittent/transient faults. It supports a new method, based on the novel concept of a containment set, for realizing transient fault tolerance without massive redundancy. It also allows for a new approach to system fault tolerance evaluation and validation which uses a transition matrix which is defined in terms of the containment set.

Lower bounds on the required number of crosspoints in concentrators, a class of interconnection networks, are given. The lower bounds are obtained from a straightforward necessary condition on the number of crosspoints in sparse crossbar full capacity concentrators. Because this condition must be satisfied by all full capacity concentrators embedded in more general concentrators, the general necessary condition is established. Several sparse crossbar designs that contain the minimum number of crosspoints are presented. An extension of the results to a more general class of interconnection networks is described.

Given any combinational, internal fan-out-free network and any complete single fault detection test set (SFDTS) for the network, we consider in this paper the problem of determining the minimal extent to which that SFDTS will cover multiple faults in the network. The basis of our approach is the development of a generic perspective to multiple faults which uses a representation of such faults called an L-expression. This perspective leads to a technique for obtaining the greatest lower bound on the multiple fault coverage capability of an SFDTS by means of a simple table look-up process. In addition to generalizing previously known results regarding multiple fault coverage, two particularly interesting results obtained from this approach are as follows: 1) On the average, every SFDTS for an internal fan-out-free network covers 92 percent of all multiple faults of sizes 8 and less. 2) On the average, every SFDTS for an internal fan-out-free network covers at least 46.1 percent of all multiple faults.

For a new class of fault situations called hybrid fault situations, we consider the fault diagnosing capabilities of systems which for testing/monitoring purposes can be viewed as being composed of independent units. The classical Preparata, Metze, and Chien model (PMC model) is used to specify the various testing assignments among the units. Hybrid fault situations are described as explicitly bounded combinations of permanently and intermittently faulty units. This new concept of a hybrid fault situation includes as special cases the all permanent fault case and the unrestricted intermittent fault case which have both been previously considered with PMC models. A general characterization of the so-called connection assignment of a PMC model is established for a diagnosing capability which is referred to as hybrid fault diagnosability without repair. This diagnosing capability is compatible with the well-known permanent fault diagnosability without repair concept, and the quality of this diagnosing capability is shown to be correct, but sometimes an incomplete diagnosis where the incompleteness is solely a consequence of intermittently faulty units. The characterization for hybrid fault diagnosability without repair is seen to encompass as extreme cases the previously known special characterizations for permanent and unrestricted intermittent diagnosability without repair. Fundamental interrelationships are determined among parameter bounds used to describe the hybrid fault cases which can be diagnosed for a given PMC model.

In the generation of test sets for the detection of stuck-type faults in combinational switching networks, it is an expedient and reasonably common assumption to consider explicitly faults only of specified sizes (for example, all single faults), and then to assume (or hope) that most or all faults of larger sizes will be covered (that is, detected) as well. This paper systematically addresses this aspect of multiple fault coverage in a quantitative manner for combinational networks, wherein only primary input fanout is allowed. A procedure is given to estimate (or project) the multiple fault coverage capability of a test set based on the known coverage capability of that test set for subsets of the multiple faults. This is accomplished by means of a recursive use of a detailed formula which exploits two fundamental interrelationships between test sets and faults. Based upon these results, it can be shown that the above-mentioned assumption must be made, in general, with discretion as its validity is highly network structure/test set dependent.

To efficiently perform the fault analysis of digital networks it is necessary that pertinent fault interrelationships be utilized. However, to determine these fault interrelationships can entail an analysis which is quite complex and thereby reduces the overall advantage of utilizing the gained insights in a fault analysis process. In this paper we suggest an approach to establishing the existence of a certain fault interrelationship relative to test set coverage in tree networks which is based only on the form of the output function. A procedure is given for generating a form expression (called an L-expression) corresponding to that function. A theorem is stated regarding the interpretation of these form expressions relative to test set coverage.

Diagnosable systems composed of interconnected units which are capable of testing each other have been studied primarily from the point of view of permanent faults. Along such lines, designs have been proposed, and necessary and sufficient conditions for the diagnosis of such faults have been established. In this paper, we study the intermittent fault diagnosis capabilities of such systems. Necessary and sufficient conditions are derived and bounds are established for some well-known systems. It is seen that in contrast to permanent fault diagnosable systems, there exists only a single type of intermittent fault diagnosable system. A procedure is given to determine the intermittent fault diagnosability of any given system.

A new diagnosis algorithm for determining the existing fault situation in a symmetric multiple processor architecture is given. The algorithm assumes that there are n processors, each of which is tested by at least t other processors, and at most t of which are faulty. The existing fault situation is always diagnosed if n ≥ 2t + 1 and, in some cases, can still be diagnosed if n < 2t + 1. The implementation of the algorithm is straightforward and suitable for microprocessor applications.

This correspondence considers fault resolution as a process of applying a sequence of input vectors, called tests, to a combinational logic network in order to resolve an existing fault situation from within a given master set of faults. A functional approach based upon an extension of the well-known Boolean difference concept to fault dependent situations is described. The test sets resulting from this extension, called fault dependent test sets, are fundamental to our considerations and are shown to be obtainable in a straightforward manner from standard test sets. Two fault interrelationships are defined which are particularly relevant to the resolution problem in that they algebraically describe the inherent limitations to the degree to which the existing fault situation can be resolved from within a given master set of faults using algebraic terminal experiments and fault dependent testing. Because these interrelationships are defined from a resolution-oriented point of view, they can be seen to be somewhat more intimate than other fault interrelationships which have been previously described in the literature. Some important ramifications of these interrelationships are discussed.

In this paper a new class of switching networks is presented for concentration and distribution interconnection assignments between disjoint sets of input and output terminals. These networks are called binomial switching networks because of their structural association with the binomial distribution. Binomial networks are uniform in that all connecting paths are of equal length and are such that cycles or iterations through stages of the network are not permitted, and binomial networks are rearrangeable in that implementing an additional path through the network for a new connection can require the rearranging of existing paths. It is shown that an upper bound on the number of such rearrangements is closely related to the number of stages in the network. A sparse crossbar switch construction of the binomial switching network is presented which contains crossbar switches in which it is not possible to connect each switch input to each switch output. Finally, the number of crosspoints needed for such networks for sufficiently large numbers of input and output terminals is seen to be less than the classical, benchmark alternatives for both concentration and distribution assignments.

The Boolean difference is a well-known mathematical concept which has found significant application in the single fault analysis of combinational logic circuits. One of the primary attributes of the Boolean difference in such situations is its completeness. In this paper we extend the Boolean difference concept to cover multiple fault situations. Expressions are developed which give all possible input patterns that can be applied to combinational logic circuits to demonstrate the presence or absence of a specified multiple fault of the stuck-type class. Such expressions are useful in situations where at most, say, p simultaneous faults need be considered, as well as situations where any multiple fault can exist. In addition the expressions developed are also shown to complete some existing single fault analysis concepts.

Abstract This paper develops multi‐stage connection networks in which each input terminal can be connected to any number of output terminals. Conditions are given such that these networks are strictly nonblocking or are rearrangeable. Rearrangement algorithms and upper bounds on the required number of moves are developed and it is shown that such networks have fewer cross‐points than the product of input and output terminals for a sufficiently large number of input and output terminals.