ビルドキャッシュの前置性

上の鍵計算を用い、「$i$ 番目の命令がキャッシュヒットするのは、$i-1$ 番目までがすべてヒットし、かつ $k_i$ に対応するレイヤがローカルに存在するときに限る」という規則でビルドするとします。$H$ は衝突しないものとします。

このとき、キャッシュヒットする命令の集合はある $m$ に対して $\{1, 2, \ldots, m\}$ という前置集合になります。さらに、前回のビルドから $\sigma(I_j)$ が変化した最小の添字を $j$ とすると $m \le j - 1$ であり、$I_j, I_{j+1}, \ldots, I_n$ はすべて再実行されます。