No justified complaints: On fair sharing of multiple resources

1. INTRODUCTION

• Fair allocation has been studied in economics and computer science, but much prior resource-sharing work focused on one resource.The introduction situates the work in both fields and points to fair-share scheduling in operating systems.Source: §1 · p. 2
• The proposed notion targets multiple continuously divisible resources shared by users with different needs and pre-negotiated entitlements.The paper says its approach applies beyond its operating-systems motivation wherever users share different resources under entitlements.Source: §1 · p. 2
• A CPU-centric approach can make disk usage a bottleneck, leaving the disk controller’s scheduling to shape overall system use.The paper argues that this can make a CPU-focused view inappropriate when enforcing predefined resource allocations.Source: §1 · p. 2
• Different users’ resource profiles can make two or more resources bottlenecks at once, such as when CPU- and I/O-heavy processes share a system.A third process using both resources can contribute to both bottlenecks.Source: §1 · p. 3
• The proposed fairness definition requires each user to receive an entitlement on at least one bottleneck resource, so users cannot justifiably complain under fixed resource-use proportions.The paper states that a fair allocation is guaranteed to exist and that its constructive proof provides a numerical computation method.Source: §1 · p. 3

2. PRIOR WORK

• Many established fair-share approaches focus on a single resource, such as CPU or one network link, rather than enforcing desired allocation across resources.The paper also notes work on scheduling bottleneck devices for performance, not for enforcing a desired allocation.Source: §2 · p. 3
• Other multiple-resource work addresses application usage control, packet scheduling, load balancing, or performance goals rather than predefined resource allocations.The paper cites these differing aims in its review of multiple-resource constraints.Source: §2 · p. 3
• Bottleneck-based scheduling identifies the device closest to full utilization and enforces desired relative allocations there, but prior versions do not handle multiple bottlenecks.The paper extends this approach to cover multiple bottlenecks.Source: §2 · p. 4
• For network flows, min-max fairness has a geometrical characterization similar to the paper’s, but equal resource requirements make finding a solution easier.The paper contrasts this with its more complicated trajectory for differing resource requirements.Source: §2 · p. 4
• Dominant resource fairness is identified as the only other policy then known to analyze fair sharing with diverse requirements across multiple resources.It focuses on each user’s maximal use of any one resource rather than explicitly identifying bottlenecks.Source: §2 · p. 4

3. SHARING MULTIPLE RESOURCES

• When aggregate requests exceed capacity on multiple resources, the section asks how fairness should be defined across those simultaneous bottlenecks.With no bottleneck, users can receive all requests; with only one, the section describes cutting back users above entitlement as straightforward.Source: §3 · p. 4
• Different resource requirements make fixed CPU-centered allocations problematic: an I/O-bound user's unused CPU share may be wasted or its reallocation may hurt that user.The section motivates allocations that exploit complementary usage profiles while respecting entitlements.Source: §3 · p. 4
• The model assumes each user consumes resources in fixed proportions, so cutting one resource by a factor cuts the others by the same factor.This excludes patterns where one resource compensates for another, such as paging or compression.Source: §3 · pp. 4–5
• Allocations must keep each resource's total usage within capacity; a resource is a bottleneck when its capacity constraint holds with equality.The allocation variable is the common fraction of each user's request that is granted across resources.Source: §3 · p. 5
• A user has no justified complaint if they receive everything requested or meet their entitlement on at least one fully used bottleneck resource.Because increasing that user's allocation would consume capacity already used by others, it would come at their expense.Source: §3 · p. 5
• The paper states that fair allocations are Pareto optimal and that its main theorem guarantees one exists, while a straightforward user-by-user greedy construction does not work.Adding a later user may require cutting back earlier users, so the earlier assignment may need to be redone.Source: §3 · p. 5

• The allocation is at least as good for each user as receiving their entitlement on every resource, providing an incentive to share.If entitlement on each resource supports fraction x of a user's requests and the fair allocation supports fraction y, then x ≤ y.Source: §4 · p. 5
• The definition is strategyproof: misreporting resource needs cannot benefit a user and can reduce their effective allocation.Inflating an unneeded resource can make the system treat the user's entitlement as satisfied; requesting more with the same resource profile may instead waste allocation.Source: §4 · p. 6
• The allocation is envy-free and Pareto efficient: no user prefers another's allocation, and increasing one user's allocation comes at another's expense.Envy-freeness follows from strategyproofness; Pareto efficiency follows from allocating based on bottlenecks.Source: §4 · p. 6
• Unlike dominant resource fairness, the definition uses system-wide bottlenecks rather than each user's dominant resource to assess allocation.When utility is unknown, the paper counts allocated resources; use of an uncongested resource does not count toward fairness under its bottleneck criterion.Source: §4 · p. 6
• The definition extends bottleneck fairness to multiple bottlenecks and differing dominant resources, whereas the DRF treatment described here limits bottleneck fairness to users with the same dominant resource.The paper states that an allocation is harder to find because the bottlenecks are not known in advance, but proves that one always exists.Source: §4 · pp. 6–7
• The definition and dominant resource fairness are equivalent when all users have the same dominant resource.In that case, the common dominant resource is the only bottleneck.Source: §4 · p. 6

