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

Krishnan, Prasad and Natarajan, Lakshmi Prasad and Lalitha, V. (2021) An Umbrella Converse for Data Exchange: Applied to Caching, Computing, and Shuffling. Entropy, 23 (8). pp. 1-32. ISSN 1099-4300

Text
Entropy.pdf - Published Version
Available under License Creative Commons Attribution.
Download (572kB)

Abstract

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. © 2021 by the authors. Licensee MDPI, Basel, Switzerland.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Natarajan, Lakshmi Prasad	http://orcid.org/0000-0003-1552-5240

Item Type:

Article

Additional Information:

Prasad Krishnan was supported by Science and Engineering Research Board (SERB), Government of India via grants CRG/2019/005572 and MTR/2017/000827. Lakshmi Natarajan was supported by Science and Engineering Research Board (SERB-DST), Government of India (via projects MTR/2019/001454 and DST/INSPIRE/04/2015/002094).

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:

. LibTrainee 2021

Date Deposited:

04 Aug 2022 11:30

Last Modified:

04 Aug 2022 11:30