What is Predictability?

Proving timeliness is an increasingly challenging task: contemporary processor architectures employ deep pipelines, branch predictors, and caches to improve performance. Further, multicore processors share buses, caches, and other resources. These features are claimed to make such processors "unpredictable".
Formally capturing the notion of predictability has so far proved to be hard. I present the first two formalizations of predictability for caches. Based on a discussion of their merits and shortcomings, I outline an array of exciting research challenges.