Split Capabilities: Making Capabilities Scale

Mark S. Miller markm@caplet.com
Thu, 20 Jul 2000 16:02:57 -0700

At 03:38 PM 7/14/00 , Jonathan S. Shapiro wrote:
>... In E, the issue is limited to SturdyRefs (if I understand matters). I
>don't know if markm has plans for distributed GC or not.

We actually *have* distributed GC (DGC).  Doesn't mean we don't have plans 
though. ;)

In E, conventional distributed GC is limited to live refs, since these are 
good only as long as the vats they span remain in communication.  Therefore, 
a DGC algorithm may have reliable knowledge about whether there remain any 
live refs that designate a particular object.

SturdyRefs exist for the purpose of surviving vat communications failure 
(whether due to network partition or vat shutdown-or-crash).  Therefore, DGC 
calculations involving SturdyRefs must assume they exist remotely when they 
can't prove otherwise.  This uncertainty led to SturdyRefs incorporating 
expiration times.  

The "sturdyRef" function in the initial (big bang) environment is the 
authority to create a SturdyRef for the objects hosted by this vat.  The 
optional second argument is the expiration time.  If left out, it defaults 
to infinity.  It's a capability, because making a SturdyRef imposes a 
storage obligation on the local vat that may last until this time expires.  
"Infinite" time is less silly than it seems -- it really mean "for the rest 
of the life of this (the hosting) vat".  Once possible outstanding 
SturdyRefs expire, the disposition of the object is again in the hand of 
normal GC and DGC mechanisms.

Jonathan has a clever scheme for often not waiting for these times to expire.  It's worse-case performance would be the same, but it's typical case may be vastly better.  Jonathan, care to explain?

Btw, E's DGC algorithm is acyclic.  It doesn't collect unreferenced loops 
that cross trust boundaries.  In the past E had efficient full DGC using the
Bejar algorithm, but only at the cost of modifying the JVM to get needed 
information from the local intra-vat garbage collector.

> > Set all the policies you want, but if you can't enforce them, what's the
> > point?
>Precisely the statement I made at IBM. Unfortunately, I attached this
>statement to a recounting of the Harrison, Ruzzo, Ullman results about
>access control lists (which provably don't constraint access right

I tried taking a look, but it exceeded my boggle threshold.  Could you 
summarize their results in english?  In particular, is it something we can 
cite on the impossibility of preventing delegation in the Communicating 
Conspirators scenario?