Анализ неуспешных обращений к кэшу: различия между версиями

Здесь <math>1 \le \alpha < e</math> и <math>\beta(1) = 2, \beta(\infty) = 1 + e \approx 3.71</math>. Этот анализ предполагает, что соперник планирует доступ к последовательностям. Для нижней границы соперник первоначально продвигает последовательность <math>s_i</math> для i = 1, ..., k на <math>X_i</math> элементов, где <math>X_i</math> выбираются равномерно и независимо из {0,  M - 1}. Затем соперник обращается к последовательностям в порядке круговой очереди.

Параметр k в верхней границе учитывает возможный дополнительный блок, обращение к которому может выполняться из-за рандомизации начальных адресов. Член -kM в нижней границе учитывает тот факт, что неудачные обращения к кэшу не могут быть подсчитаны, когда соперник изначально сдвигает последовательности.