On the NP-Hardness of the RedundantTaskAlloc Problem

Date
2007-11-01
Authors
Wingstrom, J.
Casanova, H.
Contributor
Advisor
Department
Instructor
Depositor
Speaker
Researcher
Consultant
Interviewer
Annotator
Journal Title
Journal ISSN
Volume Title
Publisher
Volume
Number/Issue
Starting Page
Ending Page
Alternative Title
Abstract
Consider an application that consists of n independent identical tasks to be executed on m computers, with m > n. Assume that each computer can execute a task with a given probability of success (typically <1). One can use redundancy to execute replicas of some of the tasks on the m-n computers. The problem is to determine how many replicas should be created for each task, or more precisely the number of task instances that should be created for each task and to which computers these instances should be allocated in order to maximize the probability of successful application completion. We formally define this problem, which we call RedundantTaskAlloc, and prove that it is NP-hard.
Description
Keywords
Citation
Extent
Format
Geographic Location
Time Period
Related To
Table of Contents
Rights
CC0 1.0 Universal
Rights Holder
Local Contexts
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.