Coded Data Rebalancing: Fundamental Limits and Constructions

Krishnan, Prasad and Lalitha, V. and Natarajan, Lakshmi (2020) Coded Data Rebalancing: Fundamental Limits and Constructions. In: IEEE International Symposium on Information Theory - Proceedings, 21 July 2020 - 26 July 2020.

Full text not available from this repository. (Request a copy)

Abstract

Distributed databases often suffer unequal distribution of data among storage nodes, which is known as 'data skew'. Data skew arises from a number of causes such as removal of existing storage nodes and addition of new empty nodes to the database. Data skew leads to performance degradations and thus necessitates 'rebalancing' at regular intervals to reduce the amount of skew. We define an r-balanced distributed database as a distributed database in which the storage across the nodes has uniform size, and each bit of the data is replicated in r distinct storage nodes. We consider the problem of designing such balanced databases along with associated rebalancing schemes which maintain the r-balanced property under node removal and addition operations. We present a class of r-balanced databases (parameterized by the number of storage nodes) which have the property of structural invariance, i.e., the databases designed for different number of storage nodes have the same structure. For this class of r-balanced databases, we present rebalancing schemes which use coded transmissions between storage nodes, and characterize their communication loads under node addition and removal. We show that the communication cost incurred to rebalance our distributed database for node addition and removal is optimal, i.e., it achieves the minimum possible cost among all possible balanced distributed databases and rebalancing schemes.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Krishnan, PrasadUNSPECIFIED
Lalitha, V.UNSPECIFIED
Natarajan, Lakshmi Prasadhttp://orcid.org/0000-0003-1552-5240
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Balanced property; Coded transmission; Communication cost; Communication load; Distributed database; Parameterized; Performance degradation; Structural invariance
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 06 Jul 2021 09:33
Last Modified: 06 Jul 2021 09:33
URI: http://raiith.iith.ac.in/id/eprint/8139
Publisher URL: http://doi.org/10.1109/ISIT44484.2020.9174482
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8139 Statistics for this ePrint Item