Lossy Compression for Static Probabilistic Timing Analysis of Random Replacement Caches

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper outlines how Lossy Compression, a branch of
Information Theory relating to the compact representation
of data while retaining important information, can be applied
to the Worst Case Execution Time analysis problem.
In particular, this paper aims to motivate that by applying
lossy compression to the data structures involved in the
collecting semantics of a given component (for example, a
PLRU cache), showing how a useful analysis can be derived.
While such an analysis could be found via other means, the
application of Lossy Compression provides a formal method
and eases the process of discovering the analysis. Further,
as the compression and handling of the compression are formally
specied, such an analysis can be made correct-byconstruction
rather than relying on an after-the-fact proof.
Original languageEnglish
Title of host publicationRTNS '14
Subtitle of host publicationProceedings of the 22nd International Conference on Real-Time Networks and Systems
Number of pages10
ISBN (Print)978-1-4503-2727-5
Publication statusPublished - Oct 2014

Cite this