Asymptotically Optimal Coded Distributed Computing via Combinatorial Designs

Coded distributed computing (CDC) introduced by Li et al. can greatly reduce the communication load for MapReduce computing systems. In the cascaded CDC with K workers, N input files and Q output functions, each input file will be mapped by r workers and each output function will be computed by s workers such that coding techniques can be applied to create multicast opportunities. The main drawback of most existing CDC schemes is that they require the original data to be split into a large number of input files that grows exponentially with K , which would significantly increase the coding complexity and degrade the system performance. In this paper, we first use a classical combinatorial structure t -design, for any integer t >= 2 >= 2 , to develop a low-complexity and communication-efficient CDC with r=s. Our scheme has much smaller N and Q than the existing schemes under the same parameters K , r , and s ; and achieves smaller communication loads compared with the state-of-the-art schemes when K is relatively large. Remarkably, unlike the previous schemes that realize on large operation fields, our scheme operates in one-shot communication on the minimum binary field F-2 . With a derived lower bound on the communication load under one-shot linear delivery, we show that the t -design scheme is asymptotically optimal. Furthermore, we show that our construction method can incorporate the other combinatorial structures that have a similar property to t -design. For instance, we use t -GDD to obtain another one-shot asymptotically optimal CDC scheme over F-2 that has different parameters from t -design. Finally, we show that our construction method can also be used to construct CDC schemes with r not equal s that have small file number and output function number. Like what you're reading?