Fast fault-tolerant resource allocation
Date
2011
Authors
Liao, K.
Shen, H.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings: 2011 12th International Conference on Parallel and Distributed Computing, Applications and Technologies: PDCAT 2011: 20-22 October 2011 Gwangju, Korea: pp. 231-236
Statement of Responsibility
Kewen Liao and Hong Shen
Conference Name
International Conference on Parallel and Distributed Computing, Applications and Technologies (12th : 2011 : Gwangju, South Korea)
Abstract
We present the first efficient approximation algorithm for the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem [13] with uniform fault tolerance levels. UFTRA is a relaxation of the classical Fault-Tolerant Facility Location problem [11]. Based on the fundamental primal-dual theory [25], 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 [28] using a phase-greedy algorithm and improves the result of [29] adopting the linear program rounding technique. Built on this algorithm, we also show that the capacitated UFTRA (CUFTRA) problem introduced in [13] 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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright © 2011 by The Institute of Electrical and Electronics Engineers, Inc.