15102047
Separation of random number generation and resolvability
We consider the problem of determining when a given source can be used to approximate the output due to any input to a given channel. We provide achievability and converse results for a general source and channel. For the special case of a full-rank discrete memoryless channel we give a stronger converse result than we can give for a general channel.
1896551
Source Codes as Random Number Generators
A random number generator generates fair coin flips by processing deterministically an arbitrary source of nonideal randomness. An optimal random number generator generates asymptotically fair coin flips from a stationary ergodic source at a rate of bits per source symbol equal to the entropy rate of the source. Since optimal noiseless data compression codes produce incompressible outputs, it is natural to investigate their capabilities as optimal random number generators. We show under general conditions that optimal variable-length source codes asymptotically achieve optimal variable-length random bit generation in a rather strong sense. In particular, we show in what sense the Lempel-Ziv (1978) algorithm can be considered an optimal universal random bit generator from arbitrary stationary ergodic random sources with unknown distributions.
11400186
On probably correct classification of concepts
We consider the problem of classifying an unknown concept into one of two subclasses of concepts. Specifically, if C is a concept class and Co and Cl are two disjoint subsets of C, given an unknown c E Co U Cl we wish to decide whether c c Co or c E Cl based on a set of random examples. We consider both uniform and non-uniform probably correct classification for which the number of samples is or is not required to be independent of c, respectively. For both cases, we obtain necessary and sufficient conditions on Co and Cl that allow probably correct classification. The conditions obtained are in terms of separability and/or coverability conditions on the classes Co and Cl. Furthermore, in the non-uniform case we show that this is equivalent to classification in the limit. Several examples of the applicability of our results are also provided.
15475360
Estimating correspondence in digital video
This paper addresses several estimation problems involving correspondence in digital video. We present three cases, in order of increasing complexity: affine transformations, projective transformations, and general correspondence. We review some recent research in the first two cases and present a new framework for discussing the third case. We also discuss how to use the formalism of correspondence graphs to ensure that any estimated correspondence is physically valid.
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. >
877181
Density Estimation from an Individual Numerical Sequence
The article considers univariate density estimation from an individual numerical sequence. It is assumed that (i) the limiting relative frequencies of the numerical sequence are governed by an unknown density, and (ii) there is a known upper bound for the variation of the density an an increasing sequence of intervals. A simple estimation scheme is proposed, and its L/sub 1/ consistency is established when (i) and (ii) apply. In addition it is shown that there is no consistent estimation scheme for the set of individual sequences satisfying only condition (i).
33040079
Resettable vector clocks
Vector clocks (VC) are an inherent component of a rich class of distributed applications. In this paper, we first consider the problem of realistic implementation-more specifically, bounded-space and fault-tolerant-of applications that use vector clocks (VC). To this end, we generalize the notion of VC to resettable vector clocks (RVC), and provide a realistic implementation of RVC. Further, we identify an interface contract under which our RVC implementation can be substituted for VC in client applications, without affecting the client's correctness. This interface contract is designed for phase-based applications that provide certain communication guarantees. Based on such substitution and the use of the interface contract, we show how to transform the client so that it is itself realistically implemented. We illustrate our method in the context of Ricart-Agrawala's mutual exclusion program and Garg-Chase's predicate detection program.
12287966
Complexity issues in automated synthesis of failsafe fault-tolerance
We focus on the problem of synthesizing failsafe fault-tolerance where fault-tolerance is added to an existing (fault-intolerant) program. A failsafe fault-tolerant program satisfies its specification (including safety and liveness) in the absence of faults. However, in the presence of faults, it satisfies its safety specification. We present a somewhat unexpected result that, in general, the problem of synthesizing failsafe fault-tolerant distributed programs from their fault-intolerant version is NP-complete in the state space of the program. We also identify a class of specifications, monotonic specifications, and a class of programs, monotonic programs, for which the synthesis of failsafe fault-tolerance can be done in polynomial time (in program state space). As an illustration, we show that the monotonicity restrictions are met for commonly encountered problems, such as Byzantine agreement, distributed consensus, and atomic commitment. Furthermore, we evaluate the role of these restrictions in the complexity of synthesizing failsafe fault-tolerance. Specifically, we prove that if only one of these conditions is satisfied, the synthesis of failsafe fault-tolerance is still NP-complete. Finally, we demonstrate the application of monotonicity property in enhancing the fault-tolerance of (distributed) nonmasking fault-tolerant programs to masking.
11497337
Secret instantiation in ad-hoc networks
Abstract In this paper, we focus our attention on the problem of assigning initial secrets to users in ad-hoc network (respectively, sensors in a sensor network) so that they can use those secrets to ensure authentication and privacy during their communication. The goal of this assignment is to ensure that any two users can communicate securely with each other even though each user maintains only a small number of secrets. With this motivation, we present a protocol that maintains O ( n ) secrets per user where n is the number of users in the system. We show that our secret distribution protocol suffices for privacy and authentication as well as secure multihop communication between two users. Furthermore, we show that the number of secrets maintained in this protocol is within a constant factor of the optimal. For the case where user capability prevents them from maintaining the necessary secrets, we propose two probabilistic protocols that maintain O(log n) secrets and where the probability of security compromise between two users is inversely proportional to the number of secrets they maintain. Thus, our protocols provide a continuum where the level of privacy and authentication depends upon user requirements and capabilities.
14446337
Multitolerant Barrier Synchronization
Abstract We designed a multitolerant program for synchronizing the phases of concurrent processes. The tolerances of the program enable processes to: (i) execute all phases correctly in the presence of faults that corrupt the process state in a detectable manner, and (ii) execute only a minimum possible number of phases incorrectly before resuming correct computation in the presence of faults that corrupt the process state in an undetectable manner.
8636414
A Case Study on Prototyping Power Management Protocols for Sensor Networks
Power management is an important problem in battery powered sensor networks as the sensors are required to operate for a long time (usually, several weeks to several months). One of the challenges in developing power management protocols for sensor networks is prototyping. Specifically, existing programming platforms for sensor networks (e.g., nesC/TinyOS) use an event-driven programming model and, hence, require the designers to be responsible for stack management, buffer management, flow control, etc. Therefore, the designers simplify prototyping their solutions either by implementing their own discrete event simulators or by modeling them in specialized simulators. To enable the designers to prototype power management protocols in target platform (e.g., nesC/TinyOS), in this paper, we use ProSe, a programming tool for sensor networks. ProSe enables the designers to specify their programs in simple abstract models while hiding low-level challenges of sensor networks and programming-level challenges. As a case study, in this paper, we specify a power management protocol with ProSe, automatically generate the corresponding nesC/TinyOS code, and evaluate its performance. Based on the performance results, we expect that ProSe enables the designers to rapidly prototype, quickly deploy, and easily evaluate their protocols.