CIF: Small: Fundamental Tradeoffs Between Communication Load and Storage Resources in Distributed systems

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

Future data communication networks will have to support multitude of devices abundantly spread all over, collecting, processing and transferring data on the fly. Such networks are expected to struggle to meet the demand from such data communication needs. At the same time, the devices can leverage their inexpensive and distributed memory units to reduce the cost of exchanging information. A key question is which data should be placed in the memories so that, irrespective of what the devices will be requested to compute in the future, the amount of communication to satisfy these requests will be the smallest possible. The more devices the system can satisfy with a single transmission, the larger the savings are in terms of reduction of the number of transmissions. These savings translate to reduced communication costs and an ability to run computation-intensive and latency-critical applications at resource-limited devices. This project aims to develop the theoretical and algorithmic foundation for distributed computation in presence of local and limited storage resources for future hybrid hierarchical networks, where distributed devices collaborate to solve big-data inference tasks. Despite their fundamental nature, the results of this research are impact the design of emerging communication models in industry. This project also develops a rich educational program for students, who will acquire critical skills to be successful in a competitive, diverse, and global workforce market. This research identifies critical questions related to communication in distributed peer-to-peer settings with local limited storage resources. The technical aims of the project are divided into two related thrusts: distributed cache-aided "Fog Radio Access Network" architectures and peer-to-peer distributed data shuffling. The former problem models the hybrid network architecture envisaged for 5G wireless networks, while the latter finds applications in distributed computation in big data and machine learning algorithms. Both share the caching theme, i.e., leverage local storage to reduce global communication load, but more importantly leverage the distributed nature of the encoding in either the delivery or data shuffling phase. The concomitant technical questions are novel in many aspects, and span information theory, coding theory, and combinatorics. The research includes innovative approaches to derive converse and achievable bounds, with provable performance guarantees. The overarching goal is to develop a fundamental framework for distributed computation, with implications to other open problems such as distributed index coding and distributed interference alignment. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.