Search

In data centers, data replication is the primary method used to ensure availability of customer data. To avoid correlated failure, cloud storage infrastructure providers model hierarchical failure domains using a tree, and avoid placing a large number of data replicas within the same failure domain (i.e. on the same branch of the tree). Typical best practices ensure that replicas are distributed across failure domains, but relatively little is known concerning optimization algorithms for distributing data replicas. Using a hierarchical model, we answer how to distribute replicas across failure domains optimally. We formulate a novel optimization problem for replica placement in data centers. As part of our problem, we formalize and present a new criterion for optimizing a replica placement. Our overall goal is to choose placements in which correlated failures disable as few replicas as possible. In this work, we provide two optimization algorithms for dependency models represented by trees. We first present an O (n + ρ log ⁡ ρ) time dynamic programming algorithm for optimally placing ρ replicas of a single block on the leaves (representing servers) of a tree with n vertices. We next consider the problem of optimally placing replicas of multiple blocks of data, where every block may have a different replication factor. For this problem, we give a dynamic programming algorithm that runs in O (n ρ max 3 δ 2 m poly (δ)) , where m denotes the number of blocks, ρ max denotes the maximum replication factor of a block, and δ denotes the maximum difference in the replication factors of any two blocks. The running time of the algorithm is polynomial when the δ , which we refer to as the skew , is a constant. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we design and analyze a simple, greedy algorithm for checking the linear and integer feasibility of a class of linear programs called Horn programs. This algorithm, which we term the “Lifting Algorithm”, runs in time on a Horn system (Horn program) with constraints and variables. The Lifting Algorithm is a variant of the Stressing Algorithm which was proposed for checking the feasibility of Difference Constraint systems. Inasmuch as Horn constraints subsume difference constraints, and all known algorithms for the problem of checking feasibility of Difference Constraint Systems run in time , the running time of our algorithm is only a factor worse than the best known running time for checking the feasibility of Difference Constraint Systems. Horn programs arise in a number of application areas including econometrics and program verification; consequently, their study is well-motivated. An important feature of our algorithm is that it uses only one operator, viz., addition. We also show that our algorithm can identify the linear and lattice point feasibility of Extended Horn Systems in time. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a practical problem, called Minimum Forwarding Set Problem (MFSP), that emerges within the context of implementing (energy efficient) communication protocols for wireless ad hoc or sensor networks. For a given node v, MFSP asks for a minimum cardinality subset of 1-hop neighbors of v to cover v’s 2-hop neighbors. MFSP problem is also known as multi-point relay (MPR) problem. It is shown to be an NP-complete problem for its general case that does not consider the coverage characteristics of wireless transmissions. In this paper, we present two polynomial time algorithms to solve the MFSP problem under disk coverage model for wireless transmissions. In our earlier work, we presented a polynomial time algorithm for this problem under unit disk coverage model. In the current work, we present several observations on the geometric characteristics of wireless transmissions under disk coverage model and build two alternative dynamic programming based solutions with different run time and space complexities to the problem. Disk coverage model is a more general model because it allows nodes to use arbitrary power levels for transmissions. As a result, the presented algorithms provide a more practical solution that can be used as a building block for energy efficient communication protocols designed for wireless ad hoc and sensor networks. [Copyright &y& Elsevier]

A cognitive radio (CR) node is a radio device capable of operating (transmitting and receiving) over multiple channels. As a result, a network consisting of one or more CR nodes can adapt to varying channel availability in its geographical region by dynamically changing the channel (or channels) that nodes use for communication. We investigate the problem of neighbour discovery in a network consisting of one or more CR nodes when nodes have multiple receivers but only a single transmitter. Neighbour discovery, in turn, can be used to solve other important communication problems such as broadcasting and gossiping in an efficient manner. We present a TDMA-based deterministic distributed algorithm for neighbour discovery whose time-complexity is M [N/r] + O(max(M,N)log r), where M is the maximum number of channels on which a node can operate, N denotes the size of the space used to assign identifiers to nodes, and r is the number of receivers at a node (with 1 ≤ r ≤ min(M, N)). [ABSTRACT FROM AUTHOR]

