Cổng tri thức PTIT

Bài báo quốc tế

Kho tri thức

/

/

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


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..