Crate r_fairdist

Fair Resource Distribution Algorithm

This project provides an implementation of the fairdist algorithm, a way to distribute a set of resources fairly amongst a dynamic number of users. Its infrastructure manages a hierarchy of users that currently hold shares of a resource. New users can be added at any time, and charges can be requested and released dynamically. The system ensures that every new user joining the system gets a guaranteed share of the total, regardless of how many users already hold resources.

The API abstracts over resources through the [counter::Counter] trait. This trait represents a set of numeric resource counters. In most cases these will just be usize integers. However, that is not a requirement. The resource counter is only required to “look like an integer” (see [counter::Counter] and its dependencies on the num crate). Furthermore, the API abstracts over users. It does not track users who interact with the system, but relies on the API user to provide a key or index that identifies the user of a given operation. This way the resource allocators can tell whether separate operations are performed by the same accounting user, or whether they are different. This is all information the system needs about the different users.

At the root level, the API user has to create a [Resource] object with the resource counters initialized to reflect the total resources available for distribution. These resources can now be requested through [Charge] objects. Charges are RAII-type objects that record a resource charge and make sure resources are released again when the Charge is dropped. To request resources, the API user must specify the accounting user to perform the charge as, as well as the amount to charge. If the quotas of the accounting user were exceeded, the charge is rejected. Otherwise, the charge will be granted. The allocators behind the resource objects make sure resources are distributed fairly. Additionally to the root-level [Resource] objects, the API allows to create sub-hierarchies to redistribute resources further. That is, new non-root-level [Resource] objects can be created given the accounting user to act as. This new sub-resource will then behave similar to the top-level resource and allow charges to be performed. It will ensure the same guarantees on its own sub-level, so the sub-distribution is again fair. Furthermore, the top-level guarantees are unaffected by sub-hierarchies that are formed. That is, individual accounting users cannot increase their resource shares by creating sub-hierarchies.

There are multiple possible algorithm that can be used for the individual allocations. In most cases the selected default is sufficient. However, the [allocator::Allocator] trait allows selecting from a range of predefined allocators, as well as creating individual allocators. The default allocator guarantees quasilinear shares to every user of the system. In particular, this means regardless how many users join the allocation system, each one is guaranteed a share of 1 over O(n * log(n)^2) of the total.

Modules

• allocator
  Allocation Calculations
• counter
  Abstract representation of a multi-dimensional resource counter.

Structs

• Charge
  A charge represents temporarily borrowed resources.
• Resource
  A resource that can be distributed amongst users.
• Subscription
  A subscription to a resource.