{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/107992"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/107992","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A Lyapunov analysis of LRU","abstract":"Caches are segments of memory that store requested information in a system subject to a set of decision rules, defined as the caching algorithm. One of the most popular caching algorithms is the least recently used algorithm (LRU) due to its simplicity and effectiveness in a multitude of applications. LRU caches operate by storing objects in the order that they were most recently requested. Further, whenever an item is requested that is not currently in the cache, the requested item is placed at the head of the cache, and the least recently requested item is evicted. Many have suggested a tie between the performance of an LRU cache and a time to live (TTL) cache. In this thesis, we present a unique Lyapunov based proof for an asymptotically exact TTL approximation for the steady state distribution of our LRU Markov model. We further present ongoing theoretical extensions to other variants of LRU, as well as simulations that validate our model. We conclude by proposing a variance corrected model to better approximate hit rate over time.","abstract_html":"Caches are segments of memory that store requested information in a system subject to a set of decision rules, defined as the caching algorithm. One of the most popular caching algorithms is the least recently used algorithm (LRU) due to its simplicity and effectiveness in a multitude of applications. LRU caches operate by storing objects in the order that they were most recently requested. Further, whenever an item is requested that is not currently in the cache, the requested item is placed at the head of the cache, and the least recently requested item is evicted. Many have suggested a tie between the performance of an LRU cache and a time to live (TTL) cache. In this thesis, we present a unique Lyapunov based proof for an asymptotically exact TTL approximation for the steady state distribution of our LRU Markov model. We further present ongoing theoretical extensions to other variants of LRU, as well as simulations that validate our model. We conclude by proposing a variance corrected model to better approximate hit rate over time.","abstract_has_math":false,"creators":["Brenner, Michael"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-08-26T21:54:53Z","date_published":"2020-08-26T21:54:53Z","updated_at":"2026-07-22T22:24:47Z","subjects":["Lyapunov","Control Thoery","Stochastic Systems","Cache","LRU","Least recently used","Markov Chain","TTL"],"languages":["en"],"rights":["Copyright 2020 Michael Brenner"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/107992","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Brenner, Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-08-26T21:54:53Z","2020-05-11","2020-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Lyapunov","Control Thoery","Stochastic Systems","Cache","LRU","Least recently used","Markov Chain","TTL"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Michael Brenner"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/107992"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Caches are segments of memory that store requested information in a system subject to a set of decision rules, defined as the caching algorithm. One of the most popular caching algorithms is the least recently used algorithm (LRU) due to its simplicity and effectiveness in a multitude of applications. LRU caches operate by storing objects in the order that they were most recently requested. Further, whenever an item is requested that is not currently in the cache, the requested item is placed at the head of the cache, and the least recently requested item is evicted. Many have suggested a tie between the performance of an LRU cache and a time to live (TTL) cache. In this thesis, we present a unique Lyapunov based proof for an asymptotically exact TTL approximation for the steady state distribution of our LRU Markov model. We further present ongoing theoretical extensions to other variants of LRU, as well as simulations that validate our model. We conclude by proposing a variance corrected model to better approximate hit rate over time.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo terms","The student, Michael Brenner, accepted the attached license on 2020-05-05 at 09:31.","The student, Michael Brenner, submitted this Thesis for approval on 2020-05-05 at 09:38.","This Thesis was approved for publication on 2020-05-11 at 07:16.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15210 on 2020-08-25 at 17:12:13","Made available in DSpace on 2020-08-26T21:54:53Z (GMT). No. of bitstreams: 2 BRENNER-THESIS-2020.pdf: 455094 bytes, checksum: 4015ffe09ac171aa11f36b07d365a48b (MD5) LICENSE.txt: 4212 bytes, checksum: fed6f97b9c558ce39e9627be10915b92 (MD5) Previous issue date: 2020-05-11"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["A Lyapunov analysis of LRU"]}]}],"canonical_facts":{"dc:contributor":["Srikant, Rayadurgam"],"dc:creator":["Brenner, Michael"],"dc:date":["2020-08-26T21:54:53Z","2020-05-11","2020-05"],"dc:description":["Caches are segments of memory that store requested information in a system subject to a set of decision rules, defined as the caching algorithm. One of the most popular caching algorithms is the least recently used algorithm (LRU) due to its simplicity and effectiveness in a multitude of applications. LRU caches operate by storing objects in the order that they were most recently requested. Further, whenever an item is requested that is not currently in the cache, the requested item is placed at the head of the cache, and the least recently requested item is evicted. Many have suggested a tie between the performance of an LRU cache and a time to live (TTL) cache. In this thesis, we present a unique Lyapunov based proof for an asymptotically exact TTL approximation for the steady state distribution of our LRU Markov model. We further present ongoing theoretical extensions to other variants of LRU, as well as simulations that validate our model. We conclude by proposing a variance corrected model to better approximate hit rate over time.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo terms","The student, Michael Brenner, accepted the attached license on 2020-05-05 at 09:31.","The student, Michael Brenner, submitted this Thesis for approval on 2020-05-05 at 09:38.","This Thesis was approved for publication on 2020-05-11 at 07:16.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15210 on 2020-08-25 at 17:12:13","Made available in DSpace on 2020-08-26T21:54:53Z (GMT). No. of bitstreams: 2 BRENNER-THESIS-2020.pdf: 455094 bytes, checksum: 4015ffe09ac171aa11f36b07d365a48b (MD5) LICENSE.txt: 4212 bytes, checksum: fed6f97b9c558ce39e9627be10915b92 (MD5) Previous issue date: 2020-05-11"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/107992"],"dc:language":["en"],"dc:rights":["Copyright 2020 Michael Brenner"],"dc:subject":["Lyapunov","Control Thoery","Stochastic Systems","Cache","LRU","Least recently used","Markov Chain","TTL"],"dc:title":["A Lyapunov analysis of LRU"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:47Z"}