Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility

Abstract:
By using redundant data storage strategies in a disk array of a multimedia server, good disk load balancing can be achieved by solving the incurred retrieval problem, i.e.\ decide for each requested block of data which disk to use for its retrieval. Two possible load balancing approaches are block-based load balancing and time-based load balancing. In this paper we give a time complexity classification for the respective retrieval problems. It turns out that the retrieval problems corresponding to the block-based approach can be solved in polynomial time, whereas those corresponding to the time-based approach belong to the class of NP-hard problems.
Keywords: Analysis of algorithms, combinatorial problems, information retrieval, time complexity classification, NP-completeness proofs, polynomial time algorithms