We consider a problem where a physical quantity is repeatedly measured by replicated devices, yielding a stream of numerical data. Data are stored within the measuring devices and sporadically retrieved by a user. To avoid data losses due to large data streams with insufficient memory, the data are split into fragments, each of which is a compressed encoding of a number in the stream, and different fragments are stored in different, replicated devices. The devices are not allowed to communicate with each other, and they produce the local streams of fragments from independent measurements. Given the independence of measurements, the fragments are corrupted by independent errors, which are likely to be small integers, although errors of unbounded magnitude may also occur due to failures or to interferences. As devices may fail, or communication may be unreliable, the user may be unable to download fragments from some of the replicated devices, leading to fragment erasures. Our approach to the problem is to encode the data in a Residue Number System with Nonpairwise-Prime Moduli, named D-RNS-NPM. Withnmoduli andnresidue digits, every replicated device is tied to a different modulus, with which it produces and stores a residue digit (i.e., a fragment) from the local measurement. Assuming an upper boundz, withzn, to the number of erasures, we show that the D-RNS-NPM guarantees the reconstruction of any number from a subset of at leastn-zfragments. If fragments bear errors, whose magnitude is unrestricted for at most one error and upper bounded by a small δ for the others, reconstruction is within an approximation of ±δ, and this property is retained when errors cannot be detected due to the unbounded error multiplicity. The time complexity of the decoding algorithm is polynomial. This problem appears to be relevant in wireless sensor networks, and an application in this area is envisioned.

A novel routing protocol for wireless mobile ad hoc networks, named virtual distance vector (VDV), is presented. This protocol augments AODV with a virtual overlay, unrelated to the actual network topology, which accounts for routes kept proactively by mobile nodes acting as scouts toward the nodes in the respective subsets of peers. This provides routes from any source to any destination node, along which data packets can be routed without the need of preliminary route discovery. The intended goal of VDV was to reduce the average end-to-end delivery time of data packets. VDV has been evaluated against AODV by running extensive simulation under OPNET Modeler. Simulation confirmed the expected advantage of VDV, which increases with increasing node mobility and average route length. The confidence intervals of reported data showed that VDV fits better the dynamic nature of the network.

System-level diagnosis aims at the identification of faulty units in a system by the analysis of the system syndrome, that is, the outcomes of a set of interunit tests. For any given syndrome, it is possible to produce a correct (although possibly incomplete) diagnosis of the system if the number of faults is below a syndrome-dependent bound and the degree of diagnosis completeness, that is, the number of correctly diagnosed units, is also dependent on the actual syndrome sigma. The worst-case diagnosis completeness is a syndrome-independent bound that represents the minimum number of units that the diagnosis algorithm correctly diagnoses for any syndrome. This paper provides a lower bound to the worst-case diagnosis completeness for regular graphs for which vertex- isoperimetric inequalities are known and it shows how this bound can be applied to toroidal grids. These results prove a previous hypothesis about the influence of two topological parameters of the diagnostic graph, that is, the bisection width and the diameter, on the degree of diagnosis completeness.

In this paper we address the problem of Denial of Service (DoS) mitigation in multicast environment. The contribution of the paper is twofold: first, we introduce an optimization (PMT) on the Merkle tree distillation codes by leveraging the implicit redundancy of a Merkle tree representation. Second, we devise a new algorithm(CECInA) for encoding/decoding that mitigates DoS attacks on the end user device and reduces the buffer size in case of DoS. In particular, according to the type of DoS attack, CECInA achieves either complexity or buffering savings. This attack mitigation capability is not a feature offered by state of the art algorithms. Furthermore CECInA is particularly efficient when used in conjunction with PMT. We derive and plot analytical results that indicates that the proposed solutions are effective. Hence, CECInA can be a viable solution to mitigate DoS in multicast, particularly suited for contexts in which end-user devices are resource constrained. As for PMT, note that it is a general technique that can be adopted independently from CECInA.

This paper addresses the problem of the identification of faulty units in symmetric systems under the diagnostic model proposed by Barsi, Grandoni and Maestrini (hence called the BGM model). The paper introduces and evaluates an algorithm named Diagnosis Algorithm for Symmetric Systems under the BGM model (DABS). It is shown that DABS provides a diagnosis unconditionally correct although possibly incomplete. A measure of diagnosis incompleteness IDeg(t) has been defined as the quotient between the number of suspect units (i.e. the units that DABS is unable to identify as either good or faulty) and the number of system units. IDeg(t) is evaluated over the set of syndromes deriving from at most t faults under the BGM model. A general approach to the evaluation of IDeg(t) in symmetric systems is introduced, and tight bounds to IDeg(t) are derived for square toroidal grids and hypercubes. This bound is O(t/n) in the case of square toroidal grids of n units.

