Boolean Network Tomography (BNT) aims at identifying failures of internal network components by means of end-to-end monitoring paths. However, when the number of failures is not known a priori, failure identification may require a huge number of monitoring paths. We address this problem by designing a Bayesian approach that progressively selects the next path to probe on the basis of its expected information utility, conditioned on prior observations. As the complexity of the computation of posterior probabilities of node failures is exponential in the number of failed paths, we propose a polynomial-time greedy strategy which approximates these values. To consider aging of information in dynamic failure scenarios where node states can change during a monitoring period, we propose a monitoring technique based on a sliding observation window of adaptive length. By means of numerical experiments conducted on real network topologies we demonstrate the practical applicability of our approach, and the superiority of our algorithms with respect to state of the art solutions based on classic BNT as well as sequential group testing.

The multiplication of a matrix by its transpose, ATA, appears as an intermediate operation in the solution of a wide set of problems. In this paper, we propose a new cache-oblivious algorithm (AtA) for computing this product, based upon the classical Strassen algorithm as a sub-routine. In particular, we decrease the computational cost to the time required by Strassen’s algorithm, amounting to floating point operations. AtA works for generic rectangular matrices, and exploits the peculiar symmetry of the resulting product matrix for saving memory. In addition, we provide an extensive implementation study of AtA in a shared memory system, and extend its applicability to a distributed environment. To support our findings, we compare our algorithm with state-of-the-art solutions specialized in the computation of ATA. Our experiments highlight good scalability with respect to both the matrix size and the number of involved processes, as well as favorable performance for both the parallel paradigms and the sequential implementation, when compared with other methods in the literature.

Boolean Network Tomography (BNT) allows to localize network failures by means of end-to-end monitoring paths. Nevertheless, it falls short of providing efficient failure identification in real scenarios, due to the large combinatorial size of the solution space, especially when multiple failures occur concurrently. We aim at maximizing the identification capabilities of a bounded number of monitoring probes. To tackle this problem we propose a progressive approach to failure localization based on stochastic optimization, whose solution is the optimal sequence of monitoring paths to probe. We address the complexity of the problem by proposing a greedy strategy in two variants: one considers exact calculation of posterior probabilities of node failures given the observation, whereas the other approximates these values through a novel failure centrality metric. We discuss the approximation of the proposed approaches. Then, by means of numerical experiments conducted on real network topologies, we demonstrate the practical applicability of our approach. The performance evaluation evidences the superiority of our algorithms with respect to state of the art solutions based on classic Boolean Network Tomography as well as approaches based on sequential group testing.

Boolean network tomography is a powerful tool to infer the state (working/failed) of individual nodes from path-level measurements obtained by edge-nodes. We consider the problem of optimizing the capability of identifying network failures through the design of monitoring schemes. Finding an optimal solution is NP-hard and a large body of work has been devoted to heuristic approaches providing lower bounds. Unlike previous works, we provide upper bounds on the maximum number of identifiable nodes, given the number of monitoring paths and different constraints on the network topology, the routing scheme, and the maximum path length. These upper bounds represent a fundamental limit on identifiability of failures via Boolean network tomography. Our analysis provides insights on how to design topologies and related monitoring schemes to achieve the maximum identifiability under various network settings. Through analysis and experiments we demonstrate the tightness of the bounds and efficacy of the design insights for engineered as well as real networks.

