Search

In this work, we consider the problem of placing replicas in a data center or storage area network, represented as a digraph, so as to lexico-minimize a previously proposed reliability measure which minimizes the impact of all failure events in the model in decreasing order of severity. Prior work focuses on the special case in which the digraph is an arborescence. In this work, we consider the broader class of multitrees: digraphs in which the subgraph induced by vertices reachable from a fixed node forms a tree. We parameterize multitrees by their number of "roots" (nodes with in-degree zero), and rule out membership in the class of fixed-parameter tractable problems (FPT) by showing that finding optimal replica placements in multitrees with 3 roots is NP-hard. On the positive side, we show that the problem of finding optimal replica placements in the class of \emph{untangled} multitrees is FPT, as parameterized by the replication factor $\rho$ and the number of roots $k$. Our approach combines dynamic programming (DP) with a novel tree decomposition to find an optimal placement of $\rho$ replicas on the leaves of a multitree with $n$ nodes and $k$ roots in $O(n^2\rho^{2k+3})$ time., Comment: 18 pages, 7 figures accepted for publication in COCOA 2017

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 explain 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. We provide two optimization algorithms for dependency models represented by trees. We first present an $O(n + \rho \log \rho)$ time dynamic programming algorithm for placing $\rho$ replicas of a single file on the leaves (representing servers) of a tree with $n$ vertices. We next consider the problem of placing replicas of $m$ blocks of data, where each block may have different replication factors. For this problem, we give an exact algorithm which runs in polynomial time when the skew, the difference in the number of replicas between the largest and smallest blocks of data, is constant., Comment: 64 pages, 9 figures. Preprint submission to Theoretical Computer Science

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 with in 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 scanning 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., Comment: 54 pages, 5 figures, 1 table, 6 algorithms, accepted in Journal of Parallel and Distributed Computing

A new model of causal failure is presented and used to solve a novel replica placement problem in data centers. The model describes dependencies among system components as a directed graph. A replica placement is defined as a subset of vertices in such a graph. A criterion for optimizing replica placements is formalized and explained. In this work, the optimization goal is to avoid choosing placements in which a single failure event is likely to wipe out multiple replicas. Using this criterion, a fast algorithm is given for the scenario in which the dependency model is a tree. The main contribution of the paper is an $O(n + \rho \log \rho)$ dynamic programming algorithm for placing $\rho$ replicas on a tree with $n$ vertices. This algorithm exhibits the interesting property that only two subproblems need to be recursively considered at each stage. An $O(n^2 \rho)$ greedy algorithm is also briefly reported., Comment: 22 pages, 7 figures, 4 algorithm listings

Web Based Query Management System (WBQMS) is a methodology to design and to implement Mobile Business, in which a server is the gateway to connect databases with clients which sends requests and receives responses in a distributive manner. The gateway, which communicates with mobile phone via GSM Modem, receives the coded queries from users and sends packed results back. The software which communicates with the gateway system via SHORT MESSAGE, packs users' requests, IDs and codes, and sends the package to the gateway; then interprets the packed data for the users to read on a page of GUI. Whenever and wherever they are, the customer can query the information by sending messages through the client device which may be mobile phone or PC. The mobile clients can get the appropriate services through the mobile business architecture in distributed environment. The messages are secured through the client side encoding mechanism to avoid the intruders. The gateway system is programmed by Java, while the software at clients by J2ME and the database is created by Oracle for reliable and interoperable services., Comment: IEEE Publication format, International Journal of Computer Science and Information Security, IJCSIS, Vol. 7 No. 3, March 2010, USA. ISSN 1947 5500, http://sites.google.com/site/ijcsis/