Online Caching Networks with Adversarial Guarantees
Yuanyuan Li, Tareq Si Salem, Giovanni Neglia, Stratis Ioannidis
2021Proceedings of the ACM on Measurement and Analysis of Computing Systems12 citationsDOIOpen Access PDF
Abstract
We study a cache network under arbitrary adversarial request arrivals. We propose a distributed online policy based on the online tabular greedy algorithm. Our distributed policy achieves sublinear (1-1/e)-regret, also in the case when update costs cannot be neglected. Numerical evaluation over several topologies supports our theoretical results and demonstrates that our algorithm outperforms state-of-art online cache algorithms.
Topics & Concepts
Sublinear functionComputer scienceRegretCacheAdversarial systemCache algorithmsNetwork topologyOnline algorithmState (computer science)Computer networkDistributed computingTheoretical computer scienceCPU cacheAlgorithmArtificial intelligenceMachine learningMathematicsMathematical analysisCaching and Content DeliveryOptimization and Search ProblemsAge of Information Optimization