fractal reserve banks shapj@us.ibm.com
Thu, 15 Jul 1999 14:42:25 -0400

In the course of another conversation, Mark and I got to talking about durability, and about storage management. Durability requires that the allocator be unable to deallocate the object (in general). If I build the object and give it to you exclusively, only *you* should be able to delete the storage.

After some discussion, we concluded that allocated pages and nodes could be transferred from one bank to another without loss of correctness, and that this provides a possible means of implementation.

Mark then pointed out that you could transfer "futures" as well. That is, the right to allocate an unallocated page can be transferred from one bank to another (i.e. you can give away pieces of your quota).

The transfer rule for unallocated objects from bank A to bank B goes as follows:

There is some common ancestor bank P that is a "parent" (perhaps indirectly) of both A and B. That is, there is some set of banks

A(0) A(1) A(2) ... A(n) and B(0) B(1) B(2) ... B(m)

such that

```          A == A(0), B == B(0)
P == A(n), P == B(m)
P is the direct parent of A(n) and also the direct parent of B(m)
Forall i, A(i+1) is the direct parent of A(i).

```

A transfer of k units of quota is permissable when

```     forall 0 <= i < n
residual quota of A(i) >= k

```

The transfer is accomplished by performing the following actions as an atomic operation.

```     forall 0 <= i < n
reduce residual quota of A(i) by k
forall 0 <= i < m
increase residual quota of B(i) by k

```

This description is correct and sufficient, but it is a bit odd that it uses i < n and i < m rather than i <= n and i <= m. It is legal in the bakn hierarchy for a child's residual to exceed the parent's residual, so this is okay. Also, note that as a result of the transfer the residual of P is conserved, so there isn't any point to doing the decrement and increment on P.

Jonathan S. Shapiro, Ph. D.
IBM T.J. Watson Research Center
Email: shapj@us.ibm.com
Phone: +1 914 784 7085 (Tieline: 863)
Fax: +1 914 784 7595