An Umbrella Converse for Data Exchange: Applied to Caching, Computing, and Shuffling.

Krishnan, P. and Natarajan, L. and Lalitha, V. (2021) An Umbrella Converse for Data Exchange: Applied to Caching, Computing, and Shuffling. Entropy, 23 (8). p. 985. ISSN 10994300

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


The problem of data exchange between multiple nodes with 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. 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, and Coded Distributed Computing, can be seen as instances of this generic data exchange problem. Applying our generic converse, we can efficiently recover known important converses in these formulations. Further, for a generic coded caching problem with heterogeneous cache sizes at the clients with or without a central server, we obtain a new general converse, which subsumes some existing results. Finally we relate a “centralized” version of our bound to the known generalized independence number bound in index coding and discuss our bound’s tightness in this context.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Natarajan, Lakshmi Prasad
Item Type: Article
Uncontrolled Keywords: Coded caching, Coded data shuffling, Coded distributed computing, Converse, Data exchange, Index coding
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 10 Nov 2021 09:46
Last Modified: 11 Mar 2022 06:17
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8961 Statistics for this ePrint Item