arXiv Analytics

Sign in

arXiv:2205.06257 [cs.IT]AbstractReferencesReviewsResources

Coded Data Rebalancing for Distributed Data Storage Systems with Cyclic Storage

Athreya Chandramouli, Abhinav Vaishya, Prasad Krishnan

Published 2022-05-12Version 1

We consider replication-based distributed storage systems in which each node stores the same quantum of data and each data bit stored has the same replication factor across the nodes. Such systems are referred to as \textit{balanced distributed databases}. When existing nodes leave or new nodes are added unto this system, the balanced nature of the database is lost, either due to the reduction in the replication factor, or due to non-uniformity of the storage at the nodes. This triggers a \textit{rebalancing} algorithm, which exchanges data between the nodes so that the balance of the database is reinstated. In a recent work by Krishnan et al., coded transmissions were used to rebalance a carefully designed distributed database from a node removal or addition. These coded rebalancing schemes have optimal communication load, however require the file-size to be at least exponential in the system parameters. In this work, we consider a \textit{cyclic balanced database} (where data is cyclically placed in the system nodes) and present coded rebalancing schemes for node removal and addition in such a database. These databases (and the associated rebalancing schemes) require the file-size to be only \textit{cubic} in the number of nodes in the system. We show that the communication load of the node-removal rebalancing scheme is strictly smaller than the load of the uncoded scheme. In the node addition scenario, the rebalancing scheme presented is a simple uncoded scheme, which we show has optimal load.

Related articles: Most relevant | Search more
arXiv:2001.04939 [cs.IT] (Published 2020-01-14)
Coded Data Rebalancing: Fundamental Limits and Constructions
arXiv:1311.4096 [cs.IT] (Published 2013-11-16, updated 2014-11-06)
Distributed Data Storage Systems with Opportunistic Repair
arXiv:2102.10163 [cs.IT] (Published 2021-02-19)
On Gradient Coding with Partial Recovery