Please use this identifier to cite or link to this item: http://hdl.handle.net/10125/33380

On the NP-Hardness of the RedundantTaskAlloc Problem

File SizeFormat 
foo.pdf101.9 kBAdobe PDFView/Open

Item Summary

Title: On the NP-Hardness of the RedundantTaskAlloc Problem
Authors: Wingstrom, J.
Casanova, H.
Issue Date: 01 Nov 2007
Series/Report no.: ICS2007-11-02
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.
URI/DOI: http://hdl.handle.net/10125/33380
Rights: CC0 1.0 Universal
Appears in Collections:Technical Reports



Items in ScholarSpace are protected by copyright, with all rights reserved, unless otherwise indicated.