Coded Wireless Distributed Matrix Multiplication with Flexible Assignment of Output Vectors

Wireless distributed computing can be widely applied in the network edges to complete large-scale computing tasks. However, the existence of stragglers (nodes with less computing resources) and the heavy communication among nodes are two main bottlenecks in distributed systems which can affect the performance of distributed computing. Previous work [1] has proposed a unified framework to deal with the above two issues simultaneously in wireline scenarios. In this paper, we extend the framework in [1] to wireless distributed computing, where mobile devices are connected through an access point and collaborate for calculating massive distributed matrix multiplication. We allow a subset of devices first finishing local computations to participate in the output of the calculated result, which means the remaining slow devices (stragglers) are mitigated. In our extended framework, the assignment of output vectors is flexible, where the number of output vectors assigned for different devices can be different when the total output vectors cannot be divided equally among them. And the uplink transmission bandwidth from mobile devices to the access point is reduced compared to the wireline bandwidth in [1] due to different transmission scheme. After the uplink transmission, the downlink transmission bandwidth from the access point to mobile devices is further reduced by new coding technique. Furthermore, we prove information-theoretic lower bounds on uplink and downlink transmission loads respectively for flexible assignment of output vectors. And we derive the constant gaps when all devices finish their local computations if total output vectors can be assigned equally among them.