This is a specific hack that was proposed but not implemented for Keykos. It may have nothing to do with capabilities but it works at least in that context.

The connection to the real line is that it has to do with a substance that is indefinitely sub-divisible—like the real line. Actually the proposed Keykos version is bisectable only 88 times but we take 88 to be an approximation of infinity here, and the subdivision is limited to bisection in particular. I will call it the line key here; no name has been proposed before. There is a new key type with internal format like the number key which has 88 constant bits of internal data. Each 88 bit value is taken to represent a node of the binary tree of 288−1 nodes. Unlike the number key there is no order to reveal those bits. There is an order on a line key that takes another line key and if the passed key is inferior to the invoked key then the difference of the two keys are returned as a number (of up to 87 bits). Otherwise the line would respond “no”. Another order on a line key reveals its height in the tree. Yet another order yields a dependent key, given an offset value. Think of line keys as deeds to portions of the real line.

In Tree Speak

To bootstrap, a key for the root of the maximum tree is initially provided to a branch allocator who holds the key closely. The height call on a line key X merely returns the number time X may be bisected. The query call sends line key X to line key Y. If X is a sub-tree of Y then Y returns the path from the root of Y to the root of X as a string of bits, each representing a left-right choice. The sub-tree generation call passes such a string of bits to line key X and if X is high enough (height of X > length of string), it returns a key to the sub-tree navigated to by the sequence of choices given by the string of bits.

Note that a holder of a line key X can determine its height but not the path to the root of the maximal tree. Only the maximal line key will reveal that and that key is held by someone than probably has a policy to not reveal such information.

Utility of Line Key

All sorts of things can be owned by the holding of a line key. To own something by virtue of holding such a key requires that the server for some particular sort of thing hold some line key for the tree of items of that sort. Before such a server begins service it acquires a line key T of sufficient height that the sub-keys are sufficiently numerous to serve as ownership tokens to be held by the clients of the server. If the server stores data outside the computer system than the server might take a data file and give back a line key which may subsequently be shown to the server which is thereby obliged to return the contents of the corresponding file. The server acquires T from someone trusted to insure that no sub-keys of T have ever been disseminated before. Keys of greater height are thus dearer than those of lesser height.

A possible application.


The line key has a curious status regarding rescinding. There is ostensibly no way to rescind a line key. With a manipulation of abstraction levels, however, we see that line keys are as rescindable as page keys. (?? Needs analysis!) The Keykos page key is generated by the page range key .... Range keys are non-rescindable, but closely held. A page key is a temporary key to most of a disk page frame and the rest of the disk page frame is the allocation count which is compared with a similar field in the page key. If the fields differ then the page key has been rescinded. This sort of semantics can be instituted outside the kernel.