Distributed storage of data files in different nodes of a network enhances its fault tolerance capability by offering protection against node and link failures. Reliability is often achieved through redundancy in one of the following two ways: (i) storage of multiple copies of the entire file at different locations (nodes) or (ii) storage of file segments (not entire files) at different node locations. In the file distribution scheme, file segments from a file are created in such a way that it is possible to reconstruct the entire file, just by accessing any segments. For the reconstruction scheme to work, it is essential that the segments of the file are stored in nodes that are connected in the network. However, in the event of node/link failures, the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially correlated or region based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The first goal of this research is to design a least cost file storage scheme to ensure that no matter which region is destroyed; resulting in fragmentation of the network, a largest connected component of the residual network will have enough file segments with which to reconstruct the entire file. In case the least cost to ensure this objective is within the allocated budget, the storage design will be all region fault‐tolerant (ARFT). In case the least cost exceeds the allocated budget, design of an ARFT file storage system design is impossible. The second goal of this research is to design file storage schemes that will be maximum region fault‐tolerant within the allocated budget. The third goal of this research is to investigate the impact of the coding parameters and on storage requirements for ensuring all region or \textit{maximum region} fault‐tolerant design. We provide maximum region fault‐tolerant design. We provide approximation algorithms for the problems and evaluate their performance through simulation using two real networks and compare their results to the optimal solutions obtained using Integer Linear Program. The simulation results demonstrate that the approximation algorithms almost always produce near optimal results in a fraction of the time needed to find the optimal solution. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 380–395 2015

Internet and social media devices created a new public space for online debate on political and social topics. A debate is defined as a formal discussion on a set of related topics in a public meeting, in which opposing perspectives and arguments are put forward. In this paper, we develop automated perspective discovery techniques which would contribute to the understanding of features (i.e. social, political, cultural, religious beliefs, goals, and practices) shared by each side of the debate. Secondly, we show that, compared to a semi-automated process, our perspective discovery algorithms not only identify larger number of relevant features, but they also yield a higher accuracy scaling of moderate to extreme organizations on both sides of a debate.

Distributed storage of data files in different nodes of a network enhances the reliability of the data by offering protection against node failure. In the (N,K),N ≥ K file distribution scheme, from a file F of size |F|, N segments of size |F|/K are created in such a way that it is possible to reconstruct the entire file, just by accessing any K segments. For the reconstruction scheme to work it is essential that the K segments of the file are stored in nodes that are connected in the network. However in case of node failures the network might become disconnected (i.e., split into several connected components). We focus on node failures that are spatially-correlated or region-based. Such failures are often encountered in disaster situations or natural calamities where only the nodes in the disaster zone are affected. The goal of this research is to devise a file segment distribution scheme so that, even if the network becomes disconnected due to any region fault, at least one of the largest connected components will have at least K distinct file segments with which to reconstruct the entire file. The distribution scheme will also ensure that the total storage requirement is minimized. We provide an optimal solution through Integer Linear Programming and an approximation solution with a guaranteed performance bound of O(ln n) to solve the problem for any arbitrary network. The performance of the approximation algorithm is evaluated by simulation on two real networks.

Robustness or fault-tolerance capability of a network is an important design parameter in both wired and wireless networks. Connectivity of a network is traditionally considered to be the primary metric for evaluation of its fault-tolerance capability. However, connectivity κ(G) (for random faults) or region-based connectivity κR(G) (for spatially correlated or region-based faults, where the faults are confined to a region R) of a network G, does not provide any information about the network state, (i.e., whether the network is connected or not) once the number of faults exceeds κ(G) or κR(G). If the number of faults exceeds κ(G) or κR(G), one would like to know, (i) the number of connected components into which G decomposes, (ii) the size of the largest connected component, (iii) the size of the smallest connected component. In this paper, we introduce a set of new metrics that computes these values. We focus on one particular metric called region-based component decomposition number (RBCDN), that measures the number of connected components in which the network decomposes once all the nodes of a region fail. We study the computational complexity of finding RBCDN of a network. In addition, we study the problem of least cost design of a network with a target value of RBCDN. We show that the optimal design problem is NP-complete and present an approximation algorithm with a performance bound of O(log K + 4log n), where n denotes the number of nodes in the graph and K denotes a target value of RBCDN. We evaluate the performance of our algorithm by comparing it with the performance of the optimal solution. Experimental results demonstrate that our algorithm produces near optimal solution in a fraction of time needed to find an optimal solution.

