國立虎尾科技大學 |

Algorithms for Optimal Replica Placement in Data Centers.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Algorithms for Optimal Replica Placement in Data Centers./
Author:	Mills, Kenneth Alex.
Description:	1 online resource (170 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 79-03(E), Section: B.
Contained By:	Dissertation Abstracts International79-03B(E).
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9780355392647

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

Algorithms for Optimal Replica Placement in Data Centers. - 1 online resource (170 pages)

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

Thesis (Ph.D.)

Includes bibliographical references

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.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355392647Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Algorithms for Optimal Replica Placement in Data Centers.
LDR:04498ntm a2200361Ki 4500 001 910979
005 20180517120325.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355392647
035 $a (MiAaPQ)AAI10675243
035 $a (MiAaPQ)0382vireo:149Mills
035 $a AAI10675243
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Mills, Kenneth Alex. $3 1182544
245 1 0 $a Algorithms for Optimal Replica Placement in Data Centers.
264 0 $c 2017
300 $a 1 online resource (170 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-03(E), Section: B.
500 $a Adviser: Neeraj Mittal.
502 $a Thesis (Ph.D.) $c The University of Texas at Dallas $d 2017.
504 $a Includes bibliographical references
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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a The University of Texas at Dallas. $b Computer Science. $3 1182545
773 0 $t Dissertation Abstracts International $g 79-03B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10675243 $z click for full text (PQDT)