{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:15:31Z","timestamp":1758845731730,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,31]],"date-time":"2018-03-31T00:00:00Z","timestamp":1522454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CSR-1217981, CCF-1422715 and AITF-1535929"],"award-info":[{"award-number":["CSR-1217981, CCF-1422715 and AITF-1535929"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Google research award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>\n            Motivated by the growing complexity and heterogeneity of modern data centers, and the prevalence of commodity component failures, this article studies the\n            <jats:italic>failure-aware placement problem<\/jats:italic>\n            of placing tasks of a parallel job on machines in the data center with the goal of increasing availability. We consider two models of failures: adversarial and probabilistic. In the adversarial model, each node has a weight (higher weight implying higher reliability) and the adversary can remove any subset of nodes of total weight at most a given bound\n            <jats:italic>W<\/jats:italic>\n            and our goal is to find a placement that incurs the least disruption against such an adversary. In the probabilistic model, each node has a probability of failure and we need to find a placement that maximizes the probability that at least\n            <jats:italic>K<\/jats:italic>\n            out of\n            <jats:italic>N<\/jats:italic>\n            tasks survive at any time.\n          <\/jats:p>\n          <jats:p>\n            For adversarial failures, we first show that (i) the problems are in \u03a3\n            <jats:sub>2<\/jats:sub>\n            , the second level of the polynomial hierarchy; (ii) a variant of the problem that we call R\n            <jats:sc>obust<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            (for Robust Failure-Aware Placement) is co-NP-hard; and (iii) an all-or-nothing version of R\n            <jats:sc>obust<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            is \u03a3\n            <jats:sub>2<\/jats:sub>\n            -complete. We then give a polynomial-time approximation scheme (PTAS) for R\n            <jats:sc>obust<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            , a key ingredient of which is a solution that we design for a fractional version of R\n            <jats:sc>obust<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            . We then study H\n            <jats:sc>ier<\/jats:sc>\n            R\n            <jats:sc>obust<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            , which is the fractional R\n            <jats:sc>obust<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            problem over a hierarchical network, in which failures can occur at any subset of nodes in the hierarchy, and a failure at a node can adversely impact all of its descendants in the hierarchy. To solve H\n            <jats:sc>ier<\/jats:sc>\n            R\n            <jats:sc>obust<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            , we introduce a notion of\n            <jats:italic>hierarchical max-min fairness<\/jats:italic>\n            and a novel\n            <jats:italic>Generalized Spreading<\/jats:italic>\n            algorithm, which is simultaneously optimal for every upper bound\n            <jats:italic>W<\/jats:italic>\n            on the total weight of nodes that an adversary can fail. These generalize the classical notion of\n            <jats:italic>max-min fairness<\/jats:italic>\n            to work with nodes of differing capacities, differing reliability weights, and hierarchical structures. Using randomized rounding, we extend this to give an algorithm for integral H\n            <jats:sc>ier<\/jats:sc>\n            R\n            <jats:sc>obust<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            .\n          <\/jats:p>\n          <jats:p>\n            For the probabilistic version, we first give an algorithm that achieves an additive \u03f5 approximation in the failure probability for the single level version, called P\n            <jats:sc>rob<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            , while giving up a (1 + \u03f5) multiplicative factor in the number of failures. We then extend the result to the hierarchical version, H\n            <jats:sc>ier<\/jats:sc>\n            P\n            <jats:sc>rob<\/jats:sc>\n            F\n            <jats:sc>ap<\/jats:sc>\n            , achieving an \u03f5 additive approximation in failure probability while giving up an (L + \u03f5) multiplicative factor in the number of failures, where\n            <jats:italic>L<\/jats:italic>\n            is the number of levels in the hierarchy.\n          <\/jats:p>","DOI":"10.1145\/3210367","type":"journal-article","created":{"date-parts":[[2018,6,21]],"date-time":"2018-06-21T12:04:33Z","timestamp":1529582673000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Robust and Probabilistic Failure-Aware Placement"],"prefix":"10.1145","volume":"5","author":[{"given":"Madhukar","family":"Korupolu","sequence":"first","affiliation":[{"name":"Nvidia Inc, Santa Clara, CA"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA"}]}],"member":"320","published-online":{"date-parts":[[2018,6,21]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Ceph storage architecture. Retrieved January 17 2018 from http:\/\/docs.ceph.com\/docs\/giant\/architecture\/.  Ceph storage architecture. Retrieved January 17 2018 from http:\/\/docs.ceph.com\/docs\/giant\/architecture\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1011"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1402946.1402967"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00193ED1V01Y200905CAC006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1030.0065"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"A. Bhalgat A. Goel and S. Khanna. 2011. Improved approximation results for stochastic knapsack problems. In SODA.   A. Bhalgat A. Goel and S. Khanna. 2011. Improved approximation results for stochastic knapsack problems. In SODA.","DOI":"10.1137\/1.9781611973082.127"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2342356.2342439"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_9"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11036-013-0489-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"C. Daskalakis A. De I. Diakonikolas A. Moitra and R. Servedio. 2014. A polynomial-time approximation scheme for fault-tolerant distributed storage. In SODA.   C. Daskalakis A. De I. Diakonikolas A. Moitra and R. Servedio. 2014. A polynomial-time approximation scheme for fault-tolerant distributed storage. In SODA.","DOI":"10.1137\/1.9781611973402.48"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556583"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/75247.75248"},{"volume-title":"Foundations of Bilevel Programming","author":"Dempe S.","key":"e_1_2_1_14_1","unstructured":"S. Dempe . 2002. Foundations of Bilevel Programming . Kluwer Academic Publishers . S. Dempe. 2002. Foundations of Bilevel Programming. Kluwer Academic Publishers."},{"key":"e_1_2_1_15_1","first-page":"93","article-title":"Bilevel programming with knapsack constraint","volume":"8","author":"Dempe S.","year":"2000","unstructured":"S. Dempe and K. Richter . 2000 . Bilevel programming with knapsack constraint . Central European Journal of Operations Research 8 , 2 (2000), 93 -- 107 . S. Dempe and K. Richter. 2000. Bilevel programming with knapsack constraint. Central European Journal of Operations Research 8, 2 (2000), 93--107.","journal-title":"Central European Journal of Operations Research"},{"volume-title":"Proceedings of Operating Systems Design and Implementation (OSDI).","author":"Ford D.","key":"e_1_2_1_17_1","unstructured":"D. Ford , F. Labelle , F. I. Popovici , M. Stokely , V. A. Truong , L. Barroso , C. Grimes , and S. Quinlan . 2010. Availability in globally distributed storage systems . In Proceedings of Operating Systems Design and Implementation (OSDI). D. Ford, F. Labelle, F. I. Popovici, M. Stokely, V. A. Truong, L. Barroso, C. Grimes, and S. Quinlan. 2010. Availability in globally distributed storage systems. In Proceedings of Operating Systems Design and Implementation (OSDI)."},{"key":"e_1_2_1_18_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043164.2018477"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2015.07.006"},{"volume-title":"An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network","author":"Keshav S.","key":"e_1_2_1_21_1","unstructured":"S. Keshav . 1997. An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network . Addison-Wesley Longman Publishing Co., Inc. , Boston, MA . S. Keshav. 1997. An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network. Addison-Wesley Longman Publishing Co., Inc., Boston, MA."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.03.006"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935802"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1960.10.1181"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/4492.4495"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.33"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488731"},{"volume-title":"The Theory of Error-correcting Codes","author":"MacWilliams Florence Jessie","key":"e_1_2_1_28_1","unstructured":"Florence Jessie MacWilliams and Neil James Alexander Sloane . 1977. The Theory of Error-correcting Codes . Vol. 16 . Elsevier . Florence Jessie MacWilliams and Neil James Alexander Sloane. 1977. The Theory of Error-correcting Codes. Vol. 16. Elsevier."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"R. Mansi C. Alves J. de Carvalho and S. Hanafi. 2012. An exact algorithm for bilevel 0-1 knapsack problems. Mathematical Problems in Engineering (2012).  R. Mansi C. Alves J. de Carvalho and S. Hanafi. 2012. An exact algorithm for bilevel 0-1 knapsack problems. Mathematical Problems in Engineering (2012).","DOI":"10.1155\/2012\/504713"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"K. A. Mills R. Chandrasekaran and N. Mittal. 2015. Algorithms for replica placement in high-availability storage. In ArXiv Preprint arXiv:1503.02654.  K. A. Mills R. Chandrasekaran and N. Mittal. 2015. Algorithms for replica placement in high-availability storage. In ArXiv Preprint arXiv:1503.02654.","DOI":"10.1007\/978-3-319-26626-8_26"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1987.1096782"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/050622328"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"E. Nikolova. 2010. Approximation algorithms for offline risk-averse combinatorial optimization. In APPROX.   E. Nikolova. 2010. Approximation algorithms for offline risk-averse combinatorial optimization. In APPROX.","DOI":"10.1007\/978-3-642-15369-3_26"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-009-9523-6"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.234856"},{"key":"e_1_2_1_36_1","unstructured":"Eduardo Pinheiro Wolf-Dietrich Weber and Luiz Andr\u00e9 Barroso. 2007. Failure trends in a large disk drive population.. In FAST. 17--23.   Eduardo Pinheiro Wolf-Dietrich Weber and Luiz Andr\u00e9 Barroso. 2007. Failure trends in a large disk drive population.. In FAST. 17--23."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199709)27:9%3C995::AID-SPE111%3E3.3.CO;2-Y"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391236"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/78\/1\/012022"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492101.1555372"},{"volume-title":"Proceedings of IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid\u201916)","author":"Sedaghat M.","key":"e_1_2_1_41_1","unstructured":"M. Sedaghat , E. Wadbro , J. Wilkes , S. De Luna , O. Seleznjev , and E. Elmroth . 2016. Die-hard: Reliable scheduling to survive correlated failures in cloud data centers . In Proceedings of IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid\u201916) . M. Sedaghat, E. Wadbro, J. Wilkes, S. De Luna, O. Seleznjev, and E. Elmroth. 2016. Die-hard: Reliable scheduling to survive correlated failures in cloud data centers. In Proceedings of IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid\u201916)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.142683"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741964"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807161"},{"volume-title":"The Theory of Market Economy","author":"von Stackelberg H.","key":"e_1_2_1_45_1","unstructured":"H. von Stackelberg . 1952. The Theory of Market Economy . Oxford University Press . H. von Stackelberg. 1952. The Theory of Market Economy. Oxford University Press."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1188455.1188582"},{"volume-title":"Proceedings of the Workshop on Real, Large Distributed Systems (WORLDS\u201904)","author":"Yalagandula P.","key":"e_1_2_1_47_1","unstructured":"P. Yalagandula , S. Nath , H. Yu , P. B. Gibbons , and Seshan S . 2004. Beyond availability: Towards a deeper understanding of machine failure characteristics in large distributed systems . In Proceedings of the Workshop on Real, Large Distributed Systems (WORLDS\u201904) . P. Yalagandula, S. Nath, H. Yu, P. B. Gibbons, and Seshan S.2004. Beyond availability: Towards a deeper understanding of machine failure characteristics in large distributed systems. In Proceedings of the Workshop on Real, Large Distributed Systems (WORLDS\u201904)."},{"volume-title":"Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.","author":"Zaharia M.","key":"e_1_2_1_48_1","unstructured":"M. Zaharia , M. Chowdhury , M . J. Franklin , S. Shenker , and I. Stoica . 2010. Spark: Cluster computing with working sets . In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. M. Zaharia, M. Chowdhury, M . J. Franklin, S. Shenker, and I. Stoica. 2010. Spark: Cluster computing with working sets. In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210367","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210367","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:13Z","timestamp":1750208893000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,31]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3210367"],"URL":"https:\/\/doi.org\/10.1145\/3210367","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2018,3,31]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}