The goal of System Level Formal Verification is to show system correctness notwithstanding uncontrollable events (disturbances), as for example faults, variations in system parameters, external inputs, etc. This may be achieved with an exhaustive Hardware In the Loop Simulation based approach, by c onsidering all relevant scenarios in the System Under Verification (SUV) operational environment. In this paper, we present SyLVaaS, a Web-based tool enabling Verification as a Service (VaaS). SyLVaaS implements an assume-guarantee approach to (Hardware In the Loop Simulation based) System Level Formal Verification. SyLVaaS takes as input a finite state automaton defining the SUV operational environment and computes, using parallel algorithms deployed in a cluster infrastructure, a set of highly optimised simulation campaigns, which can be executed in an embarrassingly parallel fashion (i.e., with no communication among the parallel processes) on a set of Simulink instances, using a platform independent Simulink driver downloadable from the SyLVaaS Web site. As the actual simulation is carried out at the user premises (e.g., on a private cluster), SyLVaaS allows full Intellectual Property protection of the SUV model as well as of the user verification flow. The simulation campaigns computed by SyLVaaS randomise the verification order of operational scenarios and this enables, at anytime during the parallel simulation activity, the estimation of the completion time and the computation of an upper bound to the Omission Probability, i.e., the probability that there is a yet-to-be-simulated operational scenario which violates the property under verification. This information supports graceful degradation in the verification activity. We show effectiveness of the SyLVaaS algorithms and infrastructure by evaluating the system on case studies consisting of input operational environments entailing up to 35 641 501 scenarios related to the system level verification of models from the Simulink distribution (namely, Inverted Pendulum on a Cart and Fuel Control System).

The goal of System Level Formal Verification is to show system correctness notwithstanding uncontrollable events (disturbances), as for example faults, variation in system parameters, external inputs, etc. This may be achieved with an exhaustive Hardware In the Loop Simulation based approach, by considering all relevant scenarios in the System Under Verification (SUV) operational environment. In this paper, we present SyLVaaS, a Web-based tool enabling Verification as a Service (VaaS). SyLVaaS implements an assume-guarantee approach to the verification problem outlined above. SyLVaaS takes as input a high-level model defining the SUV operational environment and computes, using parallel algorithms deployed in a cluster infrastructure, a set of highly optimised simulation campaigns, which can be executed in an embarrassingly parallel fashion on a set of Simulink instances, using a platform independent Simulink driver downloadable from the SyLVaaS Web site. As the actual simulation is carried out at the user premises (e.g., in a private cluster), SyLVaaS allows full Intellectual Property protection on the SUV model and the user verification flow. The simulation campaigns computed by SyLVaaS randomise the verification order of operational scenarios and this enables, at anytime during the parallel simulation activity, the estimation of the completion time and the computation of an upper bound to the Omission Probability, i.e., the probability that there is a yet-to-be-simulated operational scenario which violates the property under verification. This information supports graceful degradation in the verification activity. We show effectiveness of the SyLVaaS algorithms and infrastructure by evaluating the system on industry-scale input related to the verification of the Fuel Control System (FCS) model in the Simulink distribution.

We present a parallel random exhaustive Hardware In the Loop Simulation based model checker for hybrid systems that, by simulating all operational scenarios exactly once in a uniform random order, is able to provide, at any time during the verification process, an upper bound to the probability that the System Under Verification exhibits an error in a yet-to-be-simulated scenario (Omission Probability). We show effectiveness of the proposed approach by presenting experimental results on System Level Formal Verification of the Fuel Control System example in the Simulink distribution. To the best of our knowledge, no previously published model checker can exhaustively verify hybrid systems of such a size and provide at any time an upper bound to the Omission Probability.

One of the main goals of systems biology models in a health-care context is to individualise models in order to compute patient-specific predictions for the time evolution of species (e.g., hormones) concentrations. In this paper we present a statistical model checking based approach that, given an inter-patient model and a few clinical measurements, computes a value for the model parameter vector (model individualisation) that, with high confidence, is a global minimum for the function evaluating the mismatch between the model predictions and the available measurements. We evaluate effectiveness of the proposed approach by presenting experimental results on using the GynCycle model (describing the feedback mechanisms regulating a number of reproductive hormones) to compute patient-specific predictions for the time evolution of blood concentrations of E2 (Estradiol), P4 (Progesterone), FSH (Follicle-Stimulating Hormone) and LH (Luteinizing Hormone) after a certain number of clinical measurements.

