Fast fault-tolerant resource allocation

Kewen Liao, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

Abstract

We present the first efficient approximation algorithm for the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem [12] with uniform fault tolerance levels. UFTRA is a relaxation of the classical Fault-Tolerant Facility Location problem [10]. Based on the fundamental primal-dual theory [23], our primal-dual algorithm achieves an approximation ratio of 1.861 while it can be implemented in quasi-linear time. Besides the significant improvement in runtime over all previous work, the solution quality of the algorithm matches the work in [26] using a phase-greedy algorithm and improves the result of [27] adopting the linear program rounding technique. Built on this algorithm, we also show that the capacitated UFTRA (CUFTRA) problem introduced in [12] achieves 3.722- approximation in quasi-linear time. In this paper, before the presence of the main algorithm and its extensive theoretical analysis, we provide some necessary background knowledge of the problem. This includes the problem's mathematical model formulation, the primal-dual theory applied to this formulation, and the problem's abstract system model with its potential application domains such as content distribution networks and cloud computing.

Original languageEnglish
Title of host publicationProceedings - 2011 12th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2011
PublisherIEEE Computer Society
Pages231-236
Number of pages6
ISBN (Electronic)9780769545646
ISBN (Print)9781457718076
DOIs
Publication statusPublished - 3 Jan 2012
Externally publishedYes
Event2011 12th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2011 - Gwangju, Korea, Republic of
Duration: 20 Oct 201122 Oct 2011

Conference

Conference2011 12th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2011
CountryKorea, Republic of
CityGwangju
Period20/10/1122/10/11

Fingerprint Dive into the research topics of 'Fast fault-tolerant resource allocation'. Together they form a unique fingerprint.

  • Cite this

    Liao, K., & Shen, H. (2012). Fast fault-tolerant resource allocation. In Proceedings - 2011 12th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2011 (pp. 231-236). [6118928] IEEE Computer Society. https://doi.org/10.1109/PDCAT.2011.41