Capacity Results of Coded Caching: The Pareto Optimal Frontier of the Two-User Case
Zhiqiang Luo, Nan Liu, Wei Kang · 2023
In this paper, we study the multi-objective problem in coded caching to minimize the rates of each demand type, which is equivalent to finding the Pareto optimal frontier. We focus on the problem with N files and 2 users, each with a cache size M. We fully characterize the Pareto optimal frontier by characterizing converse results on the rate of each demand type, and proving that the time-sharing of the memory-sharing of the schemes proposed in Maddah-Ali and Niesen can achieve any point on the Pareto optimal frontier. The result obtained contains the special case of finding the minimum worst-case delivery rate for the case of two users and N files, which has been solved by Maddah-Ali, Niesen and Chao. Our results show that in the case N = 2, M ∈ [0, 1], there is no universal scheme that is optimal for all demand types. Furthermore, coded cache placement is necessary to achieve the Pareto optimal frontier. However, for the case of N = 2, M ∈ [1, 2] and N ≥ 3, M ∈ [0, N], a single scheme is universal for any demand type, and uncoded cache placement is sufficient to achieve the Pareto optimal frontier.