Explore the vast range of titles available.

Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient fault can cause vast disruption in the system before legitimacy is reached. This paper introduces the notion of fault-containment to address this particular weakness of self-stabilizing systems. Informally, a fault-containing self-stabilizing protocol, in addition to providing self- stabilization, contains the effects of faults. This ensures that disruption during recovery from faults, is proportional to the extent of the faults. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. The main result of the paper is a transformer that converts any non-reactive self-stabilizing protocol into an equivalent fault-containing self-stabilizing protocol that can repair any single fault in the system in O(1) time. For a large class of input protocols, the corresponding output protocols produced by the transformer have O(1) space overhead. The small time and space overhead make the fault-containing self-stabilizing protocol a practical alternative to the original self-stabilizing protocol. The transformer is based on a novel stabilizing timer paradigm that significantly simplifies the task of fault-containment. [PUBLICATION ABSTRACT]

The coverage problem in wireless sensor networks deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of line segments with minimum number of sensors. A line segment ℓ is said to be 1-covered if it intersects the sensing region of at least one among the sensors distributed in a bounded rectangular region R . We assume that the sensing radius of each sensor is uniform. The problem of finding the minimum number of sensors needed to 1-cover each member in a given set of line segments in R is NP-hard. We propose two constant factor approximation algorithms and a PTAS (polynomial time approximation scheme) for the problem for 1-covering a set of axis-parallel line segments. We also show that a PTAS exists for 1-covering a set of arbitrarily oriented line segments in R where the lengths of the line segments are bounded within a constant factor of the sensing radius of each sensor. Finally, we propose a constant factor approximation algorithm for k-covering axis-parallel line segments such that sensors maintain a minimum separation among them.

Temporal graphs are graphs where the topology and/or other properties of the graph change with time. They have been used to model applications with temporal information in various domains. Problems on static graphs become more challenging to solve in temporal graphs because of dynamically changing topology, and many recent works have explored graph problems on temporal graphs. In this paper, we define a type of matching called 0-1 timed matching for temporal graphs, and investigate the problem of finding a maximum 0-1 timed matching for different classes of temporal graphs. We first prove that the problem is NP-Complete for rooted temporal trees when each edge is associated with two or more time intervals. We then propose an \\(O(n n)\\) time algorithm for the problem on a rooted temporal tree with \\(n\\) nodes when each edge is associated with exactly one time interval. The problem is then shown to be NP-Complete also for bipartite temporal graphs even when each edge is associated with a single time interval and degree of each node is bounded by a constant \\(k 3\\). We next investigate approximation algorithms for the problem for temporal graphs where each edge is associated with more than one time intervals. It is first shown that there is no \\(1n^1-\\)-factor approximation algorithm for the problem for any \\( > 0\\) even on a rooted temporal tree with \\(n\\) nodes unless NP = ZPP. We then present a \\(52N^* + 3\\)-factor approximation algorithm for the problem for general temporal graphs where \\(N^*\\) is the average number of edges overlapping in time with each edge in the temporal graph. The same algorithm is also a constant-factor approximation algorithm for degree bounded temporal graphs.

A belt region is said to be k-barrier covered by a set of sensors if all paths crossing the width of the belt region intersect the sensing regions of at least k sensors. Barrier coverage can be achieved from a random initial deployment of mobile sensors by suitably relocating the sensors to form a barrier. Reducing the movement of the sensors is important in such scenarios due to the energy constraints of sensor devices. In this paper, we propose a centralized algorithm which achieves 1-barrier coverage by forming a non-linear barrier from a random initial deployment of sensors in a belt. The algorithm uses a novel idea of physical behavior of chains along with the concept of virtual force. Formation of non-linear barrier reduces the movement of the sensors needed as compared to linear barriers. Detailed simulation results are presented to show that the proposed algorithm achieves barrier coverage with less movement of sensors compared to other existing algorithms in the literature.

Self-stabilizing systems can automatically recover from arbitrary transient faults, and changes in the environment of the system, without any external intervention. However, in existing distributed self-stabilizing protocols, the performance of recovery is not linked to the severity of the fault. Recovery from failure at even a single component of the system may take a long time and affect the operation of the entire system. Since at any given time, limited faults in a small number of components are more likely than faults in a large number of components, this limitation restricts the use of self-stabilizing protocols in practice. As a solution, we propose in this thesis the design of fault-containing self-stabilizing protocols, self-stabilizing protocols that provide additional performance guarantees from less severe faults. From limited faults that are expected to occur more frequently in practice, such protocols ensure very fast recovery, and affects only the processes in a small region around the faults during the recovery. The effects of limited faults are thus contained efficiently in both time and space. At the same time, self-stabilization ensures automatic recovery from occasional transient faults that may be more widespread in the system. These protocols are a step forward towards making self-stabilization more practical. As a first step, we focus on fault-containment from single transient faults. However, our definitions are applicable to containment from other subsets of limited faults as well. The first part of this thesis presents a framework for defining and evaluating fault-containing self-stabilizing protocols. In particular, we define important metrics for evaluating the fault-containment properties of a self-stabilizing protocol. The second part of the thesis presents fault-containing self-stabilizing protocols for three important problems: leader election on a ring, construction of the spanning tree of a network, and construction of the breadth-first-search tree of a network. Finally, we present a general technique to automatically transform a non-reactive self-stabilizing protocol into a fault-containing self-stabilizing protocol. This general technique significantly simplifies the design of fault-containing self-stabilizing protocols.

The coverage problem in wireless sensor networks deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of line segments in sensor networks. A line segment ` is said to be covered if it intersects the sensing regions of at least one sensor distributed in that region. We show that the problem of finding the minimum number of sensors needed to cover each member in a given set of line segments in a rectangular area is NP-hard. Next, we propose a constant factor approximation algorithm for the problem of covering a set of axis-parallel line segments. We also show that a PTAS exists for this problem.

Deep neural networks are capable of modelling highly non-linear functions by capturing different levels of abstraction of data hierarchically. While training deep networks, first the system is initialized near a good optimum by greedy layer-wise unsupervised pre-training. However, with burgeoning data and increasing dimensions of the architecture, the time complexity of this approach becomes enormous. Also, greedy pre-training of the layers often turns detrimental by over-training a layer causing it to lose harmony with the rest of the network. In this paper a synchronized parallel algorithm for pre-training deep networks on multi-core machines has been proposed. Different layers are trained by parallel threads running on different cores with regular synchronization. Thus the pre-training process becomes faster and chances of over-training are reduced. This is experimentally validated using a stacked autoencoder for dimensionality reduction of MNIST handwritten digit database. The proposed algorithm achieved 26\\% speed-up compared to greedy layer-wise pre-training for achieving the same reconstruction accuracy substantiating its potential as an alternative.

Nodes in a MANET can be vulnerable to different types of attacks. These attacks can occur at different layers and can be classified into several ways. Most of the existing works that propose new and secure protocols for MANET have discussed about the issue of classifying the attacks. However, these works have largely remained focused on routing attacks. In [2,3], the authors have discussed the issue of misbehavior of nodes at Medium Access Control (MAC) layer and have attempted the classification of attacks at that layer. Some work has also been done on the attacks on application layer [4,5], but the area of focus has largely remained on sensor networks. It is also important to note that many of the existing works have made some specific and/or implicit assumptions as per their requirements.