Brief Announcement: Improved Understanding of Landlord Under Suffix Analysis

The suffix analysis problem provides a formal framework for analyzing the performance of cache replacement algorithms in the presence of pauses and restarts. However, little work has been done in this model. Currently bounds have only been proven for two particular algorithms from the Landlord (AKA Greedy-Dual Size) algorithm family. In this paper, we work to extend that knowledge to the more general family. We provide an upper bound for the suffix competitive ratio of all deterministic Landlord algorithms in the fault model of caching. We also show an asymptotically tight lower bound for the strongest candidate from the family in the same model.