The traditional studies on fault-tolerance in networks assume that the faults are random in nature, i.e., the probability of a node failing is independent of its location in the deployment area. However, this assumption is no longer valid if the faults are spatially correlated. In this paper we focus on the study of the impact of region-based faults on wireless networks. Most of the studies on connectivity of wireless networks assume a unit disk graph model, i.e., links exist between two nodes if they are within a circular transmission range of one another. However, the unit disk graph model does not capture wireless communication environment accurately. The log-normal shadow fading model for communication was introduced to overcome the limitations of the unit disk graph model. In this paper we investigate connectivity issues of wireless networks in a log-normal shadow fading environment where the faults are spatially correlated. If dmin(G) denotes the minimum node degree of the network, we provide the analytical expression and method for computing P(dmin(G) ≥ 1) in a region-based fault scenario, where P(dmin(G) ≥ 1) denotes the probability of the minimum node degree being at least 1. Through extensive simulation, we find (P(κG) ≥ 1), where κ(G) represents the connectivity of the graph G formed by the distribution of nodes on a 2D plane and examine the relationship between P(dmin(G) ≥ 1) and P(κ(G) ≥ 1).

Connectivity k(G) of a network G is traditionally considered to be the primary metric for evaluation of its fault tolerance capability. However, connectivity as a metric has several limitations - e.g., it has no mechanism to distinguish between localized and random faults. Also it does not provide any information about the network state, if number of failures exceed k(G). The network state information that might be of interest in such a scenario is the size of the largest connected component. In this paper, we address both these limitations and introduce a new metric called region-based largest component size (RBLCS), that provides the largest size of the component in which the network decomposes once all the nodes of a region fail. We study the computational complexity of finding RBLCS for a given network. In addition, we study the problem of least cost design of a network with a target value of RBLCS. We prove that the optimal design problem is NP-complete and present a heuristic to solve the problem. We evaluate our heuristic by comparing its solutions with the optimal solutions. Experimental results demonstrate that our heuristic produces near optimal solution in a fraction of time needed to find the optimal.

Optical reach is defined as the distance optical signal can traverse before its quality degrades to a level that necessitates regeneration. It typically ranges from 500 to 2000 miles, and as a consequence, regeneration of optical signal becomes essential in order to establish a lightpath between a source-destination node pair whose distance exceeds the limit. In a translucent optical network, the optical signal is regenerated at selected nodes of the network before the signal quality degrades below the acceptable threshold. Given the optical reach of the signal, to minimize the overall network design cost, the goal of the regenerator placement problem is to find the minimum number of regenerators necessary in the network, so that every pair of nodes is able to establish a lightpath between them. In this paper, we study the regenerator placement problem and present complexity result for that.

The optical reach (the distance an optical signal can travel before the signal quality degrades to a level that necessitates regeneration) ranges from 500 to 2000 miles. To establish a lightpath of length greater than the optical reach, it is necessary to regenerate optical signals. In a translucent optical network, there are regeneration points, where the signal undergoes Optical-Electronic-Optical (O-E-O) conversion. In this paper we have proposed routing algorithms for translucent networks in a dynamic lightpath allocation environment in which requests for communication arrive continuously. In response to each request for communication, the objective is to establish, if possible, a path, from the source to the destination of the request for communication, so that a lightpath may be established, using the path that requires the fewest stages of regeneration. In practical transparent networks, a lightpath must satisfy the wavelength continuity constraint. However, in a translucent network, this constraint can be relaxed at the regeneration points. We have proposed an Integer Linear Program, to give the optimum results for small networks, as well as an efficient heuristic for this problem that works for larger networks. We have evaluated the heuristic through extensive simulations to establish that the heuristic produces close-to-optimal solutions in a fraction of the time needed for the optimal solutions. Our extensive evaluations demonstrate the relative impact of a set of network resources, such as (i) the number of regenerators, (ii) the optical reach of the regenerators and (iii) the number of wavelengths, on the network performance, measured in terms of the call blocking probability. To the best of our knowledge this is the first study that undertakes such an evaluation for translucent networks.