Predicting failures and acting proactively have a potential to improve availability as a correct prediction and a successful mitigation may bring a reward resulting in decrease of downtime and availability improvement. But, conversely, each incorrect prediction may introduce additional downtime (penalty). Therefore, depending on the quality of prediction and the system parameters, predictive fault-tolerance methods may improve or may degrade availability in comparison to the reactive ones. We first derive taxonomies of fault-tolerant techniques and policies to differentiate between reactive and proactive policies that are further classified as systematic and predictive. To evaluate whether a predictive policy improves availability or not, we derive an analytical model for availability quantification. We use Markov chains to extend steady-state availability equation to include: precision and recall, penalty and reward, mitigation success probability and potential failure rate increase due to the prediction load. We also derive an A-measure to optimize failure prediction for increasing availability. In our conclusion, precision and recall have comparable impact on availability as changing MTTF and MTTR. To validate the model we also simulate and analyze availability of a virtualized server with exponential distribution of failure and repair rates.

We tackle the problem of classifying Electrocardiography (ECG) signals with the aim of predicting the onset of Paroxysmal Atrial Fibrillation (PAF). Atrial fibrillation is the most common type of arrhythmia, but in many cases PAF episodes are asymptomatic. Therefore, in order to help diagnosing PAF, it is important to design procedures for detecting and, more importantly, predicting PAF episodes. We propose a method for predicting PAF events whose first step consists of a feature extraction procedure that represents each ECG as a multi-variate time series. Successively, we design a classification framework based on kernel similarities for multi-variate time series, capable of handling missing data. We consider different approaches to perform classification in the original space of the multi-variate time series and in an embedding space, defined by the kernel similarity measure. We achieve a classification accuracy comparable with state of the art methods, with the additional advantage of detecting the PAF onset up to 15 minutes in advance.

Malware detection methods are divided in two groups: static and dynamic. While methods based on static analysis might be lightweight and suitable for constrained resources of mobile devices, they suffer from inability to detect malware during its execution. On the other side, dynamic detection methods are usually too complex to be run on mobile devices. This paper is about dynamic, but lightweight, detection methods and, in particular, about features that can be used in these methods to identify malware. We take into account all the features related to memory and CPU usage that can be collected and observed on the mobile device through its operating system. We analyze these features and their significance within the malware families they belong to, and take into account the most indicative ones for each family. Furthermore, we analyze the occurrence of features in all the families. By taking into account the most indicative features per malware family we determine ones that are more resistant to variety of mobile malware rather than just observe the overall significance of features. Results show that the number of occurrences of features among the most indicative ones varies; some features appear as good candidates for malware detection in general, some features appear as good candidates for detection of specific malware families, and some others are simply irrelevant.

Fabrication process introduces some inherent variability to the attributes of transistors (in particular length, widths, oxide thickness). As a result, every chip is physically unique. Physical uniqueness of microelectronics components can be used for multiple security applications. Physically Unclonable Functions (PUFs) are built to extract the physical uniqueness of microelectronics components and make it usable for secure applications.

With an ever-increasing and ever more aggressive proliferation of malware, its detection is of utmost importance. However, due to the fact that IoT devices are resource-constrained, it is difficult to provide effective solutions. The main goal of this paper is the development of lightweight techniques for dynamic malware detection. For this purpose, we identify an optimized set of features to be monitored at runtime on mobile devices as well as detection algorithms that are suitable for battery-operated environments. We propose to use a minimal set of most indicative memory and CPU features reflecting malicious behavior. The performance analysis and validation of features usefulness in detecting malware have been carried out by considering the Android operating system. The results show that memory and CPU related features contain enough information to discriminate between execution traces belonging to malicious and benign applications with significant detection precision and recall. Since the proposed approach requires only a limited number of features and algorithms of low complexity, we believe that it can be used for effective malware detection, not only on mobile devices, but also on other smart elements of IoT.

