OverAllocation

Over Allocation

This refers to a scheme of allocation which I have seen in the wild and in some software contexts. There is a hierarchy or tree of limits on the use of some fungible resource.

Abstractly a user must have a key which designates a meter. Each meter has a limit which is a variable non-negative real number. There is one special (primordial) meter with no limit and which needs no key. Each meter itself has a key to a ‘superior’ meter. To use the resource a meter key is necessary and sufficient. Any usage goes against the limit in the designated meter and recursively the superior meters. This chain must terminate in the primordial meter. Authority is distributed somehow to mechanisms that can read and write the individual meter limits. It is widely possible to create new meters given a meter key to serve to designate its superior meter.

Notably absent is the restriction that the limits in meters inferior to a meter X sum to less than the limit in X. Thus the title ‘OverAllocation’. Some resource allocation is like borrowing as when the Keykos space bank sells a page (for data) whence the limits go down. The page can be sold back to the bank whereupon the limits of the bank increases again.

Authority over the mechanisms that govern the limits is distributed to those with responsibility of limiting allocation. Keykos uses this pattern in two contexts:

The Space Bank which governs, or at least limits allocation of the most permanent storage in the system.
The Meter which give out access to the system’s CPUs and perhaps a few other critical resources.

Both of these follow the tree pattern and their respective service keys deliver the authority that completes the pattern described here.

The applications I have seen had until recently were put in place because the resource was dear. It allows mission critical applications to be assured of necessary resources. Two more reasons have recently popped up:

Remove an impediment to deterministic replay.
Limit bulk of exfiltrated data.

The latter is what inspired this note. The United States Office of Personnel Management recently lost the security clearance data of many millions of US Citizens. There were perhaps 10,000 individual with legitimate need to look at that data, but there were very few that needed to see the data for more than a few individuals each day. If such a hierarchical system of limits had been in place the bulk exfiltration as it was performed, would have been impossible. There are programs that need high bandwidth access to that data but access to those programs is not widely needed. Authority to install such programs may also be limited.