386
Density evolution for asymmetric memoryless channels
Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution has been widely and successfully applied to different channels, including binary erasure channels (BECs), binary symmetric channels (BSCs), binary additive white Gaussian noise (BiAWGN) channels, etc. This paper generalizes density evolution for asymmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g., z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed-size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation (BP) algorithm even when only symmetric channels are considered. Hence, the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels.
7846439
Universal lossless source coding with the Burrows Wheeler Transform
The Burrows Wheeler transform (1994) is a reversible sequence transformation used in a variety of practical lossless source-coding algorithms. In each, the BWT is followed by a lossless source code that attempts to exploit the natural ordering of the BWT coefficients. BWT-based compression schemes are widely touted as low-complexity algorithms giving lossless coding rates better than those of the Ziv-Lempel codes (commonly known as LZ'77 and LZ'78) and almost as good as those achieved by prediction by partial matching (PPM) algorithms. To date, the coding performance claims have been made primarily on the basis of experimental results. This work gives a theoretical evaluation of BWT-based coding. The main results of this theoretical evaluation include: (1) statistical characterizations of the BWT output on both finite strings and sequences of length n /spl rarr/ /spl infin/, (2) a variety of very simple new techniques for BWT-based lossless source coding, and (3) proofs of the universality and bounds on the rates of convergence of both new and existing BWT-based codes for finite-memory and stationary ergodic sources. The end result is a theoretical justification and validation of the experimentally derived conclusions: BWT-based lossless source codes achieve universal lossless coding performance that converges to the optimal coding performance more quickly than the rate of convergence observed in Ziv-Lempel style codes and, for some BWT-based codes, within a constant factor of the optimal rate of convergence for finite-memory sources.
9782780
A paradigm for class identification problems
The following problem arises in many applications involving classification, identification, and inference. There is a set of objects X, and a particular x /spl isin/ X is chosen (unknown to us). Based on information obtained about x in a sequential manner, one wishes to decide whether x belongs to one class of objects A/sub 0/ or a different class of objects A/sub 1/. The authors study a general paradigm applicable to a broad range of problems of this type, which they refer to as problems of class identification or discernibility. They consider various types of information sequences, and various success criteria including discernibility in the limit, discernibility with a stopping criterion, uniform discernibility, and discernibility in the Cesaro sense. They consider decision rules both with and without memory. Necessary and sufficient conditions for discernibility are provided for each case in terms of separability conditions on the sets A/sub 0/ and A/sub 1/. They then show that for any sets A/sub 0/ and A/sub 1/, various types of separability can be achieved by allowing failure on appropriate sets of small measure. Applications to problems in language identification, system identification, and discrete geometry are discussed. >
1752947
Learning decision rules for pattern classification under a family of probability measures
In this paper, uniformly consistent estimation (learnability) of decision rules for pattern classification under a family of probability measures is investigated. In particular, it is shown that uniform boundedness of the metric entropy of the class of decision rules is both necessary and sufficient for learnability under each of two conditions: (i) the family of probability measures is totally bounded, with respect to the total variation metric, and (ii) the family of probability measures contains an interior point, when equipped with the same metric. In particular, this shows that insofar as uniform consistency is concerned, when the family of distributions contains a total variation neighborhood, nothing is gained by this knowledge about the distribution. Then two sufficient conditions for learnability are presented. Specifically, it is shown that learnability with respect to each of a finite collection of families of probability measures implies learnability with respect to their union; also, learnability with respect to each of a finite number of measures implies learnability with respect to the convex hull of the corresponding families of uniformly absolutely continuous probability measures.
6063474
PAC learning with generalized samples and an application to stochastic geometry
In this paper, we introduce an extension of the standard PAC learning model which allows the use of generalized samples. We view a generalized sample as a pair consisting of a functional on the concept class together with the value obtained by the functional operating on the unknown concept. It appears that this model can be applied to a number of problems in signal processing and geometric reconstruction to provide sample size bounds under a PAC criterion. We consider a specific application of the model to a problem of curve reconstruction, and discuss some connections with a result from stochastic geometry.
7606261
Rates of convergence of nearest neighbor estimation under arbitrary sampling
Rates of convergence for nearest neighbor estimation are established in a general framework in terms of metric covering numbers of the underlying space. The first result is to find explicit finite sample upper bounds for the classical independent and identically distributed (i.i.d.) random sampling problem in a separable metric space setting. The convergence rate is a function of the covering numbers of the support of the distribution. For example, for bounded subsets of R/sup r/, the convergence rate is O(1/n/sup 2/r/). The main result is to extend the problem to allow samples drawn from a completely arbitrary random process in a separable metric space and to examine the performance in terms of the individual sample sequences. The authors show that for every sequence of samples the asymptotic time-average of nearest neighbor risks equals twice the time-average of the conditional Bayes risks of the sequence. Finite sample upper bounds under arbitrary sampling are again obtained in terms of the covering numbers of the underlying space. In particular, for bounded subsets of R/sup r/ the convergence rate of the time-averaged risk is O(1/n/sup 2/r/). The authors then establish a consistency result for k/sub n/-nearest neighbor estimation under arbitrary sampling and prove a convergence rate matching established rates for i.i.d. sampling. Finally, they show how their arbitrary sampling results lead to some classical i.i.d. sampling results and in fact extend them to stationary sampling. The framework and results are quite general while the proof techniques are surprisingly elementary. >
37856387
Collision-Free Communication in Sensor Networks
In this paper, we provide a stabilizing solution for collision-free diffusion in sensor networks. Such diffusions are often necessary in sensor networks when information from one sensor needs to be communicated to other sensors that satisfy certain geographic properties. Our solution deals with several difficulties, e.g., unidirectional links, unreliable links, long links, failed sensors, and sensors that are sleeping in order to save energy, that occur in sensor networks. It also ensures that there are no collisions during the diffusion and that the time required for the diffusion is O(D) where D is the diameter of the network. Moreover, while the solution can be applied to an arbitrary topology, it is more suitable for a commonly occurring topology, a two-dimensional grid. 
 