As computing systems become increasingly pervasive, the number of applications that can benefit from or require localization capabilities continuously increases. In indoor environments, wireless sensor networks are a common means to perform localization, trilateration being one of the most commonly used techniques. The placement of anchor nodes influences greatly the system performance and cost. This paper addresses the placement problem for fault-tolerant trilateration based localization. The goal is to minimize the number of anchor nodes needed to localize a target anywhere in an area of arbitrary shape with obstacles, even after one anchor node fails. We propose an exact algorithm based on integer linear programming, as well as an efficient heuristic to solve this problem. The heuristic consists of greedy placement and pruning stages, and achieves the results, in terms of the number of anchors placed, within less than 0.5% of optimum on average. We validate our solutions by simulation.

With Smart Grids efficiency of the electric power delivery service can be significantly increased by using advanced ICT infrastructure. The looming danger of merging two critical infrastructures, ICT and electric power, is that dependability may be compromised due to interdependencies and different approaches to dependability in the two communities. This calls for a unified approach to dependability which may be achieved by viewing Smart Grids as cyber-physical systems. We analyze and compare definitions and figures of merit used in ICT and electric power systems' communities to provide the basis for dependability analysis of Smart Grids. We propose a taxonomy of faults for Smart Grids by examining a large set of previous power system outages. Our work relies on the analysis of relevant events from the past in an attempt to understand present dependability state of Smart Grids and pave the way for proactive grid management.

With explosive growth in the number of mobile devices mobile malware is rapidly spreading, making security one of the key issues. Existing solutions, which are mainly based on binary signatures, are not very effective. The main contribution of this paper is a novel methodology to design and implement secure mobile devices by offering a resource-optimized method that combines efficient, light-weight malware detection on the mobile device with high precision detection methods on cloud servers. We focus on the early detection of behavioral patterns of malware families rather than the detection of malware binary signatures. Upon detection of an attack, an alarm is raised and the damage that can be caused by the detected malware type is estimated. Furthermore, the database with behavioral patterns is continuously updated, thus keeping a device resistant to new malware families.

Service Discovery (SD) is an integral part of service networks. Before a service can be used, it needs to be discovered successfully. Thus, a comprehensive service dependability analysis needs to consider the dependability of the SD process. As a time-critical operation, an important property of SD is responsiveness: the probability of successful discovery within a deadline, even in the presence of faults. This is especially true for dynamic networks with complex fault behavior such as wireless networks. We present results of a comprehensive responsiveness evaluation of decentralized SD, specifically active SD using the Zeroconf protocol. The ExCovery experiment framework has been employed in the Distributed Embedded System (DES) wireless test bed at Freie Universität Berlin. We present and discuss the experiment results and show how SD responsiveness is affected by the position and number of requesters and providers as well as the load in the network. Results clearly demonstrate that in all but the most favorable conditions, the configurations of current SD protocols struggle to achieve a high responsiveness. We further discuss results reflecting the long-term behavior of the test bed and how its varying reliability impacts SD responsiveness.

Today's businesses rely ever more on dependable service provision deployed on information and communications technology (ICT) infrastructures. Service dependability is highly influenced by the properties of individual infrastructure components. Combining these properties for consistent dependability analysis is challenging as every service requester might use a different set of components during service usage, constituting the user-perceived view on a service. This paper presents a methodology to evaluate user-perceived instantaneous service availability. It uses three input models: (1) The ICT infrastructure, with failure rates, repair rates and deployment times of all components, (2) an abstract description of complex hierarchical services, (3) a mapping that contains concrete ICT components for the service pair requester and provider, as well as existing replicas, and a duration of usage. The presented methodology sets up the basis for automatic generation of availability models from those parts of the ICT infrastructure needed during provision for the specified pair. To calculate instantaneous availability, the age of the ICT components, the order and time of their usage during service provision are taken into account. The methodology supports generation of different availability models, exemplarily providing reliability block diagrams and fault-trees. We demonstrate the feasibility of the proposed approach by applying it to parts of the network infrastructure of University of Lugano, Switzerland.

