Optimal Data Placement on Networks With Constant Number of Clients

Details Optimal Data Placement on Networks With Constant Number of Clients Optimal Data Placement on Networks With Constant Number of Clients

2010-04-26

arxiv.org/abs/1004.4420v1

Computer Science

Data Structures and Algorithms

Scientific paper

We introduce optimal algorithms for the problems of data placement (DP) and page placement (PP) in networks with a constant number of clients each of which has limited storage availability and issues requests for data objects. The objective for both problems is to efficiently utilize each client's storage (deciding where to place replicas of objects) so that the total incurred access and installation cost over all clients is minimized. In the PP problem an extra constraint on the maximum number of clients served by a single client must be satisfied. Our algorithms solve both problems optimally when all objects have uniform lengths. When objects lengths are non-uniform we also find the optimal solution, albeit a small, asymptotically tight violation of each client's storage size by $\epsilon$lmax where lmax is the maximum length of the objects and $\epsilon$ some arbitrarily small positive constant. We make no assumption on the underlying topology of the network (metric, ultrametric etc.), thus obtaining the first non-trivial results for non-metric data placement problems.

Affiliated with

Also associated with

No associations

Rating

Optimal Data Placement on Networks With Constant Number of Clients does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Data Placement on Networks With Constant Number of Clients, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Data Placement on Networks With Constant Number of Clients will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-31800