A Pliable Index Coding Approach to Data Shuffling

DOI10.1109/TIT.2019.2954338MaRDI QIDQ5123790zbMATH OpenOpenAlexFDO

Authors Linqi Song, Christina Fragouli, Tianchu Zhao

Publication date 29 September 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05540

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distributed systems (68M14) Source coding (94A29)

Abstract: A promising research area that has recently emerged, is on how to use index coding to improve the communication efficiency in distributed computing systems, especially for data shuffling in iterative computations. In this paper, we posit that pliable index coding can offer a more efficient framework for data shuffling, as it can better leverage the many possible shuffling choices to reduce the number of transmissions. We theoretically analyze pliable index coding under data shuffling constraints, and design a hierarchical data-shuffling scheme that uses pliable coding as a component. We find benefits up to $O(ns/m)$ over index coding, where $ns/m$ is the average number of workers caching a message, and $m$, $n$, and $s$ are the numbers of messages, workers, and cache size, respectively.

Cited in

(2)

• An encoding method for multifield sorting and indexing
• A Polynomial-Time Algorithm for Pliable Index Coding

This page was built for publication: A Pliable Index Coding Approach to Data Shuffling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5123790)