Over the last decade, research on dependable computing has undergone a shift from reactive towards proactive methods: In classical fault tolerance a system reacts to errors or component failures in order to prevent them from turning into system failures, and maintenance follows fixed, time-based plans. However, due to an ever increasing system complexity, use of commercial-off-the-shelf components, virtualization, ongoing system patches and updates and dynamicity such approaches have become difficult to apply. Therefore, a new area in dependability research has emerged focusing on proactive approaches that start acting before a problem arises in order to increase time-to-failure and/or reduce time-to-repair. These techniques frequently build on the anticipation of upcoming problems based on runtime monitoring. Industry and academia use several terms for such techniques, each focusing on different aspects, including self-* computing, autonomic computing, proactive fault management, trustworthy computing, software rejuvenation, or preventive/proactive maintenance.

An overview of a generic restart procedure of a computer system - be it a personal computer, a server or a big parallel machine - is presented. The objective of this paper is to analyze the restart procedures and propose techniques to reduce the time taken to restart the system, hence providing higher availability and ultimately assurance. Experiments, data and evaluation are provided to support the achieved results.

Assurance networks are designed to realize trustable Internet-Of-Things including terminal devices/infrastructure service applications for new generation networks. This paper proposes a unified design model for assurance networks and demonstrates the model, methodology and its application to mobile ad hoc networks. In the unified design model, in order to realize the assurance networks, an overall network is partitioned into sub networks and real-time self-organized control functions are incorporated into each sub network for resilience to dynamic change, faults possibly causing failure and attacks to security. In the application of the proposed unified design model to mobile ad hoc networks, a real-time self-organizing autonomous clustering is presented. The simulation experimental results show that the presented autonomous clustering is resilient to a diversity of node mobility and its variation.

Permanence of the assurance challenge in computer and communication systems is described and justified. Models and methods of meeting the assurance challenge are briefly outlined.

Dependability should be considered throughout the phases of the SOA life cycle. This article proposes the application of a service level management approach to address dependability and presents dependability-related activities for every stage (Model, Assemble, Deploy, and Manage) of the SOA life cycle. Furthermore, we describe the concepts and the formalisms that are behind these activities. Following these activities service providers and aggregators can offer optimized levels of dependability from their existing services and thus better meet user requirements.

Proactive approaches to failure avoidance, recovery and maintenance have recently attracted increased interest among researchers and practitioners from various areas of dependable system design and operation. This first workshop provided a stimulating, and fruitful forum to foster collaboration among researchers working on proactive fault management, to discuss ideas, exchange experiences and to find new answers to the overall challenge of significantly improving system dependability in contemporary computing and communication systems.

We analyze accuracy of hysteresis link status detectors in static and mobile wireless multi-hop networks (WMNs), with focus on errors in link status detection caused by the unreliable communication channel. The hysteresis link status detectors are of particular importance in WMNs due to their use in various protocols, such as AODV and OLSR. Stochastic models are derived that describe hysteresis link status detector behavior as a function of detector parameters and network characteristics. Models are applied to a real network and their analysis shows that the probability of errors in link status detection in WMNs is considerable. In order to reduce these errors, we optimize detector parameters so that the link detection error probability is minimized.

The members of a self-organizing distributed system have ability to automatically organize themselves into a specific structure. The functionality of the system is achieved by collaboration of the members in this structure. Through automatic (re)organization, such a system is able to recover from various temporary faults which may disturb the established structure. In this paper, we propose a technique to identify all recoverable faults as well as to analyze fault tolerance and recovery from temporary faults by reorganization in self-organizing systems.

Proactive approaches to failure avoidance, recovery and maintenance have recently attracted increased interest among researchers and practitioners from various areas of dependable system design and operation. This first workshop aimed to provide a stimulating, and fruitful forum to foster collaboration among researchers working on proactive fault management, to discuss ideas, exchange experiences and to find new answers to the overall challenge of significantly improving system dependability in contemporary computing and communication systems.

With ever-growing complexity of computer and communication systems analytical methods do not scale, especially with respect to dependability assessment of information technology (IT) organization. Generic reference models can be used as an alternative to analytical approaches by focusing on transforming qualitative assessment into quantitative evaluation of IT organization. In this paper, we examine the reference models IT infrastructure library (ITIL) and the control objectives for information and related technology (CobiT) to derive a quantifiable concept for estimating the criticality of dependability-related IT organization processes in CobiT. After systematically analyzing ITIL processes and deriving properties that are relevant to dependability, those processes are mapped onto CobiT processes. Furthermore, we propose a process criticality index (PCI) which reflects the significance of each dependability-related process within a particular reference model. The PCI is based on the graph theory concept of betweenness centrality and uses a directed graph where nodes represent dependability-related processes and edges relations among them. Finally, using cycle and sequence analysis we are able to identify for every process which processes have to be implemented a priori. This provides an efficient strategy for implementing most significant processes first, according to the ranking based on the PCI.

