[E-Lang] Migration and Una (was: E FAQ)

[Mark S Miller]

Rees wrote:
>> >4.8. Is there a reason that object mobility isn't supported?

>MarkM wrote:
>> [...] it would seem that secure mobile objects are impossible.

At 11:10 AM Friday 9/28/01, Ken Kahn wrote:
>I'll agree about the general case, but aren't there many cases where one
>would want object mobility to trusted hosts? [...]

Sure.  And it would be perfectly sensible for such a thing to be provided.

Btw, in light of previous discussions on e-lang, we may want to rephrase 
this as "mutually reliant UTCBs".


>The broader question is what should a language support. I would argue it
>should support those things that a large enough fraction of the users need,
>when providing such support provides greater benefits than if the
>functionality were provided by user code. Unless adding such functionality
>costs too much in terms of complexity or implementation costs.

I'd say that's exactly the right question.  Since mobility among mutually 
reliant UTCBs can't provide a security benefit (mutually reliant UTCBs 
jointly form a single UTCB anyway), I assume the only benefits we're seeking 
are performance and management of our vulnerabilities to partition.  I 
believe user code can obtain these benefits by using the planned support for 
PassByContruction (for replication and smart references), delegation (to 
switch which replica is taken to be authoritative) and GC (to get rid of old 
replicas when it's safe to do so).

Let's say A1 is designed to be a pseudo-migratable object.  If A1 is 
immutable, then everything's easy: It should be PassByContruction (pbc), and 
it should just make a replica of itself in every vat that references it. 
/*Note: Selfless pcbs are Immutable, Transparent, and PassByCopy.  See 
http://www.erights.org/elib/equality/same-object.html */. All resolved 
references to a pbc object are near references, so there would be no 
resolved remote references to any replica for a partition to break. 
(Unresolved remote promises that designate a pbc object should promptly 
resolve,  but until then are breakable.  This corresponds to an unavoidable 
issue under any scheme.)  When there are no longer any references to a local 
replica, then it gets GC'ed, and "migration" has been accomplished.


                                       Una


If A1 is mutable, then we can first arrange for eventually consistent 
(Lamport-style) replication using Chip Morningstar's Unum pattern.  This 
doesn't yet give us "migration", but please bear with me.  Each replica of 
an Unum is a "presence" of the Unum, and all the presences jointly are taken 
to form the Unum.  One of the presences is the "authoritative presence" -- 
its state is considered to be the "true" state of the Unum.  A1, being the 
initial presence, therefore starts out as the authoritative presence.

The other presences are effectively smart remote references to the 
authoritative presence.  These "shadow presences" maintain a somewhat stale 
cache of a copy of some state from the authoritative presence -- but only 
state that can be useful even when it's stale.  These shadow presences do 
support immediate calls for those operations that can be sensible performed 
using this stale data -- giving us another huge victory over network 
latency.  But operations needing accurate state must still be eventual, and 
must be delegated to the authoritative presence.

The shadow presences also register themselves as observers (in E, 
"reactors") on the authoritative presence.  Every time the authoritative 
presence changes replicated state, it notifies all its reactors, so that 
they may update their cached copies.  In the absence of partition, we can 
say that these caches are always "eventually consistent" -- they are always 
consistent with some past state, they only move forward in time, and under 
quiescence they will always eventually become accurate.  (Does this capture 
Lamport-like eventual consistency?)

During a partition, the presence can still give correct, even if 
increasingly stale, service for the staleness tolerant operations.  Of 
course, it must refuse the accurate operations.  Should the authoritative 
presence again become reachable, the shadow should "heal".  (Note: at EC we 
didn't do this.  Instead, we always invalidated shadow presences on 
partition.  So although both choices seem valuable, we don't yet have any 
experience with shadows that survive partition.)


What happens when a shadow presence A2 is passed?  Two simple possibilities are

1) a new shadow presence A3 is created that takes the authoritative presence 
    A1 as authoritative.  A2 and A3 would both be registered as reactors on A1.