This paper introduces a distributed data storage for mobile, wireless networks based on a peer-to-peer paradigm. The distributed storage provides support to create and share files under a write-once model, and ensures at the same time data confidentiality and dependability by encoding files in a Redundant Residue Number System. More specifically files are partitioned into records and each record in encoded separately as (h+r)-tuples of data residues using h+r moduli. In turn, the residues are distributed among the mobiles in the network. Dependability is ensured since data can be reconstructed in the presence of up to s≤r residue erasures, combined with up to ¨ o 2 s r − corrupted residues, and data confidentiality is ensured since recovering the original information requires knowledge of the entire set of moduli.

The problem of identifying the faulty units in regularly interconnected systems is addressed. The diagnosis is based on mutual tests of units, which are adjacent in the "system graph" describing the interconnection structure. This paper evaluates an algorithm named EDARS (Efficient Diagnosis Algorithm for Regular Structures). The diagnosis provided by this algorithm is provably correct and almost complete with high probability. Diagnosis correctness is guaranteed if the cardinality of the actual fault set is below a "syndrome-dependent bound," asserted by the algorithm itself along with the diagnosis. Evaluation of EDARS relies upon extensive simulation which covered grids, hypercubes, and cube-connected cycles (CCC). Simulation experiments showed that the degree of the system graph has a strong impact over diagnosis completeness and affects the "syndrome-dependent bound," ensuring correctness. Furthermore, a comparative analysis of the performance of EDARS, with hypercubes and CCCs on one side and grids of the same size and degree on the other side, showed that diameter and bisection width of the system graph also influence the diagnosis correctness and completeness.

A new diagnosis algorithm for square grids is introduced. The algorithm always provides correct diagnosis if the number of faulty processors is below T, a bound with T /spl epsi//spl Theta/(n/sup 2/3/), which was derived by worst-case analysis. A more effective tool to validate the diagnosis correctness is the syndrome dependent bound T/sub /spl sigma// with T/sub /spl sigma///spl ges/T, asserted by the diagnosis algorithm itself for every given diagnosis experiment. Simulation studies provided evidence that the diagnosis is complete or almost complete if the number of faults is below T. The fraction of units which cannot be identified as either faulty or nonfaulty remains relatively small as long as the number of faults is below n/3 and, as long as the number of faults is below n/2, the diagnosis is correct with high probability.

Introduces EDARS (Efficient Diagnosis Algorithm for Regular Structures). The algorithm provides a diagnosis which is correct, but possibly incomplete, if the cardinality of the actual fault set is below a "syndrome-dependent bound" asserted by the algorithm itself. The time complexity of EDARS is O(nt) when executed on t-regular structures of size n. The correctness and the completeness degree of EDARS were evaluated by means of simulation. Grids, hypercubes and cube-connected cycle (CCC) structures were considered. Simulation results with grid structures showed a strong influence of structure degree over diagnosis performance. Furthermore, comparisons of simulation results obtained with hypercubes, CCCs and grids of the same size and degree showed that diameter and bisection width also appear to influence the performance of EDARS, particularly with respect to diagnosis completeness.

A novel approach to the diagnosis of hypercubes, called self-validating diagnosis (SVD), is introduced. An algorithm bared on this approach, called the SVD algorithm, is presented and evaluated. Given any fault set and the resulting syndrome, the algorithm returns a diagnosis and a syndrome-dependent bound, T/sub /spl sigma//, with the property that the diagnosis is correct (although possibly incomplete) if the actual number of faulty units is less than T/sub /spl sigma//. The average of T/sub /spl sigma// is very large and the diagnosis is almost complete even when the percentage of faulty units in the system approaches 50%. Moreover, the diagnosis correctness can be validated deterministically by individually probing a very small number of units. These results suggest that the SVD algorithm is suitable for applications requiring a large degree of diagnosability, as is the case for wafer-scale testing of VLSI chips, where the percentage of faulty units may be as large us 50%.

