CaltechAUTHORS
  A Caltech Library Service

Memory Allocation in Information Storage Networks

Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2002) Memory Allocation in Information Storage Networks. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2002.ETR048

[img]
Preview
Postscript
See Usage Policy.

243Kb
[img]
Preview
PDF (Adobe PDF (1.8MB))
See Usage Policy.

1797Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2002.ETR048

Abstract

We propose a file storage scheme which bounds the file-retrieving delays in a hetrerogeneous information network, under both fault-free and faulty circumstances. The scheme combines coding with storage for better performance. We study the memory allocation problem for the scheme, which is to decide how much data to store on each node, with the objective of minimizing the total amount of data stored in the network. This problem is NP-hard for general networks. We present three polynomial-time algorithms which solve the memory allocation problem for tree networks. The first two algorithms are for tree networks with and without upper bounds on nodes' memory sizes respectively. The third algorithm finds, among all the optimal solutions for the tree network, the solution that minimizes the greatest memory size of single nodes. By combining these memory allocation algorithms with known data-interleaving techniques, a complete solution to realize the file storage scheme in tree networks is established.


Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription
http://www.paradise.caltech.edu/papers/ETR048.psPublisherUNSPECIFIED
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2002.ETR048
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2002.ETR048
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26078
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:09 Dec 2002
Last Modified:26 Dec 2012 13:53

Repository Staff Only: item control page