Fairness in the k-Server Problem

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

TL;DR

This paper introduces and formalizes the concept of "fairness" for the k-server problem, aiming to distribute the workload (server movement cost) equitably among servers, not just minimize the total cost. They develop algorithms that achieve this fairness with minimal loss in competitiveness, both in offline and online settings, and investigate the fairness properties of existing algorithms on specific metric spaces.

What Problem Does This Paper Address?

The k-server problem is a classic online algorithm problem where k servers move in a metric space to serve a sequence of requests, with the goal of minimizing total movement cost. While much research has focused on minimizing this total cost (competitiveness), this paper addresses a crucial aspect often overlooked in practical distributed systems: fairness. In many real-world scenarios, it's not enough to minimize the total cost; the cost must also be distributed equitably among the servers. Imagine a fleet of delivery vehicles: minimizing total travel distance is important, but so is ensuring no single vehicle is consistently overworked. This paper tackles the challenge of achieving both competitiveness and fairness simultaneously in the k-server setting.

Methods

The authors introduce a formal definition of (α, β)-fairness, where no server incurs more than an α/k fraction of the total cost plus an additive term β. They then propose several algorithmic approaches:

  • Offline Fairness: They develop a deterministic algorithm that transforms any optimal offline solution into an (α, β)-fair solution with minimal cost increase. This algorithm uses a series of pairwise server swaps to gradually balance server loads.
  • Online Fairness (Randomized): For the online setting, they propose a randomized algorithm that uses phased random swapping. This technique involves periodically permuting server identities and positions to ensure that, with high probability, server costs are balanced. This approach balances the number of swaps to avoid excessive cost increases while maintaining fairness guarantees.
  • Fairness of Existing Algorithms: They analyze the fairness properties of well-known deterministic algorithms like the Double Coverage Algorithm (DCA) on tree metrics and the First-In First-Out (FIFO) and Least Recently Used (LRU) algorithms on uniform metrics (paging problem). This involves proving positive fairness results for some cases and demonstrating limitations in others.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design, using abstract metric spaces and request sequences as its "data."

Key Insights and Ideas

  • Formalizing Fairness: The introduction of the (α, β)-fairness definition provides a concrete mathematical framework for discussing and analyzing fairness in the k-server problem.
  • Offline Fairness is Achievable: The paper demonstrates that strong fairness can be achieved in the offline setting without sacrificing much competitiveness, using a clever pairwise swapping strategy.
  • Randomization for Online Fairness: For online settings, randomization is key. The phased random swapping technique shows that even against an oblivious adversary, fairness can be achieved with high probability.
  • DCA's Mixed Bag: The Double Coverage Algorithm (DCA), a standard for tree metrics, exhibits good fairness on line and k=2 tree metrics but can be surprisingly unfair on general tree metrics for larger k. This highlights that competitive algorithms don't automatically imply fair ones.
  • FIFO's Strong Fairness: The FIFO algorithm, a classic in paging, is shown to be remarkably fair, achieving near-perfect balance. This suggests that simple, well-established algorithms can sometimes offer strong fairness guarantees.

Key Results

  • Offline: An algorithm achieves (1 + ε, β)-fairness with β = O(diam log k/ε) and a total cost increase of O(diam k log k/ε) over the optimal offline cost.
  • Online (Randomized): A randomized algorithm achieves (α, β)-fairness with α = 1 + ε and β = O(c(σ)¹/(γ+1) * diam) with high probability, where c(σ) is the base algorithm's cost. The total cost increase is sublinear in c(σ).
  • DCA on Line Metrics: DCA is (1, O(k * diam))-fair.
  • DCA on Tree Metrics (k=2): DCA is (1.5, 1.75 * diam)-fair.
  • DCA on General Tree Metrics (General k): DCA can be highly unfair, with one server incurring Ω(k * OPT(σ)) cost.
  • FIFO on Uniform Metrics: FIFO is (1,1)-fair, meaning it's essentially perfectly fair.
  • Marking Algorithms on Uniform Metrics: These algorithms (including LRU) guarantee that no server pays more than OPT(σ) cost.

Limitations and Future Work

  • Deterministic Online Fairness: A major open question is whether fairness can be achieved by deterministic online algorithms with a competitive ratio of O(k) against adaptive adversaries. The paper makes progress but doesn't fully resolve this.
  • Stronger Adversaries: The randomized online algorithm is analyzed against oblivious adversaries. Extending this to adaptive adversaries (who can see server identities) is a significant open problem.
  • General Tree Metrics: While DCA is fair on specific tree structures, its unfairness on general tree metrics for k > 2 remains a challenge.
  • Generalization to Other Problems: The authors suggest exploring (α, β)-fairness for other generalizations of the k-server problem, such as metrical task systems.
  • Parameter 'diam': The additive fairness bounds depend on the diameter of the metric space. The authors note this can be removed by absorbing it into the multiplicative term, but it adds complexity to the presentation.

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 Mohammad Hajiesmaili and Shahin Kamali and Helia Karisani and Cameron Musco},
  title = {{Fairness in the k-Server Problem}},
  booktitle = {ITCS},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.45},
}
Figure