In large-scale distributed linear transform problems, coded computation plays an important role to reduce the delay caused by slow machines. However, existing coded schemes could end up destroying the significant sparsity that exists in large-scale machine learning problems, and in turn increase the computational delay. In this paper, we propose a coded computation strategy, referred to as diagonal code, that achieves the optimum recovery threshold and the optimum computation load. Furthermore, by leveraging the ideas from random proposal graph theory, we design a random code that achieves a constant computation load, which significantly outperforms the existing best known result. We apply our schemes to the distributed gradient descent problem and demonstrate the advantage of the approach over current fastest coded schemes.

The cost of energy usage is of significant concern in cloud/data center systems that support a large number of servers. A simple way to reduce energy consumption and the electricity bill is to turn some of the servers off during periods of under utilization. However, turning a server back on typically consumes a lot of energy. Another way to reduce the energy cost is to equip cloud systems with renewable resources and batteries. Most works in the literature have focused on one or the other approach. In this work, we propose a joint server on-off and energy control policy, which determines the servers' on-off status, as well as the energy purchasing behavior, by taking electricity price, renewable resources, possible future tasks and turn-on cost into account. The server on-off control component is proved to be optimal in terms of energy consumption minimization. The joint policy is shown to be arbitrarily close to the optimal solution in terms of electricity bill minimization, in the case where the battery has infinite capacity with stable energy level. Simulation results show that even under reasonable battery size, a significant electricity cost reduction is achieved with the proposed policy.

In a large-scale and distributed matrix multiplication problem $C=A^{\intercal}B$, where $C\in\mathbb{R}^{r\times t}$, the coded computation plays an important role to effectively deal with “stragglers” (distributed computations that may get delayed due to few slow or faulty processors). However, existing coded schemes could destroy the significant sparsity that exists in large-scale machine learning problems, and could result in much higher computation overhead, i.e., $O(rt)$ decoding time. In this paper, we develop a new coded computation strategy, we call sparse code, which achieves near optimal recovery threshold, low computation overhead, and linear decoding time $O(nnz(C))$. We implement our scheme and demonstrate the advantage of the approach over both uncoded and current fastest coded strategies.

The energy consumption of cellular networks has increased dramatically due to high demand for wireless communication. Base-stations (BSs) use about 60% to 80% of the energy consumed by these networks. An attractive way to reduce energy consumption is to turn the BSs off during periods of under-utilization. However, turning a BS back on typically consumes a lot of energy, which has not been considered in previous works, but critical to good energy management strategies. In this work, we dynamically determine the on-off schedule of these base-stations by taking both operation-cost and turn-on-cost into account. We develop the first online algorithm that only uses future information to decide the on-off status of each BS and characterize its performance using competitive ratio analysis. We extend it by utilizing history information which helps improve the competitive ratio. A heuristic adaptive online algorithm is then designed to balance the utilization of history and future information. We then show via simulation results that the adaptive algorithm works well under a wide range of traffic intensities.