The general theme of our research is to develop innovative approaches to characterize and achieve the fundamental limits of reliable, trustworthy, and verifiable distributed systems, including distributed computing and machine learning, content delivery networks, and distributed ledgers (blockchains).
Secure and Private Distributed Computing
Distributed computing raises a long list of challenges, including the heavy load of communication, the existence of stragglers, information leakage to external servers, etc. We took the first step toward understanding distributed computing from an information-theoretic perspective. We characterized the communication-computation trade-off for one of the most popular general-purpose settings, adopted in MapReduce and Apache Spark. In addition, we developed a coding approach that achieves the optimum trade-off and significantly reduces the communication load. While the benefits of coding in dealing with the stragglers in linear and bilinear computations, such as distributed massive matrix multiplications, were studied in the 80’s , designing the optimum code remained an open problem. In this regard, we developed a creative polynomial-based coding technique with optimum robustness against stragglers.
In this direction, we also radically extended secure multi-party computation (MPC) to handle massive computations, a subject that has been overlooked in the field. We also developed efficient and practical approaches to private machine learning, and straggler-resistant massive approximate computation, particularly for machine learning applications.
Coded Caching
The conventional approach to reducing the traffic load is to exploit the memories distributed across the network to duplicate (or cache) the popular content. Today’s content delivery networks are designed and optimized to increase hit rate, i.e., the chance of providing requested content from a local cache. We proved that this intuitive approach is substantially inefficient. We presented the first information-theoretic fundamental trade-off between the communication rate and cache size
for distributed cache networks and proved its optimality. To achieve optimum performance, we introduced the concept of coded caching, which relies on planning and exploiting the cached content to create particular coding opportunities. The gain offered by coded caching scales with the size of the network, which makes it even more attractive for overwhelmingly growing networks.
To translate this idea into practice, and in interaction with the business division of Nokia, we further extended the concept of coded caching to support various real-world scenarios. In particular, we addressed the cases where file popularities are non-uniform and time-varying, and the demands are asynchronous and delay-sensitive. We also generalized the proposed scheme to hierarchical cache networks or cache-aided wireless channels. Our practical implementations (Demo) demonstrated at the company’s showcases intrigued many visitors and business partners.
Interference Management using Outdated Channel State Information
The communication delay in distributed systems can significantly affect the network’s performance. An example of such systems is multi-user communication networks, where interference management techniques rely on up-to-date channel state information (CSI). However, estimating and circulating this knowledge is subject to some delay, making it outdated. There was an unquestioned belief that outdated CSI, uncorrelated with the current one, is entirely useless. We developed an innovative approach, leveraging the outdated CSI, to improve the throughput of a K-user (Broadcast) wireless network by a factor of K/log(K). Our proposed approach has initiated a new way to utilize outdated CSI, which has been extensively explored for various network settings.
Interference Alignment
Competition for communication medium is an inherent attribute of distributed systems, where concurrent interactions create interference on each other. In the absence of collaborative interference management, the communication links were conventionally scheduled in different orthogonal dimensions. In [9], we disproved this prevailing belief and introduced a fundamentally new approach to managing interference. Our so-called interference alignment (IA) scheme provides interference-free communication without splitting the network resources and sacrificing the throughput. This is done by aligning different interference contributions at each receiver to minimize their overall footprint. The surprising consequence is that when a new link starts communicating over the shared medium, it ideally will not affect the rate of the other links. Over the past few years, interference alignment has been one of the central topics of research in the field, with significant implications beyond interference management in distributed storage, computation, and private information retrieval.