This paper evaluates replication possibilities for Web services at the operating system level and how they affect Web service performance. This is done in the context of architectural translucency - an approach that defines layers in a service-oriented architecture and states that similar measures have different implications on nonfunctional properties when applied at different layers in different ways. The observed layer here is the operating system. The work presents current request processing techniques and how they are implemented in a typical platform for Web services (Windows Server 2003, IIS and .NET). It then proposes two ways to replicate Web services - per-process replication and per-thread replication and techniques to configure them on the selected platform. The case study demonstrates the feasibility of the concept with performance advantages of up to 50%.

We identify parameters impacting Web services dependability, describe the methods of dependability enhancement by redundancy in space and redundancy in time, and perform a series of experiments to evaluate the availability of Web services. To increase the availability of Web services, we employ several replication schemes and compare them with a single service. The Web services are coordinated by a replication manager. It provides a round robin algorithm for scheduling the workload of the Web services and keeps updating the availability of each Web service. The replication algorithm and the detailed system configuration are described. Experiments are performed to evaluate the resulting service availability. Modeling on the Web services with Petri-net is constructed and verified through experiments with different applications. With the parameters obtained from the experiments, the proposed model can be engaged to demonstrate the characteristics of the Web service.

We extend the Breadth First Search (BFS) algorithm to use it for cut-edge(bridge) detection in graphs. The changes in the algorithm are tailored such that the algorithm can be applied in wireless multihop networks: e.g., it fully utilizes the broadcasting nature of the wireless medium. The distributed BFS algorithm (flooding) is widely used for route discovery and information dissemination in wireless multihop networks (WMNs) so the overhead introduced by our bridge detection algorithm is limited - the network is already performing the distributed BFS and we reuse the information from it to detect the bridges.

A proactive handling of faults requires that the risk of upcoming failures is continuously assessed. One of the promising approaches is online failure prediction, which means that the current state of the system is evaluated in order to predict the occurrence of failures in the near future. More specifically, we focus on methods that use event-driven sources such as errors. We use hidden semi-Markov models (HSMMs)for this purpose and demonstrate effectiveness based on field data of a commercial telecommunication system. For comparative analysis we selected three well-known failure prediction techniques: a straightforward method that is based on a reliability model, dispersion frame technique by Lin and Siewiorek and the eventset-based method introduced by Vilalta et al. We assess and compare the methods in terms of precision, recall, F-measure, false-positive rate, and computing time. The experiments suggest that our HSMM approach is very effective with respect to online failure prediction.

Recently, measurement-based studies of software systems have proliferated, reflecting an increasingly empirical focus on system availability, reliability, aging, and fault tolerance. However, it is a nontrivial, error-prone, arduous, and time-consuming task even for experienced system administrators, and statistical analysts to know what a reasonable set of steps should include to model, and successfully predict performance variables, or system failures of a complex software system. Reported results are fragmented, and focus on applying statistical regression techniques to monitored numerical system data. In this paper, we propose a best practice guide for building empirical models based on our experience with forecasting Apache web server performance variables, and forecasting call availability of a real-world telecommunication system. To substantiate the presented guide, and to demonstrate our approach in a step by step manner, we model, and predict the response time, and the amount of free physical memory of an Apache web server system, as well as the call availability of an industrial telecommunication system. Additionally, we present concrete results for a) variable selection where we cross benchmark three procedures, b) empirical model building where we cross benchmark four techniques, and c) sensitivity analysis. This best practice guide intends to assist in configuring modeling approaches systematically for best estimation, and prediction results.

