Algorithms for optimal replica placement under correlated failure in hierarchical failure domains

DOI10.1016/J.TCS.2020.01.004MaRDI QIDQ2290650zbMATH OpenOpenAlexWikidataFDO

Authors K. Alex Mills, R. Chandrasekaran, Neeraj Mittal

Publication date 29 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.01539

zbMATH Keywords

combinatorial optimizationcorrelated failuredata center managementfault-tolerant storagereplica placement

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Abstract: 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+hologho)$ time dynamic programming algorithm for placing $ho$ 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.

Recommendations

• On replica placement in high-availability storage under correlated failure
• Optimal inter-object correlation when replicating for availability
• Optimal inter-object correlation when replicating for availability
• Minimal replication cost for availability
• Placement of data replicas for optimal data availability in ring networks

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3099436 (Why is no real title available?)
• A Survey of Combinatorial Gray Codes
• Analytical approach to parallel repetition
• On replica placement in high-availability storage under correlated failure
• On the inapproximability of minimizing cascading failures under the deterministic threshold model
• Optimal placement of data replicas in distributed database with majority voting protocol
• Placement of data replicas for optimal data availability in ring networks
• Which Networks are Least Susceptible to Cascading Failures?

Cited in

(5)

• Optimal inter-object correlation when replicating for availability
• Optimal inter-object correlation when replicating for availability
• On replica placement in high-availability storage under correlated failure
• Robustly assigning unstable items
• Lexico-minimum replica placement in multitrees

This page was built for publication: Algorithms for optimal replica placement under correlated failure in hierarchical failure domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290650)