Assigning Sites to Redundant Clusters in a Distributed Storage System

Abstract

Redundant Arrays of Distributed Disks (RADD) can be used in a distributed computing system or database system to provide recovery in the presence of disk crashes and temporary and permanent failures of single sites. In this paper, we look at the problem of partitioning the sites of a distributed storage system into redundant arrays in such a way that the communication costs for maintaining the parity information are minimized. We show that the partitioning problem is NP-hard. We then propose and evaluate several heuristic algorithms for finding approximate solutions. Simulation results show that significant reduction in remote parity update costs can be achieved by optimizing the site partitioning scheme.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1992
Accession Number
ADA260458

Entities

People

  • Antoine N. Mourad
  • Daniel G. Saab
  • W. Kent Fuchs

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Data Storage Systems
  • Disasters
  • Distributed Computing
  • Environment
  • Guarantees
  • Heuristic Methods
  • High Performance Computing
  • Hot Spots
  • Image Processing
  • Intervals
  • Local Area Networks
  • Military Research
  • Nonvolatile Memories
  • Optimization
  • Recovery

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Parallel and Distributed Computing.