2) a new shadow presence A3 is created that takes shadow presence A2 as 
    authoritative.  A2 is a reactor on A1, and A3 is a reactor on A2.

#1 is Granovetter introduction, and supports grant matching.  #2 is 
proxying, and does not.

Answer #1 gives us a flat multicast fanout for state updates.  Answer #2 
turns the presences into a spontaneously malformed multicast tree.  (I say 
"malformed" because the topology of the tree is based only on acts of 
introduction, and not on any sensible performance issues.)  NetNews, DNS, 
and Notes are all massively scalable systems that use Lamport-like eventual 
consistency to distribute state updates.

    "When someone says they want to buy a shovel, remember that they probably 
     really want a hole in the ground."
                                              --Klaus Landberg

Even though we have not yet addresses "migration", since the authoritative 
presence hasn't moved, I speculate that this kind of massive state 
replication, and the ability of local replicas to service local requests 
synchronously, in fact provides most of the benefits that were actually 
being sought by those who thought they wanted replication.  And so far, we 
haven't had to compromise capability security in the slightest -- given that 
the state being replicated include only state available via A1'a normal 
client interface.  (In MarcS' terminology (need link) this is "front-end 
state" rather than "encapsulated state".)  

Besides non-migration, we've made one other sacrifice above in order to in a 
simple security model: sticking to topology choices #1 and #2.  I don't know 
how to reconcile adaptive multicast topologies with capability security, 
except by resorting to another layer of crypto (treating messages as 
off-line certs), which would take us well beyond the security implicitly 
provided by E itself.


                                  Question Authority


Starting from the Unum pattern, migration is conceptually simple.  (For this 
discussion, let's assume the flat multicast fanout topology #1.)  Let's say 
the current authoritative presence A1 decides that A2 should become the 
authoritative presence.  It informs all its reactors (A2 and A3) of its 
decision.  A3 reacts to the decision by taking A2 to be authoritative, 
unregistering on A1, and registering on A2.  A2 also unregisters on A1, but 
doesn't bother to register on itself.  A2 now considers itself 
authoritative.  A1 then changes itself to consider A2 authoritative, and 
registers on A2.  

(Important: This points out another sense in which shadow presences are 
smart references: they can engage in behavior to determine who/what they 
take as authoritative.  As another example, the shadow presences of a 
Quorum-Unum would only take as authoritative answers that n out of m 
authoritative presences agreed on.  All such things should be programmable 
in regular unprivileged E code.)

Any messages A1 receives that require accurate answers (which could have 
been in transit from, eg, A3) it now forwards to A2.  Any notification 
messages it receives from A2 is forwards to any reactors that still may be 
registered.  We always settle into a #1 topology, but we allow #2 topologies 
during the transition to avoid distributed locking.

Once the above migration process settles down, the only remote references 
remaining to A1 are the same as for A3 -- the entry in A2's reactors list.  
Unfortunately, this points to a remaining feature we need to make Una work 
-- remote weak references.  If A1 is no longer needed locally, this entry on 
A2's reactor list should not prevent it from being collected.  I wouldn't be 
surprised if this was the hardest part of the story to implement.

So, to answer your question, I see nothing to be gained by directly 
supporting object migration inside E itself.  Rather, Una, migration, 
quorums, etc, are all goods tests of the generality of the primitives 
provided by E: Can these all be written in E?



             Birds, Boxes, Robots, Trucks, and Nests.  Oh my!


>P.S. Object mobility is simple in ToonTalk. An object migrates by giving a
>bird a box with a copy of its robots and its box. The bird flies off to a
>possibly remote host where a robot puts the incoming robots and box in a
>truck and the object is now running on the host where the bird's nest is.

I'm afraid I'm not yet good enough at translating between these worlds.  
Could you rephrase in more conventional language terminology?  (Sorry)





        Cheers,
        --MarkM