A Caltech Library Service

Diversity Coloring for Distributed Storage in Mobile Networks

Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2001) Diversity Coloring for Distributed Storage in Mobile Networks. California Institute of Technology . (Unpublished)

PDF (Adobe PDF (528KB))
See Usage Policy.

See Usage Policy.


Use this Persistent URL to link to this item:


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)
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2001.ETR038
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:26036
Deposited By: Imported from CaltechPARADISE
Deposited On:03 Sep 2002
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page