{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:25:47Z","timestamp":1761294347796,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T00:00:00Z","timestamp":1627603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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 \u201ccentralized\u201d version of our bound to the known generalized independence number bound in index coding and discuss our bound\u2019s tightness in this context.<\/jats:p>","DOI":"10.3390\/e23080985","type":"journal-article","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T12:59:24Z","timestamp":1627649964000},"page":"985","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Umbrella Converse for Data Exchange: Applied to Caching, Computing, and Shuffling"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9182-6278","authenticated-orcid":false,"given":"Prasad","family":"Krishnan","sequence":"first","affiliation":[{"name":"Signal Processing & Communications Research Center, International Institute of Information Technology Hyderabad, Hyderabad 500032, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lakshmi","family":"Natarajan","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Indian Institute of Technology Hyderabad, Kandi 502205, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2874-8910","authenticated-orcid":false,"given":"V.","family":"Lalitha","sequence":"additional","affiliation":[{"name":"Signal Processing & Communications Research Center, International Institute of Information Technology Hyderabad, Hyderabad 500032, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,7,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2856","DOI":"10.1109\/TIT.2014.2306938","article-title":"Fundamental Limits of Caching","volume":"60","author":"Niesen","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Li, S., Maddah-Ali, M.A., and Avestimehr, A.S. (October, January 29). Coded MapReduce. Proceedings of the 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2015.7447112"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TIT.2017.2756959","article-title":"A Fundamental Tradeoff Between Computation and Communication in Distributed Computing","volume":"64","author":"Li","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1514","DOI":"10.1109\/TIT.2017.2736066","article-title":"Speeding Up Distributed Machine Learning Using Codes","volume":"64","author":"Lee","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3616","DOI":"10.1109\/TIT.2020.2966197","article-title":"Fundamental Limits of Decentralized Data Shuffling","volume":"66","author":"Wan","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3098","DOI":"10.1109\/TIT.2020.2964547","article-title":"On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning","volume":"66","author":"Elmahdy","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Krishnan, P., Lalitha, V., and Natarajan, L. (2020, January 21\u201326). Coded Data Rebalancing: Fundamental Limits and Constructions. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174482"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"El Rouayheb, S., Sprintson, A., and Sadeghi, P. (2010, January 6\u20138). On coding for cooperative data exchange. Proceedings of the 2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo), Cairo, Egypt.","DOI":"10.1109\/ITWKSPS.2010.5503135"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1517","DOI":"10.1109\/TIT.2012.2227674","article-title":"Error Correction for Index Coding with Side Information","volume":"59","author":"Dau","year":"2013","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Sadeghi, P., Arbabjolfaei, F., and Kim, Y.H. (2016, January 11\u201314). Distributed index coding. Proceedings of the 2016 IEEE Information Theory Workshop (ITW), Cambridge, UK.","DOI":"10.1109\/ITW.2016.7606850"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1725","DOI":"10.1109\/TIT.2018.2869161","article-title":"Cooperative Multi-Sender Index Coding","volume":"65","author":"Li","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1109\/TIT.2020.3043767","article-title":"Embedded Index Coding","volume":"67","author":"Porter","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Yu, Q., Li, S., Maddah-Ali, M.A., and Avestimehr, A.S. (2017, January 21\u201325). How to optimally allocate resources for coded distributed computing?. Proceedings of the 2017 IEEE International Conference on Communications (ICC), Paris, France.","DOI":"10.1109\/ICC.2017.7996730"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Krishnan, P., Natarajan, L., and Lalitha, V. (2020, January 11\u201315). An Umbrella Converse for Data Exchange: Applied to Caching, Computing, Shuffling & Rebalancing. Proceedings of the 2020 IEEE Information Theory Workshop, Riva del Garda, Italy.","DOI":"10.1109\/ITW46852.2021.9457640"},{"key":"ref_15","unstructured":"Wan, K., Tuninetti, D., and Piantanida, P. (2016, January 11\u201314). On the optimality of uncoded cache placement. Proceedings of the 2016 IEEE Information Theory Workshop (ITW), Cambridge, UK."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1281","DOI":"10.1109\/TIT.2017.2785237","article-title":"The Exact Rate-Memory Tradeoff for Caching with Uncoded Prefetching","volume":"64","author":"Yu","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1109\/TIT.2015.2504556","article-title":"Fundamental Limits of Caching in Wireless D2D Networks","volume":"62","author":"Ji","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Asadi, B., Ong, L., and Johnson, S.J. (2018, January 25\u201329). Centralized Caching with Unequal Cache Sizes. Proceedings of the 2018 IEEE Information Theory Workshop (ITW), Guangzhou, China.","DOI":"10.1109\/ITW.2018.8613348"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Ibrahim, A.M., Zewail, A.A., and Yener, A. (2017, January 19\u201322). Centralized Coded Caching with Heterogeneous Cache Sizes. Proceedings of the 2017 IEEE Wireless Communications and Networking Conference (WCNC), San Francisco, CA, USA.","DOI":"10.1109\/WCNC.2017.7925535"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"8179","DOI":"10.1109\/TCOMM.2019.2940671","article-title":"On the Optimality of D2D Coded Caching With Uncoded Cache Placement and One-Shot Delivery","volume":"67","author":"Yapar","year":"2019","journal-title":"IEEE Trans. Commun."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ibrahim, A.M., Zewail, A.A., and Yener, A. (2018, January 20\u201324). Device-to-Device Coded Caching with Heterogeneous Cache Sizes. Proceedings of the 2018 IEEE International Conference on Communications (ICC), Kansas City, MO, USA.","DOI":"10.1109\/ICC.2018.8422195"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Wei, Y., and Ulukus, S. (2017, January 3\u20136). Coded caching with multiple file requests. Proceedings of the 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2017.8262770"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2252","DOI":"10.1109\/TIT.2019.2955384","article-title":"Fundamental Limits of Coded Caching With Multiple Antennas, Shared Caches and Uncoded Prefetching","volume":"66","author":"Parrinello","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1109\/TNET.2014.2317316","article-title":"Decentralized Coded Caching Attains Order-Optimal Memory-Rate Tradeoff","volume":"23","author":"Niesen","year":"2015","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Karat, N.S., Bhargav, K.L.V., and Rajan, B.S. (2020, January 21\u201326). On the Optimality of Two Decentralized Coded Caching Schemes with and without Error Correction. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174115"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1479","DOI":"10.1109\/TIT.2010.2103753","article-title":"Index Coding with Side Information","volume":"57","author":"Birk","year":"2011","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","unstructured":"Birk, Y., and Kol, T. (April, January 29). Informed-source coding-on-demand (ISCOD) over broadcast channels. Proceedings of the IEEE INFOCOM \u201998, the Conference on Computer Communications, Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, Gateway to the 21st Century (Cat. No.98), San Francisco, CA, USA."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Tehrani, A.S., Dimakis, A.G., and Neely, M.J. (2012, January 1\u20136). Bipartite index coding. Proceedings of the 2012 IEEE International Symposium on Information Theory Proceedings, Cambridge, MA, USA.","DOI":"10.1109\/ISIT.2012.6283853"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/8\/985\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:37:16Z","timestamp":1760164636000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/8\/985"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,30]]},"references-count":28,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["e23080985"],"URL":"https:\/\/doi.org\/10.3390\/e23080985","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,7,30]]}}}