Upper Bounds for Multi-Level Multi-Server Paging Academic Article uri icon


  • The distributed multi-level multi-server paging (DMLMSP) problem defined in this paper extends and generalizes the classical distributed paging problem [3] to a distributed concurrent multi-level setting, in which multiple servers share caches at multiple levels. The DMLMSP problem can be used for modeling algorithms for efficient distributed storage systems, in which multiple servers use caches for accelerating access to a centralized storage, maintaining cache coherency across multiple nodes while minimizing access latency and optimizing cache-hit ratio. We present an optimal offline algorithm for the DMLMSP problem model, with minimum number of page faults and minimum makespan, whose time complexity is polynomial in the length of the servers' page request sequences.

publication date

  • June 29, 2017