國立高雄大學圖資館 |

Language: English

Back

Algorithms for Optimal Replica Place...

Mills, Kenneth Alex.

Algorithms for Optimal Replica Placement in Data Centers.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Algorithms for Optimal Replica Placement in Data Centers.
Author:	Mills, Kenneth Alex.
Published:	Ann Arbor : ProQuest Dissertations & Theses, 2017
Description:	170 p.
Notes:	Source: Dissertation Abstracts International, Volume: 79-03(E), Section: B.
Notes:	Adviser: Neeraj Mittal.
Contained By:	Dissertation Abstracts International79-03B(E).
Subject:	Computer science.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10675243
ISBN:	9780355392647

Algorithms for Optimal Replica Placement in Data Centers.
Mills, Kenneth Alex.

Algorithms for Optimal Replica Placement in Data Centers. - Ann Arbor : ProQuest Dissertations & Theses, 2017 - 170 p.

Source: Dissertation Abstracts International, Volume: 79-03(E), Section: B.

Thesis (Ph.D.)--The University of Texas at Dallas, 2017.

Owners of data centers are contractually obligated to provide high-availability service to their customers in the presence of ubiquitous hardware failures. Studies have indicated that co-occurring component failure is a key contributing factor towards unavailability in modern data centers [12]. Much effort has been made to produce quality statistical models of correlation among failures. In this dissertation we depart from this approach and provide a model which explicitly captures dependencies among system components. Our model consists of a directed graph wherein nodes represent hardware components and directed edges are used to connect nodes whose associated hardware components have a causal failure dependency. That is to say, failure in the source component may result in the compromised operation of the destination component. Given such a model, we consider how best to place r replicas of data in the data center so as to ensure as many replicas survive as possible. To this end, we cast our goals as combinatorial optimization problems for which we then provide algorithms or establish hardness.

ISBN: 9780355392647Subjects--Topical Terms:

199325
Computer science.

Algorithms for Optimal Replica Placement in Data Centers.
LDR:04161nmm a2200313 4500 001 523963
005 20180517120325.5
008 180709s2017 ||||||||||||||||| ||eng d
020 $a 9780355392647
035 $a (MiAaPQ)AAI10675243
035 $a (MiAaPQ)0382vireo:149Mills
035 $a AAI10675243
040 $a MiAaPQ $c MiAaPQ
100 1 $a Mills, Kenneth Alex. $3 795477
245 1 0 $a Algorithms for Optimal Replica Placement in Data Centers.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2017
300 $a 170 p.
500 $a Source: Dissertation Abstracts International, Volume: 79-03(E), Section: B.
500 $a Adviser: Neeraj Mittal.
502 $a Thesis (Ph.D.)--The University of Texas at Dallas, 2017.
520 $a Owners of data centers are contractually obligated to provide high-availability service to their customers in the presence of ubiquitous hardware failures. Studies have indicated that co-occurring component failure is a key contributing factor towards unavailability in modern data centers [12]. Much effort has been made to produce quality statistical models of correlation among failures. In this dissertation we depart from this approach and provide a model which explicitly captures dependencies among system components. Our model consists of a directed graph wherein nodes represent hardware components and directed edges are used to connect nodes whose associated hardware components have a causal failure dependency. That is to say, failure in the source component may result in the compromised operation of the destination component. Given such a model, we consider how best to place r replicas of data in the data center so as to ensure as many replicas survive as possible. To this end, we cast our goals as combinatorial optimization problems for which we then provide algorithms or establish hardness.
520 $a We consider several variations on the survivable replica placement problem. Motivated by their use in commercially-available systems for distributed storage, we first address the case wherein the graph is given as a tree. For this problem, we propose lexico-minimizing the failure aggregate, a novel vector-valued objective which closely matches our intuition concerning "good" replica placements. We provide an O(n+r log r) time dynamic programming algorithm for lexico-minimizing the failure aggregate. Next, we consider the problem of placing m replicated blocks of data, so as to optimize the placement of replicas for each block simultaneously. The complexity of this problem appears to be closely related to the skew, which we define to be the difference between the largest and smallest number of replicas among all blocks. We provide an algorithm whose running time grows like O(m O(delta2)), where delta is the skew, which is polynomial-time when the skew is a constant.
520 $a We then consider models which are more complicated than trees. We prove that optimizing replica placement over natural extensions of our model to bipartite graphs is NP-hard, and further show that this implies NP-hardness for directed graphs in general. In light of these hardness results, we next consider classes of graphs which are computationally tractable. Specifically, we show that reliable replica placement is fixed-parameter tractable in a special class of multitrees. A multitree is a directed acyclic graph in which the set of all nodes that can be reached from any fixed node induces a subgraph which is a tree. We parameterize multitrees via their number of roots (i.e., nodes with in-degree zero), and prove that survivable replica placement is NP-hard even when restricted to multitrees with only three roots. We then design a polynomial time algorithm for a special class of multitrees with two roots, and show how to extend this algorithm to one which runs on multitrees with k roots in O(nr 2k+2) time, which is polynomial-time when both the number of roots and the number of replicas is fixed.
590 $a School code: 0382.
650 4 $a Computer science. $3 199325
690 $a 0984
710 2 $a The University of Texas at Dallas. $b Computer Science. $3 708576
773 0 $t Dissertation Abstracts International $g 79-03B(E).
790 $a 0382
791 $a Ph.D.
792 $a 2017
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10675243