The goal of online failure prediction is to forecast imminent failures while the system is running. This paper compares similar events prediction (SEP) with two other well-known techniques for online failure prediction: a straightforward method that is based on a reliability model and dispersion frame technique (DFT). SEP is based on recognition of failure-prone patterns utilizing a semi-Markov chain in combination with clustering. We applied the approaches to real data of a commercial telecommunication system. Results are presented in terms of precision, recall, F-measure and accumulated runtime-cost. The results suggest a significantly improved forecasting performance.

We have developed a mathematical model for calculation of expected value of share of edges being dropped while constructing a Gabriel or a relative neighborhood graph starting from a random geometrical graph created by a homogeneous Poisson point process on a plane. The expressions for the expected values of number of faces and face size are derived as well. All expressions are given as functions of deployment configuration. The results are verified through detailed comparison with extensive simulation results. Since Gabriel and relative neighborhood graphs are used for various applications in ad hoc networking we believe that our model simplifies theoretical analysis of functionality and performance of such networks

Recently, measurement based studies of software systems proliferated, reflecting an increasingly empirical focus on system availability, reliability, aging and fault tolerance. However, it is a non-trivial, error-prone, arduous, and time-consuming task even for experienced system administrators and statistical analysis to know what a reasonable set of steps should include to model and successfully predict performance variables or system failures of a complex software system. Reported results are fragmented and focus on applying statistical regression techniques to captured numerical system data. In this paper, we propose a best practice guide for building empirical models based on our experience with forecasting Apache Web server performance variables and forecasting call availability of a real world telecommunication system. To substantiate the presented guide and to demonstrate our approach step-by-step we model and predict the response time and the amount of free physical memory of an Apache Web server system. Additionally, we present concrete results for a) variable selection where we cross benchmark three procedures, b) empirical model building where we cross benchmark four techniques and c) sensitivity analysis. This best practice guide intends to assist in configuring modeling approaches systematically for best estimation and prediction results

In the context of clients accessing a read/write shared object, persistency of a written value is a property stating that a value written into the object is always available unless overwritten by a successive write operation. This property can be easily guaranteed in a static distributed system provided that either a subset of processes implementing the object does not crash or processes can crash and then recover being able to retrieve their last state. Unfortunately the enforcing of this property in a potentially large scale and dynamic distributed system (e.g. a P2P system) is far from being trivial when considering the case in which processes implementing the object may fail or leave at any time without notifying any other process (i.e., the last state might not be retrievable). The paper introduces the notion of weak persistency that guarantees persistency of values when a system becomes quiescent (arrivals and departures subside). An implementation of a weakly-persistent object ensuring causal consistency is provided along with its correctness proof. The interest of causal consistency lies in the fact that, contrarily to atomic consistency, it can be maintained even during non-quiescent periods of the distributed system (i.e., when persistency is not guaranteed)

Availability prediction in a telecommunication system plays a crucial role in its management, either by alerting the operator to potential failures or by proactively initiating preventive measures. In this paper, we apply linear (ARMA, multivariate, random walk) and nonlinear (Radial and Universal Basis Functions) regression techniques to recognize system failures and to predict the system's call availability up to 15 minutes in advance. Secondly we introduce a novel nonlinear modeling technique for call availability prediction. We benchmark all five techniques against each other. The applied modeling methods are data driven rather than analytical and can handle large amounts of data. We apply the modeling techniques to real data of a commercial telecommunication platform. The data used for modeling includes: a) time stamped event-based log files; and b) continuously measured system states. Results are given in terms of a) receiver operator characteristics (AUC) for classification into classes of failure and non-failure states and b) as a cost-benefit analysis. Our findings suggest: a) high degree of nonlinearity in the data; b) statistically significant improved forecasting performance and cost-benefit ratio of nonlinear modeling techniques; and finally finding that c) log file data does not contribute to improve model performance with any modeling technique

Summary form only given. A proposal for a new generation of logfiles with regard to new challenges posed by autonomic computing is presented. While a variety of techniques are being developed on the way to autonomic computing, the problem of a system's logfiles remains to be critical. Several recommendations for logfile design are introduced: (a) Event type and source of events have to be distinguishably incorporated into the design, (b) Logfiles should incorporate hierarchical numbering schemes, (c) Information contained in logfiles should be categorized into classes, (d) Logfiles have to easily lend themselves to automatic analysis, (e) Information density of logfiles should be considered in the design of logging functionality. A metric to measure information entropy of logfiles is proposed. The type of information to be included in logfiles in order to support various aspects of autonomic computing as originally defined by IBM's eight elements is specified.

