ISIT 2021, Melbourne, Victoria, Australia
Modern algorithms need to efficiently execute complex queries on massive databases in a way that minimizes the use of communication resources while preserving the privacy of the entity that initiated the query. Such queries are functions of the data points that are stored at remote servers. For example, linear and multivariate polynomial operations are widely used fundamental primitives for building the complex queries that support on-line big-data analytics and data mining procedures. In those scenarios, it is too resource-consuming to download locally all the input variables in order to compute the desired output value. Instead, it is desirable to directly download the result of the desired output function, which should also be kept private. This tutorial introduces a principled and holistic framework for the problem of privately retrieving, at distributed cache-aided nodes, the output of functions based on both data that is locally computed and data that is received from multiple servers. This problem is at the intersection of distributed coded caching and private information retrieval. This tutorial has three major parts: (1) design optimal coded caching schemes for user-private general function retrieval; (2) motivated by distributed settings in which a user may also be a sender, devise optimal server-private function retrieval strategies; and (3) overcome complexity bottleneck in practical distributed computing systems with server- and/or user-privacy. The goal of this tutorial is to provide an overview of significant results on the topic, together with a comprehensive list of relevant past contributions for distributed coded caching and private information retrieval, and point to open research directions.