This paper introduces a diagnosing algorithm for bidimensional processor arrays, where processors are interconnected in horizontal and vertical meshes. For the purpose of diagnosis, the array is considered to be partitioned in square clusters of processors. The algorithm is based on interprocessor tests, using a comparison model. The algorithm, which is divided in four steps, called intracluster diagnosis, interluster diagnosis, fault-free core identification and augmentation, identifies a set of non-faulty and a set of faulty units. The diagnosis is proved to be correct in the worst case, assuming that the actual number of faulty processors is no more that T(N), an increasing function of the number N of processors. It is shown that T(N) is O(N/sup 2/3/). Although correct, the diagnosis is generally incomplete. However, using probabilistic techniques, it is shown that the diagnosis is very likely to be complete under the same limitations which ensure correctness in the worst case.

A VLSI chip for performing relational data base operations is proposed. The chip is a tree of processors (TOP), where each chip has elementary storage and processing capabilities. A relation will be stored in the lowest levels of a TOP. More precisely, every m-tuple will occupy a subtree whose root is s= [log2(m+1)] =1 levels above the leaves. Denoting by h the height of the tree, the upper h-s levels will be used for routing and bookkeeping purposes. A number of basic operations such as allocate and deallocate subtrees, insert and compare m-tuples etc., are defined for the TOP's. Relational operations are effectively performed as simple combinations of basic operations. The architecture of a data base machine based on TOP's is also sketched. Such a machine is feasible with the current VLSI technology and could become attractive in few years if density and performance of VLSI keep improving at the current rate.

The idea of adding a magnitude index to the residue representation of numbers is reconsidered. The range of a given residue number system is supposed to be divided into intervals of equal width, and the magnitude index of a number X is defined as an integer locating X into one of such intervals. It is shown that the redundancy implied by the use of the magnitude index allows error detection or correction, and the redundancy requirements to detect or correct single residue digit errors are the same as in redundant residue number systems and in product codes in residue number systems. In addition, these codes allow detection of any error affecting the residue representation, provided that the magnitude of the error exceeds a given threshold, and, whenever an error is detected, it is possible to replace the wrong number with an approximation of the correct number.

Two classes of arithmetic codes constructed in residue number systems are considered, and decoding algorithms based on the convergents of continued fractions are presented. The advantages of the proposed algorithms over those previously known are discussed.

The problem of automatic fault diagnosis of systems decomposed into a number of interconnected units is considered by using a simplified version of the diagnostic model introduced by Preparata et al. The model used in this paper is supposed to be a realistic representation of systems where each unit has a considerable computational capability. For any system of n units whose set of testing links is given, necessary and sufficient conditions for t-diagnosability are presented in both cases of one-step diagnosis and diagnosis with repair, and it is shown that the procedure for diagnosis with repair has very small complexity. The problem of optimal assignment of testing links in order to achieve a given diagnosability is also considered and classes of optimal t-diagnosable systems are presented for arbitrary values of t in both cases of one-step diagnosis and diagnosis with repair.

The arithmetic error detecting and correcting capabilities of product (AN) codes in residue number systems (RNS) are described. The redundancy necessary and sufficient to allow single residue digit error detection or correction is determined, under the hypothesis that the error affects either an arbitrary legitimate number or a number in overflow. It is shown that single-bit errors are also correctable, provided that the residue digits are conveniently encoded. Two different approaches to this problem are discussed. Simple procedures for error detection and correction are presented, and it is shown that the additive overflow detection is a by-product of such procedures. Proofs and examples are given.

The error correcting properties of the redundant residue number systems (RNS) are investigated through a more natural a approach than was previously known. The necessary and sufficient condition for the correction of a given error affecting a single residue digit of any legitimate number in an RRNS is determined. The minimal redundancy allowing the correction of the whole class of the single residue digit errors is derived and an efficienit procedure for error correction is given. Moreover, it is shown that a smaller redundancy and a single redundant modulus may allow the correction of certain important subclasses of single residue digit errors, e.g., the set of errors affecting a single bit in the code. Examples are given.

TOPI is a special-purpose computer for the synthesis and analysis of Boolean functions. The algorithms executed by TOPI have been developed specifically for this computer and are an evolution of the iterative consensus method. They allow the determination and classification of the prime implicants of a given Boolean function, as well as the determination of a number of irredundant normal coverings. The computer capabilities are limited to single-output functions of a maximum of 15 variables, or to n-output functions of a maximum of 15-n variables.