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)

See Usage Policy.

PDF (Adobe PDF (1.8MB))
See Usage Policy.


Use this Persistent URL to link to this item:


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
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2002.ETR048
Persistent URL:
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
Deposited By: Imported from CaltechPARADISE
Deposited On:09 Dec 2002
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page