2007 · 14 citations · 17 references
ComputingComputer ScienceComputer SystemsDistributed SystemsOptimizationSchedulingDistributed ComputingResource AllocationResource SchedulingReplica ManagementReplica PlacementReplica SchedulingReplica SelectionReplication SchedulingReplication-based Scheduling
Given two replication schemes X <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">old</sup> and X <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">new</sup> , the replica transfer scheduling problem (RTSP) aims at reaching X <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">new</sup> , starting from X <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">old</sup> , with minimal implementation cost. In this paper we generalize the problem description to include special cases, where deadlocks can occur while in the process of implementing X <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">new</sup> . We address this impediment by introducing artificial (dummy) transfers. We then prove that RTSP-decision is NP-complete and propose two kinds of heuristics. The first attempts to replace dummy transfers with valid ones, while the second minimizes the implementation cost. Experimental evaluation of the algorithms illustrates the merits of our approach.
17
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
Tracy D. Braun, Howard Jay Siegel, Noah Beck et al. · Journal of Parallel and Distributed Computing · 2001 · 1.7K citations
On the placement of Web server replicas
Lili Qiu, Venkata N. Padmanabhan, Geoff Voelker · 2002 · 805 citations