The Common Object Request Broker Architecture (CORBA) is a widely-accepted, standardized open system integration framework based on distributed object technologies, which has been successfully used for implementation of open Web services. CORBA is focused on facilitating general computing environments and does not explicitly address quality-of-service parameters neither for its communication links nor its endsystems. However efforts like the Real-Time CORBA Special Interest Group (SIG) at OMG and the "pluggable protocols" proposal will ultimately lead to support of quality-of-service properties for CORBA communication links. We concentrate on architectural approaches for fault-tolerant, highly available endsystems. We present the Observer approach for implementation of reliable CORBA clients. Consensus protocols based on the Composite Objects technique is our solution for constructing CORBA servers with high predictability regarding timely and reliable method execution. Our middleware uses commercial off-the-shelf (COTS) technology and aims at conversion of legacy applications into reliable Web-services. We present Java-based Web-interfaces to the Balancing Robots soft real-time simulation. Also, we demonstrate a fault-tolerant version of the Netscape Navigator based on our Observer technique.

The Common Object Request Broker Architecture (CORBA) is a widely-accepted, standardized system integration framework based on distributed object technologies. CORBA is focused on facilitating general computing environments and does not explicitly address the needs of responsive (fault-tolerant, real-time) computing. Therefore, the question remains how to extend today's CORBA implementations for support of responsive computing. In this paper we propose a CORBA-based distributed framework for responsive execution of CORBA method invocations. The framework exploits consensus for synchronization, reliable communication, and fault diagnosis among replicated server objects. Within the replicated server objects, we use the "Composite Objects" technique for predictable integration of CORBA and responsive computing. We present a methodology for creating objects which interface to CORBA while simultaneously supporting fault-tolerance and real-time requirements.

The Rate Monotonic Scheduling (RMS) policy is a widely accepted scheduling strategy for real-time systems due to strong theoretical foundations and features attractive to practical uses. For a periodic task set of n tasks with deadlines at the end of task periods, it guarantees a feasible schedule on a single processor as long as the utilization factor of the task set is below n(2/sup 1/n/-1) which converges to 0.69 for large n. We analyze the schedulability of a set of periodic tasks that is scheduled by the RMS policy and is susceptible to a single fault. The recovery action is the reexecution of all uncompleted tasks. The priority of the RMS policy is maintained even during recovery. Under these conditions, we guarantee that no task will miss a single deadline, even in the presence of a fault, if the utilization factor on the processor does not exceed 0.5. Thus, 0.5 is the minimum achievable utilization that permits recovery from faults before the expiration of the deadlines of the tasks. This bound is better than the trivial bound of 0.6912=0.345 that would be obtained if computation times were doubled to provide for reexecutions in the RMS analysis. Our result provides scheduling guarantees for tolerating a variety of intermittent and transient hardware and software faults that can be handled simply by reexecution. In addition, we demonstrate how permanent faults can be tolerated efficiently by maintaining common spares among a set of processors that are independently executing periodic tasks.

Introduces a nested-predicate scheme for fault tolerance, called Nest. Nest provides a formal comprehensive model for fault-tolerant parallel algorithms and a general methodology for designing reliable applications for multiprocessor systems. The model relies on the formalization of concepts for fault tolerance by means of three nested system predicates and on properties ruling their interrelationships. This rigorous framework facilitates the study of the specific properties that enable an algorithm to tolerate faults. The consequence of that is the outline of systematic design techniques that can be used to add fault tolerance properties to algorithms while preserving their functional characteristics.>

The tabu search is a new promising optimization heuristic used for obtaining near-optimum solutions of combinatorial optimization problems. This paper looks into an implementation of tabu search on dedicated hardware and shows a potential for improvements of two orders of magnitude in the time taken to perform a fixed number of iterations for the traveling salesman problem (TSP).>

