Capbility Concepts

[Mark S. Miller]

At 07:39 PM 7/16/00 , Jonathan S. Shapiro wrote:
>Deep copy with identity preservation (i.e. there is a one to one
>correspondance between objects in the original and objects in the copy in
>spite of multiple references) requires a widely available "keybits"
>equivalent in order to perform the necessary identity tests.
>
>My point here is that in addition to having a partitioned mechanism, we also
>wish to consider whether the mechanism provides efficient state sharing
>across a confinement boundary.

Yes, but a keybits-equivalent that's equivalent enough for the above 
purposes still need not reveal the bits in the keys, and can therefore be 
used safely by those that must not have such access -- such as computation 
constrained to be deterministically replayable.  E primitively provides an 
equality testing operation (the moral equivalent of the equality-testing 
aspect of DISCRIM), and a primitive hash table.

The hash table uses but does not reveal the bits of the keys.  Its internal 
representation is therefore non-deterministic on overt properties of the 
computation (depending on the bits of a key, which we define as a covert 
property).  However, it provides deterministic service to its clients, 
thereby not providing its clients a way to escape deterministic replay.  We 
pay a price for this: in order to be deterministic, the table's enumeration 
order depends on order of entry and removal, not hash order.

These two primitives are sufficiently keybits-like for the above purposes, 
but the services they provide avoid Norm's criticisms.


         Cheers,
         --MarkM