Optimal placement of replicas in trees with read, write, and storage costs

We consider the problem of placing copies of objects in a tree network in o rder to minimize the cost of servicing read and write requests to objects w hen the tree nodes have limited storage and the number of copies permitted is limited. The set of nodes that have a copy of the object is the residenc e set of the object. A node wishing to read the object will read the object from the closest node in the residence set. A node wishing to update the o bject will update the copy of the object at all the nodes in the residence set. Updates are propagated over a certain minimum spanning tree. The cost associated with a residence set equals the cost of servicing all the read a nd write requests and the storage costs for those copies. We describe a O(n (3)p(2))-time algorithm for finding an optimal residence set of size p for an object in a tree with n nodes, taking into consideration the read, write , and storage costs. Furthermore, we describe a O(n(3)p(2)Delta (2)(max))-t ime algorithm for finding a minimum cost normal p-residence set for an obje ct in a tree, this time also taking into account the load imposed by the no des of the tree on the nodes in a residence set and their capacity constrai nts, where Delta (max) is an upper bound on the capacity of each node of th e tree.