8320156
Resettable vector clocks
Vector clocks (VC) are an inherent component of a rich class of distributed applications. In this paper, we consider the problem of realistic —more specifically, bounded-space and fault-tolerant— implementation of these client applications. 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. Based on such substitution, we show how to transform the client so that it is itself realistically implemented; we demonstrate our method in the context of Ricart-Agrawala's mutual exclusion program.
52887342
Low-cost fault-tolerance in barrier synchronizations
We show how fault-tolerance can be effectively added to several types of faults in program computations that use barrier synchronization. We divide the faults that occur in practice into two classes, detectable and undetectable, and design a fully distributed program that tolerates the faults in both classes. Our program guarantees that every barrier is executed correctly even if detectable faults occur, and that eventually every barrier is executed correctly even if undetectable faults occur. Via analytical as well as simulation results we show that the cost of adding fault-tolerance is low, in part by comparing the times required by our program with that required by the corresponding fault-intolerant counterpart.
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.
6279302
A line in the sand: a wireless sensor network for target detection, classification, and tracking
Intrusion detection is a surveillance problem of practical import that is well suited to wireless sensor networks. In this paper, we study the application of sensor networks to the intrusion detection problem and the related problems of classifying and tracking targets. Our approach is based on a dense, distributed, wireless network of multi-modal resource-poor sensors combined into loosely coherent sensor arrays that perform in situ detection, estimation, compression, and exfiltration. We ground our study in the context of a security scenario called "A Line in the Sand" and accordingly define the target, system, environment, and fault models. Based on the performance requirements of the scenario and the sensing, communication, energy, and computation ability of the sensor network, we explore the design space of sensors, signal processing algorithms, communications, networking, and middleware services. We introduce the influence field, which can be estimated from a network of binary sensors, as the basis for a novel classifier. A contribution of our work is that we do not assume a reliable network; on the contrary, we quantitatively analyze the effects of network unreliability on application performance. Our work includes multiple experimental deployments of over 90 sensor nodes at MacDill Air Force Base in Tampa, FL, as well as other field experiments of comparable scale. Based on these experiences, we identify a set of key lessons and articulate a few of the challenges facing extreme scaling to tens or hundreds of thousands of sensor nodes.
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.
1711572
Designing masking fault-tolerance via nonmasking fault-tolerance
Masking fault-tolerance guarantees that programs continually satisfy their specification in the presence of faults. By way of contrast, nonmasking fault-tolerance does not guarantee as much: it merely guarantees that when faults stop occurring, program executions converge to states from where programs continually (re)satisfy their specification. In this paper, we show that a practical method to design masking fault-tolerance is to first design nonmasking fault-tolerance and to then transform the nonmasking fault-tolerant program minimally so as to achieve masking fault-tolerance. We demonstrate this method by designing novel fully distributed programs for termination detection, mutual exclusion, and leader election, that are masking tolerant of any finite number of process fail-stops and/or repairs.
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. >
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.
1329510
Noise Conditions for Prespecified Convergence Rates of Stochastic Approximation Algorithms
We develop deterministic necessary and sufficient conditions on individual noise sequences of a stochastic approximation algorithm for the error of the iterates to converge at a given rate. Specifically, suppose {/spl rho//sub n/} is a given positive sequence converging monotonically to zero. Consider a stochastic approximation algorithm x/sub n+1/=x/sub n/-a/sub n/(A/sub n/x/sub n/-b/sub n/)+a/sub n/e/sub n/, where {x/sub n/} is the iterate sequence, {a/sub n/} is the step size sequence, {e/sub n/} is the noise sequence, and x* is the desired zero of the function f(x)=Ax-b. Then, under appropriate assumptions, we show that x/sub n/-x*=o(/spl rho//sub n/) if and only if the sequence {e/sub n/} satisfies one of five equivalent conditions. These conditions are based on well-known formulas for noise sequences: Kushner and Clark's (1978) condition, Chen's (see Proc. IFAC World Congr., p.375-80, 1996) condition, Kulkarni and Horn's (see IEEE Trails Automat. Contr., vol.41, p.419-24, 1996) condition, a decomposition condition, and a weighted averaging condition. Our necessary and sufficient condition on {e/sub n/} to achieve a convergence rate of {/spl rho//sub n/} is basically that the sequence {e/sub n///spl rho//sub n/} satisfies any one of the above five well-known conditions. We provide examples to illustrate our result. In particular, we easily recover the familiar result that if a/sub n/=a/n and {e/sub n/} is a martingale difference process with bounded variance, then x/sub n/-x*=o(n/sup -1/2/(log(n))/sup /spl beta//) for any /spl beta/>1/2.
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.
53223319
Learning Changing Concepts by Exploiting the Structure of Change
This paper examines learning problems in which the target function is allowed to change. The learner sees a sequence of random examples, labelled according to a sequence of functions, and must provide an accurate estimate of the target function sequence. We consider a variety of restrictions on how the target function is allowed to change, including infrequent but arbitrary changes, sequences that correspond to slow walks on a graph whose nodes are functions, and changes that are small on average, as measured by the probability of disagreements between consecutive functions. We first study estimation, in which the learner sees a batch of examples and is then required to give an accurate estimate of the function sequence. Our results provide bounds on the sample complexity and allowable drift rate for these problems. We also study prediction, in which the learner must produce online a hypothesis after each labelled example and the average misclassification probability over this hypothesis sequence should be small. Using a deterministic analysis in a general metric space setting, we provide a technique for constructing a successful prediction algorithm, given a successful estimation algorithm. This leads to sample complexity and drift rate bounds for the prediction of changing concepts.