A polynomial-time approximation scheme for fault-tolerant distributed storage

DOI10.1137/1.9781611973402.48MaRDI QIDQ5384009zbMATH OpenOpenAlexFDO

Authors Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Approximation algorithms (68W25) Analysis of algorithms (68W40) Nonconvex programming, global optimization (90C26)

Abstract: We consider a problem which has received considerable attention in systems literature because of its applications to routing in delay tolerant networks and replica placement in distributed storage systems. In abstract terms the problem can be stated as follows: Given a random variable $X$ generated by a known product distribution over ${0,1}^n$ and a target value $0leqhetaleq1$, output a non-negative vector $w$, with $|w{|}_{1}le1$, which maximizes the probability of the event $wcdotXgeheta$. This is a challenging non-convex optimization problem for which even computing the value $Pr[wcdotXgeheta]$ of a proposed solution vector $w$ is #P-hard. We provide an additive EPTAS for this problem which, for constant-bounded product distributions, runs in $poly(n)cdot{2}^{poly(1/eps)}$ time and outputs an $eps$-approximately optimal solution vector $w$ for this problem. Our approach is inspired by, and extends, recent structural results from the complexity-theoretic study of linear threshold functions. Furthermore, in spite of the objective function being non-smooth, we give a emph{unicriterion} PTAS while previous work for such objective functions has typically led to a emph{bicriterion} PTAS. We believe our techniques may be applicable to get unicriterion PTAS for other non-smooth objective functions.

Recommendations

• Approximation algorithms for data placement in arbitrary networks
• scientific article; zbMATH DE number 1445307
• An approximation algorithm for the stochastic fault-tolerant facility location problem
• A distributed approximation algorithm for fault-tolerant metric facility location
• Fault-tolerant facility location

Cited in

(6)

• Approximation algorithms for stochastic combinatorial optimization problems
• Beyond the MDS Bound in Distributed Cloud Storage
• Maximizing expected utility for stochastic combinatorial optimization problems
• Brief Announcement
• Public Bayesian persuasion: being almost optimal and almost persuasive
• scientific article; zbMATH DE number 7724191 (Why is no real title available?)

This page was built for publication: A polynomial-time approximation scheme for fault-tolerant distributed storage

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