Search

Communication overhead is one of the major performance bottlenecks in large-scale distributed computing systems, in particular for machine learning applications. Conventionally, compression techniques are used to reduce the load of communication by combining intermediate results of the same computation task as much as possible. Recently, via the development of coded distributed computing (CDC), it has been shown that it is possible to enable coding opportunities across intermediate results of different computation tasks to further reduce the communication load. We propose a new scheme, named compressed coded distributed computing (in short, compressed CDC ), which jointly exploits the above two techniques (i.e., combining the intermediate results of the same computation and coding across the intermediate results of different computations) to significantly reduce the communication load for computations with linear aggregation (reduction) of intermediate results in the final stage that are prevalent in machine learning (e.g., distributed training algorithms where partial gradients are computed distributedly and then averaged in the final stage). In particular, compressed CDC first compresses/combines several intermediate results for a single computation, and then utilizes multiple such combined packets to create a coded multicast packet that is simultaneously useful for multiple computations. We characterize the achievable communication load of compressed CDC and show that it substantially outperforms both combining methods and CDC scheme. Based on the compressed CDC technique, we then study a distributed training problem as one of its application. We characterize the communication load for this distributed training problem and show that it is asymptotically optimal.

Coded computing is a new framework to address fundamental issues in large scale distributed computing, by injecting structured randomness and redundancy. We first provide an overview of coded computing and summarize some recent advances. Then we focus on distributed matrix multiplication and consider a common scenario where each worker is assigned a fraction of the multiplication task. In particular, by partitioning two input matrices into $m$ -by- $p$ and $p$ -by- $n$ subblocks, a single multiplication task can be viewed as computing linear combinations of $pmn$ submatrix products, which can be assigned to $pmn$ workers. Such block-partitioning-based designs have been widely studied under the topics of secure, private, and batch computation, where the state of the arts all require computing at least “cubic” ( $pmn$ ) number of submatrix multiplications. Entangled polynomial codes, first presented for straggler mitigation, provides a powerful method for breaking the cubic barrier. It achieves a subcubic recovery threshold, i.e., recovering the final product from any subset of multiplication results with a size order-wise smaller than $pmn$ . We show that entangled polynomial codes can be further extended to also include these three important settings, providing unified frameworks that order-wise reduce the total computational costs by achieving subcubic recovery thresholds.

We consider the problem of interference management in wireless cellular networks with caches at both base stations and receivers and we characterize the degrees-of-freedom (DoF) per cell to within an additive gap of 1 and a multiplicative gap of 2 for all system parameters, under one-shot linear schemes. Our result indicates that the one-shot linear DoF per cell scales linearly with the total amount of cache that is available within each cell. A similar phenomenon had been previously observed for the case of fully-connected wireless networks. Hence, our result demonstrates that it also holds in cellular networks, despite the presence of path loss and fading which results in partial connectivity of the network topology. To establish the result, we propose a randomized and decentralized cache placement and a delivery scheme which, on one hand, utilizes the overlap of contents at base station caches to zero-force part of their outgoing interference, and on the other hand, uses the receiver caches to create coded multicasting opportunities, so that the receivers can eliminate the remaining interference due to undesired packets. We also provide a converse argument to show that our achievable one-shot linear DoF per cell is within an additive gap of 1 and a multiplicative gap of 2 of its optimal value.

We study the symmetric degrees-of-freedom (DoF) of partially connected interference networks under linear coding strategies at transmitters without channel state information beyond topology. We assume that the receivers are equipped with reconfigurable antennas that can switch among their preset modes. In such a network setting, we characterize the class of network topologies in which half linear symmetric DoF is achievable. Moreover, we derive a general upper bound on the linear symmetric DoF for arbitrary network topologies. We also show that this upper bound is tight if the transmitters have at most two co-interferers., Comment: This work will be presented in part at the 2016 IEEE International Symposium on Information Theory (ISIT)

We consider the problem of multiple-input single-output broadcast channels with Rayleigh fading where the transmitter has access to delayed knowledge of the channel state information. We first characterize the capacity region of this channel with two users to within constant number of bits for all values of the transmit power. The proposed signaling strategy utilizes the delayed knowledge of the channel state information and the previously transmitted signals, in order to create a signal of common interest for both receivers. This signal would be the quantized version of the summation of the previously transmitted signals. A challenge that arises in deriving the result for finite signal-to-noise ratio regimes is the correlation that exists between the quantization noise and the signal. To guarantee the independence of quantization noise and signal, we extend the framework of lattice quantizers with dither together with an interleaving step. For converse, we use the fact that the capacity region of this problem is upper bounded by the capacity region of a physically degraded broadcast channel with no channel state information where one receiver has two antennas. Then, we derive an outer bound on the capacity region of this degraded broadcast channel. Finally, we show how to extend our results to obtain the approximate capacity of the $K$ -user multiple-input single-output broadcast channel with delayed knowledge of the channel state information at the transmitter to within $2 \log _{2} ( K \,\, + 2 )$ bits/s/Hz.