Cross-Object Coding and Allocation (COCA) for Distributed Storage Systems

Distributed storage systems (DSSs) are widely employed in data centers and sensing networks to resist storage node failures. Structured redundancy is introduced to DSS by various coding schemes to efficiently account for failures of storage nodes. The allocation of the coded data blocks to storage nodes is another factor that impacts the data reliability. In this paper, we investigate the coding and allocation problem on multiple data objects in DSS. We propose a cross-object coding and allocation (COCA), which amounts to encoding and symmetric allocation on one large virtual data object aggregated by multiple data objects. We first explore the benefits of the proposed COCA scheme and find its reliability improvement in terms of joint successful recovery probability. However, such reliability improvement comes at the cost of increased data retrieval complexity. Hence, an optimization problem is formulated to explore the tradeoff between data reliability and data retrieval complexity. By employing a coalition formation game to model the process of the data objects grouping, we also propose a coalition-formation-based grouping algorithm to provide a suboptimal solution with greatly reduced computation complexity. Simulations validate the reliability improvement of our proposed COCA scheme and the effectiveness of our proposed coalition-formation-based algorithm.