In distributed storage systems built using commodity hardware, it is necessary to have data redundancy in order to ensure system reliability. In such systems, it is also often desirable to be able to quickly repair storage nodes that fail. We consider a scheme — introduced by El Rouayheb and Ramchandran — which uses combinatorial block design in order to design storage systems that enable efficient (and exact) node repair. In this work, we investigate systems where node sizes may be much larger than replication degrees, and explicitly provide algorithms for constructing these storage designs. Our designs, which are related to projective geometries, are based on the construction of bipartite cage graphs (with girth 6) and the concept of mutually-orthogonal Latin squares. Via these constructions, we can guarantee that the resulting designs require the fewest number of storage nodes for the given parameters, and can further show that these systems can be easily expanded without need for frequent reconfiguration.
Uncoded storage has numerous advantages for distributed storage systems. For instance, uncoded data at nodes allows for distributed computing (e.g., for cloud computing), by spreading out computation to the node(s) that contain the data to be processed. Upfal and Widgerson @cite_0 consider a method for parallel computation by randomly distributing data chunks among multiple memory devices, and derive some asymptotic performance results. In contrast, our designs are deterministic, and we are also able to guarantee the smallest possible size for our storage system. Furthermore, if uncoded data chunks are distributed among the nodes according to Steiner systems, then load-balancing of computations is always possible.
@cite_0
2066015450
The power of shared-memory in models of parallel computation is studied, and a novel distributed data structure that eliminates the need for shared memory without significantly increasing the run time of the parallel computation is described. More specifically, it is shown how a complete network of processors can deterministically simulate one PRAM step in O (log n (log log n ) 2 ) time when both models use n processors and the size of the PRAM's shared memory is polynomial in n . (The best previously known upper bound was the trivial O ( n )). It is established that this upper bound is nearly optimal, and it is proved that an on-line simulation of T PRAM steps by a complete network of processors requires O( T (log n log log n )) time. A simple consequence of the upper bound is that an Ultracomputer (the currently feasible general-purpose parallel machine) can simulate one step of a PRAM (the most convenient parallel model to program) in O ((log n ) 2 log log n ) steps.