Abstract
We propose a framework for edge-facilitated wireless distributed computing, in which several mobile users connected to an access point collaborate for a distributed computing task. We characterize the minimum communication load, both in uplink (from users to the access point) and downlink (from access point to the users), required for distributed computing. In particular, we develop a communication scheme and a dataset placement strategy that induces a particular overlap of computations at the users, which can then be exploited for coding at both users and the access point to significantly reduce the communication load. We demonstrate that the reduction in communication load (compared to uncoded solutions) can scale linearly with the size of the network (i.e., the number of users), hence our proposed scheme can result in a "scalable" design for edge- facilitated wireless distributed computing (i.e., accommodating any number of users without incurring extra communication load). Furthermore, we establish the optimality of the proposed scheme by developing a tight information theoretic outer- bound, and demonstrate that the proposed scheme achieves the minimum uplink and downlink communication load simultaneously. We also generalize the results to a decentralized setting, in which a random and a priori unknown subset of users may participate in distributed computing at each time, and characterize the minimum communication load for uniformly random dataset placement at users.
Original language | English (US) |
---|---|
Title of host publication | 2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
ISBN (Electronic) | 9781509013289 |
DOIs | |
State | Published - 2016 |
Externally published | Yes |
Event | 59th IEEE Global Communications Conference, GLOBECOM 2016 - Washington, United States Duration: Dec 4 2016 → Dec 8 2016 |
Publication series
Name | 2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings |
---|
Other
Other | 59th IEEE Global Communications Conference, GLOBECOM 2016 |
---|---|
Country/Territory | United States |
City | Washington |
Period | 12/4/16 → 12/8/16 |
Bibliographical note
Publisher Copyright:© 2016 IEEE.