A Pliable Index Coding Approach to Data Shuffling

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

9 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number8906011
Pages (from-to)1333-1353
Journal / PublicationIEEE Transactions on Information Theory
Volume66
Issue number3
Online published19 Nov 2019
Publication statusPublished - Mar 2020

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.

Research Area(s)

  • coded computing, data shuffling, distributed computing, Pliable index coding, random graph

Citation Format(s)

A Pliable Index Coding Approach to Data Shuffling. / Song, Linqi; Fragouli, Christina; Zhao, Tianchu.

In: IEEE Transactions on Information Theory, Vol. 66, No. 3, 8906011, 03.2020, p. 1333-1353.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review