We show how our solution for collision-free diffusion can be used for time-division multiplexing (TDM) in sensor networks. TDM ensures that the message communication (other than the messages sent by diffusion) among sensors is also collision-free. While collision-free diffusion and time-division multiplexing are interdependent, we show how both these properties can be achieved simultaneously. Our algorithms are stabilizing fault-tolerant, i.e., collision-free diffusion and time-division multiplexing are restored even if the system reaches an arbitrary state where the sensors are corrupted or improperly initialized.
1315797
Correctness of Component-Based Adaptation
Long running applications often need to adapt due to changing requirements or changing environment. Typically, such adaptation is performed by dynamically adding or removing components. In these types of adaptation, components are often added to or removed from multiple processes in the system. While techniques for such adaptations have been extensively discussed in the literature, there is a lack of systematic methods to ensure the correctness of dynamic adaptation. To redress this deficiency, in this paper, we propose a new method, based on the concept of proof lattice, for verifying correctness of dynamic adaptation in a distributed application. We use transitional-invariant lattice to verify correctness of adaptation. As an illustration of this method, we show how correctness of dynamic adaptation is obtained in the context of a message communication application.
35260529
Transformations for Write-All-with-Collision Model
In this paper, we consider a new atomicity model, write all with collision (WAC), and compare it with existing models considered in the literature. This model captures the computations in sensor networks. We show that it is possible to transform a program from WAC model into a program in read/write model, and vice versa. Further, we show that the transformation from WAC model to read/write model is stabilization preserving, and the transformation from read/write model to WAC model is stabilization preserving for timed systems. In the transformation from read/write model to WAC model, if the system is untimed (asynchronous) and processes are deterministic then under reasonable assumptions, we show that (1) the resulting program in WAC model can allow at most one process to execute, and (2) the resulting program in WAC model cannot be stabilizing. In other words, if a deterministic program cannot read then it is important that it can tell time.
616074
Enhancing the fault-tolerance of nonmasking programs
In this paper we focus on automated techniques to enhance the fault-tolerance of a nonmasking fault-tolerant program to masking. A masking program continually satisfies its specification even if faults occur. By contrast, a nonmasking program merely guarantees that after faults stop occurring, the program recovers to states from where it continually satisfies its specification. Until the recovery is complete, however a nonmasking program can violate its (safety) specification. Thus, the problem of enhancing fault-tolerance from nonmasking to masking requires that safety be added and recovery be preserved. We focus on this enhancement problem for high atomicity programs-where each process can read all variables-and for distributed programs-where restrictions are imposed on what processes can read and write. We present a sound and complete algorithm for high atomicity programs and a sound algorithm for distributed programs. We also argue that our algorithms are simpler than previous algorithms, where masking fault-tolerance is added to a fault-intolerant program. Hence, these algorithms can partially reap the benefits of automation when the cost of adding masking fault-tolerance to a fault-intolerant program is high. To illustrate these algorithms, we show how the masking fault-tolerant programs for triple modular redundancy and Byzantine agreement can be obtained by enhancing the fault-tolerance of the corresponding nonmasking versions. We also discuss how the derivation of these programs is simplified when we begin with a nonmasking fault-tolerant program.
2311914
Exploiting Symbolic Techniques in Automated Synthesis of Distributed Programs with Large State Space
Automated formal analysis methods such as program verification and synthesis algorithms often suffer from time complexity of their decision procedures and also high space complexity known as the state explosion problem. Symbolic techniques, in which elements of a problem are represented by Boolean formulae, are desirable in the sense that they often remedy the state explosion problem and time complexity of decision procedures. Although symbolic techniques have successfully been used in program verification, their benefits have not yet been exploited in the context of program synthesis and transformation extensively. In this paper, we present a symbolic method for automatic synthesis of fault-tolerant distributed programs. Our experimental results on synthesis of classical fault-tolerant distributed problems such as Byzantine agreement and token ring show a significant performance improvement by several orders of magnitude in both time and space complexity. To the best of our knowledge, this is the first illustration where programs with large state space (beyond 2100) is handled during synthesis.