Wireless MapReduce distributed computing with full-duplex and straggling devices and imperfect CSI

Abstract

Consider a distributed computing system in which the worker devices are connected over a shared wireless channel. Devices can store a fraction of the data set over which computation needs to be carried out, and a Map-Shuffle-Reduce protocol is followed in order to enable collaborative processing. If there is exists some level of redundancy among the computations performed at the nodes, the inter-node communication load during the Shuffle phase can be reduced by using either coded multicasting or cooperative transmission. It was previously shown that the latter approach is able to reduce the high-Signal-to-Noise Ratio (SNR) communication load by half in the presence of full-duplex nodes and perfect transmit-side Channel State Information (CSI). In this work, a novel scheme based on superposition coding is proposed that is demonstrated to outperform both coded multicasting and cooperative transmission under the assumption of imperfect CSI. This work also considers an alternative scenario, relevant for wireless data centers and federated learning, in which the distributed processors, operating on generally distinct coded data, are connected via shared wireless channels accessed via full-duplex transmission. The study accounts for both wireless and computing impairments, including interference, imperfect Channel State Information, and straggling processors, and it assumes a Map-Shuffle-Reduce coded computing paradigm. The total latency of the system, obtained as the sum of computing and communication delays, is studied for different shuffling strategies revealing the interplay between distributed computing, coding, and cooperative or coordinated transmission.