DNAS: Dispersed Network Attached Storage for Reliability and Performance

Abstract

NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract included in .pdf document. With the advent of merging between communication and storage, there is an increasing need for developing dis- tributed data layout schemes for network attached storage that address reliability and performance challenges. This paper proposes a novel scheme for storing information on networks. In particular, for a fault-free operation, it provides the ability to retrieve data by accessing network nodes within a small proximity. In the event of faults, data is guaranteed to be retrieved by exploring a slightly larger proximity. The problem of designing layout schemes, namely pro- viding Dispersed Network Attached Storage (DNAS), is formulated as a graph coloring problem that we call Layered Diversity Coloring. Consider the following problem: given a graph G(V,E) and N colors, how to color vertices of G so that every vertex can find at least [...] In this paper we study the layered diversity coloring problem where the graph G(V,E) is a tree. A coloring algorithm of time complexity [...] is presented, and the sufficient and necessary condition for there to exist a layered diversity coloring on a tree follows the algorithm.