5. EXISTENCE OF A FAIR ALLOCATION

• For entitlements summing to one and admissible requests, a feasible allocation exists in which every user meets their entitlement on a saturated resource.Dummy resources let the proof treat users who receive everything they request as meeting the same formal condition.Source: §5 · p. 7

5.1 Simplifying Assumptions

• Without loss of generality, the proof ignores slack resources, grants and removes users whose requests stay below entitlement while renormalizing the remainder, and removes dominated constraints.The remaining users’ entitlements, requests, and resource capacities are renormalized so the reduced problem yields a solution to the original one.Source: §5.1 · p. 7

5.2 Proof Structure

• Because bottlenecks are unknown, the proof rounds the feasible polytope into smooth sets, finds qualifying boundary points using ordinary differential equations, and takes a convergent limit back to the feasible region.If the bottleneck set were known, the corresponding feasibility test could instead be solved as a linear program.Source: §5.2 · p. 8

5.3 The Case N = 2

• For two users, smoothing the feasible boundary yields a unique fair allocation and a uniquely determined bottleneck set, which may contain multiple resources.The proof’s limit argument covers both a point on one resource constraint and an intersection where multiple resources are bottlenecks.Source: §5.3 · pp. 8–9

5.4 Proof of Theorem 1

• For the general proof, a positive function on the feasible region’s interior diverges at its boundary, and its level sets form hypersurfaces.The level sets are introduced as part of the construction used in the arbitrary-user proof.Source: §5.4 · pp. 9–10
• The constructed trajectory has a boundary accumulation point that is a fair allocation, with every user meeting entitlement on at least one bottleneck resource.The trajectory has a convergent subsequence approaching the boundary of D, and the resulting allocation satisfies the fairness condition.Source: §5.4 · pp. 10–11
• An x-dependent symmetric positive-definite system gives a unique trajectory by the Fundamental Theorem of Ordinary Differential Equations [9]; boundedness of D ensures global existence.The proof establishes a unique solution for the derivative system, then uses continuity and boundedness to obtain global existence.Source: §5.4 · p. 11
• The proof is almost constructive: standard ODE integrators can compute trajectories, but finite-interval numerical solutions are approximate, with controllable error.If the trajectory tends to a limit for large t, that limit is a fair allocation.Source: §5.4 · p. 11

5.5 Uniqueness of the Solution

• For N=3 and m=2, fair solutions form x=(z, 1 − z, 1 − z) for 0.5 ≤ z ≤ 0.7, with both resources bottlenecks.The trajectory is unique for the chosen function f, but other choices can lead to other trajectories and solutions.Source: §5.5 · p. 11
• In the symmetric four-user, four-resource instance, seven solutions exist: the symmetric allocation xi=1/3 and six alternatives with different bottleneck resources.In the six alternatives, two resources are bottlenecks, and which ones depends on the selected users.Source: §5.5 · p. 11
• Multiple fair solutions allow secondary objectives such as maximizing utilization to select among them, but characterizing all possible solutions remains open.In the four-user example, maximizing utilization favors the symmetric solution, where all resources are bottlenecks.Source: §5.5 · p. 11

6. CONCLUSIONS

• Each user either receives all requested resources or at least their entitlement on some bottleneck, and the paper proves such a fair allocation exists.The constructive proof provides a numerical method that was implemented in Matlab.Source: §6 · p. 12
• The numerical method seemed efficient in practice, but whether it can run in time polynomial in N and m remains open.Source: §6 · p. 12
• For online scheduling with multiple bottlenecks, prioritize each process by its smallest gap on any bottleneck and stop promoting it once it reaches its target on one.This differs from basing global priority on the resource where a user is farthest behind.Source: §6 · p. 12
• The proposal specifies policy-level considerations for fairness, not a mechanism for controlling resource allocation.It can in principle be used with mechanisms such as resource containers.Source: §6 · p. 12
• The model leaves nonlinear resource-use profiles and user-adjusted substitution between resources as directions for future work.The paper also raises incorporating resource-specific user factors and utilities.Source: §6 · p. 12