Fairness in the k-Server Problem

Mohammadreza Daneshvaramoli, Helia Karisani, Mohammad Hajiesmaili, Shahin Kamali, Cameron Musco

TL;DR

This paper introduces a formal framework for fairness in the classic $k$-server problem, ensuring that the total movement cost is distributed equitably among all servers. The authors demonstrate that near-perfect fairness can be achieved in both offline and randomized online settings without significantly sacrificing competitiveness, while revealing surprising fairness limitations in classic deterministic algorithms like Double Coverage (DCA).

What Problem Does This Paper Address?

The $k$-server problem is a foundational problem in online algorithms. Given $k$ servers moving in a metric space, the goal is to service a sequence of requests over time while minimizing the total distance traveled. While decades of research have focused on optimizing this utilitarian cost, they completely ignore how the workload is distributed among individual servers.

In real-world applications—such as dispatching delivery drones, managing virtual machines in a cloud cluster, or routing ride-share vehicles—overburdening a single server leads to disproportionate wear-and-tear, battery depletion, or driver burnout. This paper tackles the challenge of balancing the workload fairly among servers while maintaining low total cost (competitiveness).

Methods

The authors formalize a novel metric called $(\alpha, \beta)$-fairness. Under this definition, an algorithm is fair if no single server incurs a cost greater than an $\alpha/k$ fraction of the total cost, plus an additive slack term $\beta$. A perfectly fair algorithm would have $\alpha=1$ and $\beta=0$.

To achieve this, they propose two main algorithmic frameworks:

  1. Offline Pairwise Swapping (Algorithm 1): A deterministic, polynomial-time algorithm that takes any optimal (but potentially unfair) solution and iteratively balances it. It identifies the heaviest- and lightest-loaded servers and swaps their future workloads at a carefully calculated time step where their remaining costs are nearly equal.
  2. Online Phased Random Swapping (Algorithm 2): A randomized online algorithm designed to work against an oblivious adversary. It divides the request sequence into phases based on cost thresholds. At the start of each phase, it randomly permutes server identities and positions. By using concentration inequalities (specifically Bernstein's inequality), the authors prove that this shuffling guarantees ex-post fairness with high probability.

Additionally, the authors rigorously analyze the inherent fairness properties of classic deterministic online algorithms, such as the Double Coverage Algorithm (DCA) on trees and First-In First-Out (FIFO) and Least Recently Used (LRU) for paging.

Datasets

Not discussed in the paper. As a theoretical computer science paper, the results are established through rigorous mathematical proofs rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Fairness is "Free" in the Long Run: In both the offline and randomized online settings, you can achieve near-perfect fairness ($\alpha = 1+\epsilon$) with only a small, additive or sublinear penalty to the total cost. The cost overhead depends on the metric space's diameter and the number of servers, but crucially, it does not scale with the length of the request sequence.
  • The Unfairness of Double Coverage: While the classic Double Coverage Algorithm (DCA) is optimally $k$-competitive on tree metrics, it can be brutally unfair. On general trees, DCA can trap servers in a pattern that forces a single server to do a massive majority ($\Omega(k \cdot \text{OPT})$) of the work while others sit idle.
  • FIFO Beats LRU in Fairness: On uniform metrics (the classic paging problem), FIFO is perfectly fair up to an additive constant of 1 because it strictly cycles through cache slots. Conversely, LRU can be highly unfair, repeatedly hitting the same cache slot in certain worst-case request patterns.

Key Results

  • Offline Setting: The authors prove that any optimal solution can be transformed into a $(1+\epsilon, \beta)$-fair solution where $\beta = O(\text{diam} \cdot \log k / \epsilon)$, with a total cost increase of just $O(\text{diam} \cdot k \log k / \epsilon)$.
  • Online Randomized Setting: Algorithm 2 achieves $(1+\epsilon, \beta)$-fairness with high probability against an oblivious adversary, with sublinear cost overhead.
  • Deterministic Online Analysis: The paper maps out the fairness landscape for classic deterministic algorithms, showing that DCA is fair on lines and 2-server trees, and FIFO is fair for paging.

The deterministic online results are summarized in the table below:

Summary of deterministic fair online algorithms for different metrics

Limitations and Future Work

The randomized online fairness guarantees hold against an oblivious adversary (or an ID-oblivious adaptive adversary), leaving open the question of whether high-probability fairness can be achieved against a fully adaptive adversary who can observe server identities.

Additionally, a major open question remains: Does there exist a deterministic online algorithm that is $O(k)$-competitive and $(\alpha, \beta)$-fair on general metric spaces? Finally, the authors suggest extending this fairness framework to other online problems, such as metrical task systems.

Summary updated

Abstract

We initiate a formal study of fairness for the $k$-server problem, where the objective is not only to minimize the total movement cost, but also to distribute the cost equitably among servers. We first define a general notion of $(α,β)$-fairness, where, for parameters $α\ge 1$ and $β\ge 0$, no server incurs more than an $α/k$-fraction of the total cost plus an additive term $β$. We then show that fairness can be achieved without a loss in competitiveness in both the offline and online settings. In the offline setting, we give a deterministic algorithm that, for any $\varepsilon > 0$, transforms any optimal solution into an $(α,β)$-fair solution for $α= 1 + \varepsilon$ and $β= O(\mathrm{diam} \cdot \log k / \varepsilon)$, while increasing the cost of the solution by just an additive $O(\mathrm{diam} \cdot k \log k / \varepsilon)$ term. Here $\mathrm{diam}$ is the diameter of the underlying metric space. We give a similar result in the online setting, showing that any competitive algorithm can be transformed into a randomized online algorithm that is fair with high probability against an oblivious adversary and still competitive up to a small loss. The above results leave open a significant question: can fairness be achieved in the online setting, either with a deterministic algorithm or a randomized algorithm, against a fully adaptive adversary? We make progress towards answering this question, showing that the classic deterministic Double Coverage Algorithm (DCA) is fair on line metrics and on tree metrics when $k = 2$. However, we also show a negative result: DCA fails to be fair for any non-vacuous parameters on general tree metrics.
BibTeX
@inproceedings{daneshvaramoli2026fairness,
  author = {Mohammadreza Daneshvaramoli and Helia Karisani and Mohammad Hajiesmaili and Shahin Kamali and Cameron Musco},
  title = {{Fairness in the k-Server Problem}},
  booktitle = {ITCS},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.45},
}
Figure