[cap-talk] Capability accounting, lost object problem

[Jed at Webstart]

At 09:02 AM 6/22/2006, Karp, Alan H wrote:
>Jed wrote:
> >
> > 2.  Regarding "There is no garbage collection in Keykos ...".  That's
> > the same philosophy we took, really by necessity, in NLTSS.
> > The attitude was that, while objects could indeed become "lost"
> > (possibly no or at least no easily found instances of capabilities
> > to them), they were still accounted for.  Whoever was responsible
> > for the account would have an incentive to clean up and destroy
> > the unused but still allocated resources.  We had a mechanism
> > whereby the owner of an account could produce new capabilities
> > for objects being charged to the account.  Such capabilities could
> > be produced (reproduced one might say) and then destroyed if
> > that was their appropriate fate.
>
> > <an additional mechanism was available in NLTSS that isolated
> > accounts for lost objects and shut off the accounts, resulting in the
> > object being destroyed. - noted just for completeness here as this
> > additional (in fact primary) mechanism was noted in my original
> > message.>
>
>Client Utility and e-speak were able to do garbage collection.  That's
>because all requests were made by a local client with a c-list visible
>to the system.  Hence, we were able to identify unreachable resources
>and delete them.    Once the last transitive reference to a resource was
>removed from the c-lists, the resource was forever unreachable and could
>safely be garbage collected.  It was "transitive" because resources were
>discoverable, but we could determine which resources could not be
>discovered.
>
>We didn't solve the problem of distributed garbage collection.  A remote
>client could have forgotten a reference to a resource, but we couldn't
>garbage collect that resource as long as the local proxy held a
>reference.  That's where we used your approach.  The quota system gave
>the remote client an incentive to clean up its proxy's references.  We
>couldn't use your approach of letting the owner create a new capability
>for the resource because we had no concept of owner.

It's clear why our implementations differed in that for the NLTSS system
everything was "distributed", so we applied the distributed policy uniformly.

Perhaps mostly for historical interest, the DCCS mechanism
(http://www.webstart.com/jed/papers/DCCS/ )
took the opposite approach of doing distributed garbage collection
(an approach that I now consider unwise as noted below).

The way that was accomplished is that:

1.  It assumed that each local system (CCS in the DCCS
terminology) did garbage collection (for others who might
be confused by this term, this means that the CCS systems
kept track of references to objects and destroyed the object
if there were no references left - much the way Unix deals
with hard links to files and directories), and

2.  Each system that had remote (distributed) access to
an object was responsible for reporting when it no longer
had any references to it (using it's local garbage collection
mechanism), and

3.  The object distribution mechanism was responsible for
deleting it's own reference to any object if there were no
longer any remote references outstanding.

While in principle the above seems workable, in practice
I believe it's unworkable and would require an approach
much like NLTSS did in any case.  This is because references
can too easily be "lost" (misplaced?) without being literally
removed.  In that case garbage collection won't deal with
the "lost" object and something like accounting must deal with
it in any case.

--Jed http://www.webstart.com/jed/