Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2001) Diversity Coloring for Distributed Storage in Mobile Networks. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2001.ETR038
PDF (Adobe PDF (528KB))
See Usage Policy.
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2001.ETR038
Storing multiple copies of files is crucial for ensuring quality of service for data storage in mobile networks. This paper proposes a new scheme, called the K-out-of-N file distribution scheme, for the placement of files. In this scheme files are splitted, and Reed-Solomon codes or other maximum distance seperable (MDS) codes are used to produce file segments containing parity information. Multiple copies of the file segments are stored on gateways in the network in such a way that every gateway can retrieve enough file segments from itself and its neighbors within a certain amount of hops for reconstructing the orginal files. The goal is to minimize the maximum number of hops it takes for any gateway to get enough file segments for the file reconstruction. We formulate the K-out-of-N file distribution scheme as a coloring problem we call diversity coloring. A diversity coloring is defined to be optimal if it uses the smallest number of colors. Upper and lower bounds on the performance of diversity coloring for general graphs are studied. Diversity coloring algorithms for several special classes of graphs - trees, rings and tori - are presented, all of which have linear time complexity. Both the algorithm for trees and the algorithm for rings output optimal diversity colorings. The algorithm for tori guarantees to output optimal diversity coloring when the sizes of tori are sufficiently large.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Parallel and Distributed Systems Group|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||03 Sep 2002|
|Last Modified:||26 Dec 2012 13:51|
Repository Staff Only: item control page