An Umbrella Converse for Data Exchange: Applied to Caching, Computing, Shuffling & Rebalancing

Krishnan, Prasad and Natarajan, Lakshmi and Lalitha, V. (2021) An Umbrella Converse for Data Exchange: Applied to Caching, Computing, Shuffling & Rebalancing. In: 2020 IEEE Information Theory Workshop, ITW 2020, 11 April 2021 - 15 April 2021,

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


The problem of data exchange between multiple nodes with (not necessarily uniform) storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem between multiple nodes. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, Coded Distributed Computing, and some of their variants, naturally can be seen as instances of this generic data exchange problem. Applying our generic converse to such problems, we recover known important converses for these settings and some of their variants in a simpler way. Further, for a generic coded caching problem with multiple transmitters, receivers and cache sizes, we show a new general converse which subsumes many existing results. We also employ our bound to obtain a new tight converse bound for the multi-node removal case in the Coded Data Rebalancing problem, in which nodes must exchange information to ‘rebalance’ a storage cluster after some node failures occur. Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1]

[error in script]
IITH Creators:
IITH CreatorsORCiD
Natarajan, Lakshmi Prasad
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Communication capabilities; Communication load; Design communication; Exchange problems; Multiple nodes; Multiple transmitters; Multiuser communication; Specific problems
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 23 Sep 2021 06:13
Last Modified: 23 Sep 2021 06:13
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8837 Statistics for this ePrint Item