Communication – Computation Tradeoffs in Distributed Computing and Networking

A key challenge in building next-generation wireless networks is to satisfy the increasing demand for data traffic and extended coverage for people and places without a corresponding rise in energy and carbon emissions.  There will be an explosion in wireless connectivity due to Internet-of-Things (IoT) devices, and these devices consume more energy for communication than for local processing.

One approach for prolonging the life of these devices is to increase the amount of computation at each node, such as by adding signal processing at the nodes, in order to reduce the number of bits that need to be communicated. 

Similarly, in distributed computing frameworks such as MapReduce, one can increase the computation load of the Map functions in order to reduce the communication overhead. Multihop wireless transmissions allow for nodes to transmit at low power levels and reuse the same frequency in different physical locations. 

In situations where battery life is important and communication to distant nodes should be avoided, distributed solutions are feasible. Distributed algorithms perform suboptimally when compared to a global centralized algorithm but can be implemented efficiently. 

The research focus of the Distributed Computing and Networking R&D group, led by Prof. Ashwin Ganesan, is on the theoretical foundations of distributed systems and networks. In ongoing research, the communication-computation tradeoff mentioned above is being investigated.

Consider the following fundamental problem in networking: what are the fundamental limits to the performance that is achievable if each node in the network has information about only its local neighborhood? Given that each link in a wireless network has a certain minimum-bandwidth quality-of-service requirement, is it possible to determine in a distributed manner whether the given set of flow rates is feasible?  

In recent research by the group, new distributed algorithms have been proposed for these problems and the tradeoff in performance between the level of decentralization and the performance of these distributed algorithms has been quantified.

Despite the large volume of prior work on this topic, this work has succeeded in cutting new ground – in analyzing models that have not been considered in the previous literature and in obtaining interesting and nontrivial performance bounds.  These research results were published in the journal IEEE/ACM Transactions on Networking in February 2020 and will be presented at the International Conference on Distributed Computing and Networking in January 2021.