Bài báo quốc tế
Kho tri thức
/
Bài báo quốc tế
/
APractical Evaluation of Paging Algorithm Smoothness: Trade-offs Between Competitiveness and Stability
APractical Evaluation of Paging Algorithm Smoothness: Trade-offs Between Competitiveness and Stability
Nguyễn Minh Tuấn
Traditional evaluation
metrics, such as competitive ratio, measure an algorithm’s worst
case efficiency relative to an optimal offline algorithm. However,
such metrics fail to capture the algorithm’s sensitivity to small
changes in input sequences- an aspect essential in real-time and
secure systems. This paper investigates the notion of smoothness,
a quantitative measure of how stable a paging algorithm’s perfor
mance is under minor perturbations of its request sequence. We
extend prior theoretical work by conducting a practical and empiri
cal evaluation of several key paging strategies, including LRU, FIFO,
SMOOTHED-LRU, and LRU-RANDOM. Through a series of simu
lations on synthetic and adversarial input sequences, we evaluate
both the smoothness and competitiveness of each algorithm. Our
results confirm the theoretical findings that LRU, though competi
tive, is not smooth, while SMOOTHED-LRU and LRU-RANDOM
demonstrate improved stability at the cost of marginal competitive
ness loss. Furthermore, we simulate side-channel attacks to assess
the security implications of low-smoothness algorithms. The exper
iments highlight how smooth algorithms can mitigate cache-based
information leakage. This trade-off analysis offers new insights for
the design of memory systems where both performance and ro
bustness are critical, particularly in real-time and security-sensitive
environments.
Xuất bản trên:
APractical Evaluation of Paging Algorithm Smoothness: Trade-offs Between Competitiveness and Stability
Ngày đăng:
2026
Nhà xuất bản:
Địa điểm:
Từ khoá:
Online algorithms; Theory of com putation; Approximation algorithms analysis; Mathematics of computing; Probability and statistics..
