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

DOI10.1016/J.TCS.2020.01.004zbMATH Open1436.68093arXiv1701.01539OpenAlexW3000211822WikidataQ126383496 ScholiaQ126383496MaRDI QIDQ2290650FDOQ2290650

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

Publication date: 29 January 2020

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• Optimal inter-object correlation when replicating for availability
• Optimal inter-object correlation when replicating for availability
• Robustly assigning unstable items
• On replica placement in high-availability storage under correlated failure
• 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)