Heterogeneous Coded Distributed Computing with Nonuniform Input File Popularity

Yong Deng, Min DongICC 2022 · OpenReview

Abstract

This paper studies the heterogeneous coded distributed computing (CDC) where input files required for job access have nonuniform popularity. We propose a file placement strategy that can handle an arbitrary number of input files and a nested coded shuffling strategy to effectively explore coded multicasting opportunities. We then formulate the joint optimization of the proposed file placement strategy and shuffling design variables into a mixed-integer linear programming (MILP) problem. To reduce the computational complexity, we propose a simple two-file-group-based approach to obtain an approximate solution. Numerical results show that the proposed two-file-group-based approach achieves nearly the same performance as solving the MILP problem using the conventional branch-and-cut method but with substantially lower computational complexity.
BibTeX
@inproceedings{deng2022heterogeneous,
  author = {Yong Deng and Min Dong},
  title = {{Heterogeneous Coded Distributed Computing with Nonuniform Input File Popularity}},
  booktitle = {ICC},
  year = {2022},
  url = {https://openreview.net/forum?id=HnaFSckh72},
}

Loading related content...

Figure