Coded MapReduce Schemes Based on Placement Delivery Array
Vinayak Ramkumar, P. Vijay Kumar · 2019
The coded MapReduce framework introduced in [1] gives a method to tradeoff extra computation for reduced communication, in-order to speedup operations for which communication is the bottleneck. In [2], it has been demonstrated that reducing the number of subfiles required in coded MapReduce at the cost of a slightly higher communication load is beneficial for certain problems. The placement delivery array (PDA), introduced in [3], is a structure used to develop coded caching schemes with small sub-packetization. In the present paper, we use PDA to come up with a method to construct coded MapReduce schemes which require smaller number of subfiles. This method gives a way to tradeoff between the number of subfiles and the communication required. We also address the problem of mitigating the impact of slow servers at the map phase on the reduce operations of normal servers.