The goal of System Level Formal Verification (SLFV) is to show system correctness notwithstanding uncontrollable events (such as: faults, variation in system parameters, external inputs, etc). Hardware In the Loop Simulation (HILS) based SLFV attains such a goal by considering exhaustively all relevant simulation scenarios. We present a distributed multi-core algorithm for HILS-based SLFV. Our experimental results on the Fuel Control System example in the Simulink distribution show that by using 64 machines with an 8 core processor each we can complete the SLFV activity in about 27 hours whereas a sequential approach would require more than 200 days. To the best of our knowledge this is the first time that a distributed multi-core algorithm for HILS-based SLFV is presented.

In this work we propose two different parallel versions of the software package COMPSYN, devoted to the production of syntethic seismograms. The first version consists in the parallelization of the code to run on a cluster of multicore processors and is obtained by exploiting the MPI paradigm and OpenMP API to the end of maximizing the performance on multicore processors. The second version exploits the set of GPU associated to the multicore processor cluster and uses CUDA to take advantage of the GPU's computational power. We analyze the application performance of the two different implementations by using a real case study. In particular, we obtain for the GPU version a speedup of 10x over the parallelized version running on the cluster of multicore processors. Furthermore, we can estimate about at least 100x the speedup of the GPU version using a single node of the cluster with respect to the original sequential version.

In this paper we address the problem of deploying heterogeneous mobile sensors over a target area. We show how traditional approaches designed for homogeneous networks fail when adopted in the heterogeneous operative setting.

The use of mobile sensors is of great relevance for a number of strategic applications devoted to monitoring critical areas where sensors can not be deployed manually. In these networks, each sensor adapts its position on the basis of a local evaluation of the coverage efficiency, thus permitting an autonomous deployment. Several algorithms have been proposed to deploy mobile sensors over the area of interest. The applicability of these approaches largely depends on a proper formalization of rigorous rules to coordinate sensor movements, solve local conflicts and manage possible failures of communications and devices. In this paper we introduce P&P, a communication protocol that permits a correct and efficient coordination of sensor movements in agreement with the PUSH&PULL algorithm. We deeply investigate and solve the problems that may occur when coordinating asynchronous local decisions in the presence of an unreliable transmission medium and possibly faulty devices such as in the typical working scenario of mobile sensor networks. Simulation results show the performance of our protocol under a range of operative settings, including conflict situations, irregularly shaped target areas, and node failures.

Abstract In this article we consider the three‐dimensional layout of hypercube networks. Namely, we study the problem of laying hypercube networks out on the three‐dimensional grid with the properties that all nodes are represented as rectangular slices and lie on two opposite sides of the bounding box of the layout volume. We present both a lower bound and a layout method, providing an upper bound on the layout volume and the maximum wire‐length of the hypercube network. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 1–8 2006

A self-routing multi-logN permutation network is presented and studied. This network has 3log/sub 2/ N-2 depth and N(log/sub 2//sup /spl gamma//N)(3log/sub 2/, N-2)/2 nodes, where N is the number of network inputs and /spl gamma/ a constant very close to 1. A parallel routing algorithm runs in 3log/sub 2/N-2 time on this network. The overall system (network and algorithm) can work in pipeline and it is asymptotically nonblocking in the sense that its blocking probability vanishes when N increases, hence the quasi-totality of the information synchronously arrives in 3log/sub 2/N-2 steps at the network outputs. This network presents very good fault tolerance, a modular architecture, and it is suitable for information exchange in very large scale parallel processors and communication systems.>

A self-routing multi-log-N permutation network is presented and studied. This network has log/sub 2/N depth and N(log/sub 2//sup 2/N+log/sub 2/N)/2 nodes, where N is the number of network inputs. Its parallel routing algorithm runs in log/sub 2/N time. The network architecture guarantees that only a negligible quantity of information is blocked, while the quasi-totality of the information synchronously reaches the network outputs in log/sub 2/N steps. This network works in pipeline, it has a modular architecture suitable for very large N, it can be used as very high performance fast packet switching fabric, and it is suitable for information exchange in very-large-scale multiprocessor systems.>