A class of algorithms suitable for fault-tolerant execution in multiprocessor systems by exploiting the existing embedded redundancy in the problem variables is characterized. Because of this unique property, no extra computations need be superimposed on the algorithm in order to provide redundancy for fault recovery, as well as fault detection in some cases. A forward recovery scheme is thus used with very low time overhead. The method is applied to the implementation of two iterative algorithms: solution of Laplace equations by Jacobi's method and the calculation of the invariant distribution of a Markov chain. Experiments show less than 15% performance degradation for significant problem instances in fault-free situations, and as low as 2.43% in some cases. The extra computation time needed for locating and recovering from a detected fault does not exceed the time necessary to execute a single iteration. The fault-detection procedures provide fault coverage close to 100% for faults causing errors that affect the correctness of the computations.>

The authors present efficient methods for testing packet-switched multistage interconnection networks. In addition to testing the data paths and routing capabilities, tests for detecting faults in the control circuitry including the conflict resolution capabilities are provided. Using a general model of the switch, testing sequences are constructed for the internal functions of the f*f switch requiring only O(f/sup 2/2/sup f/) tests in the case of round-robin priority and O(f2/sup f-1/) in the case of fixed priority (f is usually a constant that is less than or equal to eight). Algorithms are then presented to test the entire network using at most twice the number of tests needed to test a switch, independently of the network size, which results in O(log N) testing time for an N-processor network. It is shown that the method achieves higher coverage and several-orders-of-magnitude reduction in the testing time of complex multiprocessor systems compared to previous methods.>

Efficient testing techniques for two-dimensional mesh interconnection networks are presented. The tests cover faults in the data paths and the control circuitry, including faults in the arbitration logic of the switches. Testing for the resolution of the conflicts is important for ensuring the correct functioning of the interconnection network, since a fault in the arbitration logic may cause the loss of packets. Modeling conflict resolution as a graph coloring the approach optimizes the testing time by parallelizing the tests for different nodes. The testing time is constant, independent of the size of the parallel network, except for the routing tests. The proposed methods are not implementation specific and can be applied to any design with a mesh topology. However, for some specific designs only a subset of tests might be needed, depending on the type of communication or control scheme. The novel approach to the minimization of the conflict tests is twofold: it can be used to test the conflicts; it also gives a method for controlling each input of a switch and observing each output of the switch such that any test at each level can be applied to as many nodes as possible simultaneously.>

Production testing of a digital circuit requires the generation of a sequence of tests and their application to the circuit being tested. Currently, in test application, the output of the circuit under test is compared to a known correct output for each test. The method has some drawbacks likely to become more critical in the near future. In homogeneous systems of identical integrated circuits of silicon wafers, testing can be done in another way, i.e. by applying a common test to several processing elements at once and comparing the results produced by them. The authors analyze such schemes and show that they are inherently as accurate as current methods that use assumed correct results for production testing. Since this approach could allow wafers to be tested for production faults significantly more quickly than by using a probe tester, the results indicate that it can provide an attractive alternative to current methods for production testing of silicon wafers.>

Topological testing is introduced and its applications are presented. Topological testing uses graph-theoretic optimization methods such as the traveling salesman problem, the Chinese postman problem, coloring, path covering, and partitioning to minimize the test time. The topological testing techniques can be applied to test a system's behavior and its organization at each level of the system's hierarchy, namely, circuit, logic, register transfer, instruction, and processor-memory-switch levels. Specifically, the topological testing approach is demonstrated by developing tests for the multistage interconnection network and the hypercube network. Time optimization for the testing of these networks gives very promising results by taking advantage of inherent parallelism and removing test redundancy. Three-orders-of-magnitude improvement is achieved by applying topological testing techniques to the testing of an existing multistage interconnection network.>

A multicomputer network, called rectangular CC-banyan, is presented and formally defined. A graph-theoretic approach is used to study this network's permuting and partitioning properties. It is shown that a CC-banyan has a modular structure and hence can be recursively defined. A method for evaluation of the total number of permutations in CC-banyans is presented. Using this method, the analytical expressions for the number of permutations in CC-banyans with fan-outs of two and three are derived.>