Abstract: We consider the following integer multipath flow network synthesis problem. We are given two positive integers , , (), and a non-negative, integer, symmetric, matrix , each non-diagonal element of which represents the minimum requirement of -path flow value between nodes and in an undirected network on the node set . We want to construct a simple, undirected network with integer edge capacities such that each of these flow requirements can be realized (one at a time) and the sum of all the edge capacities is minimum. We present an combinatorial algorithm for the problem and we show that the problem has integer rounding property. [Copyright &y& Elsevier]

Data classification and prediction problems are prevalent in many domains. The need to predict to which class a particular data point belongs has been seen in areas such as medical diagnosis, credit rating, Web filtering, prediction, and stock rating. This has led to strong interest in developing systems that can accurately classify data and predict outcome. The classification is typically based on the feature values of objects being classified. Often, a form of ordering relation, defined by feature values, on the objects to be classified is known. For instance, the objects belonging to one class have larger (or smaller) feature values than do those in the other class. Exploiting this characteristic of isotonicity, we propose a data-classification method called isotonic separation based on linear programming, especially network programming. The paper also addresses an extension of the isotonic-separation method for continuous outcome prediction. Applications of the isotonic separation for discrete outcome prediction and its extension for continuous outcome prediction are shown to illustrate its applicability. [ABSTRACT FROM AUTHOR]

We focus on systems whose components come from discrete choice sets. In a choice set, the alternatives have increasing cost with increasing reliability. The objective is to ensure minimal cost for achieving a specified reliability for the systems under consideration. Earlier work restricted itself to series-parallel/parallel-series (S/P) systems and provided formulations and algorithms. However, these are not amenable for dealing with more general systems. In this paper, we develop alternative formulations and algorithms based on a dynamic programming approach, and these are generalized for S/P-reducible systems. The algorithms we obtain are pseudo-polynomial and possess fully polynomial approximation schemes. Moreover, the formulations & algorithms are amenable for further generalizations to k-out-of-n G and k-out-of-n : G-reducible systems, though we cannot claim pseudo-polynomiality in these cases. The results of this paper are useful for developing reliable systems at minimum cost. As such, the formulation & algorithms are of vital interest for systems & reliability professionals & researchers. [ABSTRACT FROM AUTHOR]

We consider two problems of locating facilities on trees. In the first, we wish to determine the location of n points so as to maximize the minimum distance between any pair. In the second we wish to locate ,o centers of a single type of facility so as to minimize the maximum distance between any point and the center nearest to it. We provide polynomial algorithms for both problems, of O{...N...²logn.log...N...) for the first problem and of O(N...²log ρ) for the second, where...N...is the number of nodes in the tree. [ABSTRACT FROM AUTHOR]

We consider a special case of the transportation problem with 3 supply points and n demand points. An efficient algorithm is provided and the problem is illustrated with an example concerning financial aid to students. [ABSTRACT FROM AUTHOR]

Examines a class of Art Gallery problems that are defined on a pair of convex nested polygons. Concept of the Art Gallery problems; Discussion on the efficient parallel implementation of the algorithms; Definition of a greedy structure system; Information on the mathematical structures of the problems exposed by integer programming formulations.

An important first step when deploying a wireless ad hoc network is neighbor discovery in which every node attempts to determine the set of nodes it can communicate within one wireless hop. In the recent years, cognitive radio (CR) technology has gained attention as an attractive approach to alleviate spectrum congestion. A cognitive radio transceiver can operate over a wide range of frequencies possibly spanning multiple frequency bands. A cognitive radio node can opportunistically utilize unused wireless spectrum without interference from other wireless devices in its vicinity. Due to spatial variations in frequency usage and hardware variations in radio transceivers, different nodes in the network may perceive different subsets of frequencies available to them for communication. This heterogeneity in the available channel sets across the network increases the complexity of solving the neighbor discovery problem in a cognitive radio network. In this work, we design and analyze several randomized algorithms for neighbor discovery in such a (heterogeneous) network under a variety of assumptions ( e.g. , maximum node degree known or unknown) for both synchronous and asynchronous systems under minimal knowledge. We also show that our randomized algorithms are naturally suited to tolerate unreliable channels and adversarial attacks. [ABSTRACT FROM AUTHOR]