Site partitioning for distributed redundant disk arrays

Redundant disk arrays are used for the purpose of providing reliable storage while increasing the I/O bandwidth in high performance systems. Redundant disk arrays can also be used in a distributed setting to increase availability in the presence of temporary site failures or major disasters. The data at each site is partitioned into blocks and data blocks from different sites are grouped into a parity group. The bitwise parity of the data blocks in each parity group is computed and written at a different site. The authors look at the problem of partitioning a large distributed storage system into fixed size redundant arrays in such a way as to minimize the cost of remote accesses that have to be performed to update the parity information. They model the distributed computing system by an undirected connected graph G=(V,E) where V is the set of sites and each edge e∈E represents a bidirectional link between two sites