The number of permutations performable by extra-stage multistage interconnection networks in a single pass is studied. A graph-theoretical approach is used to evaluate the multiplicity of the performable permutations. More specifically, the problem is reduced to a hypercube enumeration problem, and it is shown that there is a direct correspondence between the number of partial subgraphs of a hypercube with a given number of components, and the multiplicity of a corresponding class of permutations performable by the extra- stage network. The evaluation of these multiplicities leads to the calculation of the number of distinct permutations performable by the network.>

The quantitative relationship between speedup and communication is analyzed in terms of the ratio of the communication time to the computation time. An extension to Amdahl's law is proposed to include communication and to estimate the lower and upper bounds on speedup in multiprocessor systems. A method for estimating a response time in a multiprocessor system that incorporates the impact of communication delay is also proposed.>

A method is proposed for achieving fault tolerance by introducing a redundant stage for a special-purpose fast Fourier transform (FFT) processor. A concurrent error-detection technique, called recomputing by alternate path, is used to detect errors during normal operation. Once an error is detected, a faulty butterfly can be located with log (N+5) additional cycles. The method has 100% detection and location capability, regardless of the magnitude of the roundoff errors. A gracefully degraded reconfiguration using a redundant stage is introduced. This technique ensures a high improvement in reliability and availability. Hardware overhead is O(1/log N) with some additional comparators and switches. The method can be applied to other algorithms implementable on the butterfly structure.>

A fault-tolerant systolic sorter design is proposed. An algorithm-based fault tolerance is achieved by testing the invariants of a systolic sorter during normal operation. Transient and permanent computation errors can be detected by using error-checking code and some redundant cells. A block with a single faulty cell can be located. Small hardware overhead and negligible time overhead are shown to be the major advantages of the method. A hierarchical structure is suggested as an efficient architecture for realizing the method. An offline fault-testing method for permanent stuck-at faults is presented.>

The inherent fault tolerances of systems based on nonredundant multistage interconnection networks (MINs) is investigated. Graph models are used to describe the system, indicate faults, study their effects, and aid in mathematical formulation of these effects. Methodical terminology for defining functionality of two-sided-MIN-based multicomputer systems and specifying their fault tolerance of such systems is analyzed. The effects of a single faulty vertex and a single faulty edge are studied, and single fault tolerance, with respect to various definitions of system functionality, is evaluated. Multiple faults are analyzed. A practical example of the banyan network used in the Texas reconfigurable array computer (TRAC) and its fault tolerance capabilities are given.>

A memory called the Boolean Content Addressable Memory integrates the content-based address identification logic into the RAM comprising 1-bit words. This memory is suitable for on-chip VLSI implementation and compatible with the RAM for on-board implementation. Its application includes list management and graph traversal.

This correspondence analyzes the permuting properties of a reconfigurable multicomputer architecture based on a regular rectangular SW-banyan interconnection network with arbitrary fan-out and an arbitrary number of stages. An analytical expression for the total number of distinct permutations performable by a rectangular SW-banyan (in one pass) is derived. It is shown how the combinatorial power of a rectangular SW-banyan increases with the growth of its fan-out. It is also shown that a two-pass (unidirectional) rectangular SW-banyan network can be made rearrangeable by a proper choice of the feedback connection.

A resource allocation problem in a reconfigurable multicomputer architecture based on rectangular CC-banyan multistage interconnection network with arbitrary fanout and arbitrary number of levels is studied. Four commonly used problem structures such as ring, pipeline, broadcast and macropipeline are introduced and the mapping problem of these structures on the system model which is camparable to the resource allocation problem, is discussed. Analytic solutions to several mapping questions are presented and a new fault diagnosis method based on the solution to the problem of mapping the ring structure is given.

A comparison method for diagnosis of multiprocessor systems is introduced. Given a system of n units modeled by a linear graph, problems of finding the minimum number of comparison edges required for fault detection and fault location are solved by the use of a covering algorithm. The bounds for the number of comparison edges, the number of necessary comparisons and test cycles in fault detection and fault location in systems with n units are determined and an algorithm for an optimal comparison connection assignment is given. Simplicity and ease of implementation make the described method applicable for fault detection and location in multiprocessor systems.