ISIT 2021, International Symposium on Information Theory, 12-20 July, 2021, Melbourne, Victoria, Australia (Virtual Conference)
The work focuses on optimizing coded caching under asynchronous demands. We consider a single-stream setting where users are allowed to request content at arbitrary timeslots. Aiming to minimize the total system delay required to serve all users, i.e. from the moment of the first request to the delivery of the last bit of requested information, we design a pair of placement and delivery algorithms and show that the achievable performance is within a multiplicative factor of 2 from the optimal, under the assumption of uncoded placement, and within a multiplicative factor of 4:02 in the general placement
case. Interesting characteristics of our algorithms are that i) a placement phase agnostic to the users’ arrival times is adequate to provide a near-optimal delay, and ii) the proposed delivery algorithm requires low complexity and, at the same time, requires no non-causal information. Further, we show that systems are able to withstand some degree of asynchronicity without an increase in the delay compared to an equivalent synchronous
setting. Finally, we highlight an interesting connection between coded caching under asynchronous demands and coded caching in wireless environments under uneven channel strengths.
© 2021 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.