An old email exchange on cap-talk about implementing
import/export. Follows below.


Ian Denhardt writes:

> Quoting Christine Lemmer Webber (2020-05-19 10:16:03)
>
>> That's actually almost entirely what I'm thinking, if I understand you
>> correctly.  The key thing there is pre-allocating promise-resolver pairs
>> *for* the intermediate anticipated results in the promise pipelining.
>>
>> Assuming I understand you, maybe that means we came to the same
>> conclusion, which makes me very optimistic.
>
> If you say that's what you meant I'll take your word for it ;)

Well, in retrospect it couldn't have been what I meant because I
realized yesterday while implementing that I didn't fully understand the
problem that questions/answers are solving (or your solution).  More below.


Mark S. Miller writes:

> On Wed, May 20, 2020 at 9:31 AM Christine Lemmer Webber <
> cwebber@dustycloud.org> wrote:
>
>> Mark S. Miller writes:
>>
>> > The questions/answers table is the bookkeeping to do this backwards-in-time
>> > passing of the promise from VatB to VatA. VatA on sending the message knows
>> > that VatB, on receiving it, will create a promise/resolver pair. What would
>> > happen if VatB would send the promise part to VatA? Whatever bookkeeping
>> > that is, just set it up ahead of time.
>> >
>> > Again, that's why we don't make any special case for passing a resolver as
>> > argument. The receiver just received a remote reference to the resolver,
>> > with no reason to believe that it holds it exclusively. It may be in a race
>> > to resolve the resolver. It is not the decider.
>>
>> Let's see if I understand what you're saying here by repeating it back
>> in my own words, and find out how wrong they are. :)
>>
>>   "In a first class promise-resolver pair, it is possible that multiple
>>   entities may have access to the resolver, and the first one "wins".
>>   But for promise pipelining, we need a stronger understanding: even
>>   though we *could* just point to an arbitrary resolver, when something
>>   is sent over in the questions/answers tables, it's an indication from
>>   the other side that the vat responsible for answering is the one and
>>   only decider.  If we instead just pointed at an arbitrary exported
>>   resolver, we aren't making as strong of a commitment... and promise
>>   pipelining really needs that kind of commitment to work."
>>
>> How far away is this from your thinking?
>>
>
> You got it in one ;)

Let me add a bit more what I realized yesterday.  I walked through the
example again of Bob on Vat B wanting CarFactory on Vat C to make a car
for Bob, and then immediately drive it.

  ;; from Bob on Vat B, to car-factory on Vat C
  (define car-for-bob-vow
    (<- car-factory 'make-car))
  ;; Now immediately pipeline a drive action to this car
  (<- car-for-bob-vow 'drive)

Still being a smug upstart, I thought I could figure out how to do this
with just import/export tables, no question/answer tables at all.
Smugly, I thought that what we could do is:

 - Vat A would allocate a promise/resolver pair for this.  However, Vat
   A, when transmitting these, would still put them in its export tables
   but when transmitting this reference on the wire, would mark it as
   a special union of resolver/promise that is "decideable" by Vat B.

 - Vat B can then correspondingly mark these in its imports table, also
   marked as a "decideable" union... so Vat B does know that Vat B is
   "the decider".

 - This is important because for promise pipelining to work; when Vat B
   resolves this "decideable" promise/resolver union, Vat B will have to
   cache the answer in order to complete the pipelined messages that
   depend on its resolution.  Ie, in the car factory scenario, the
   resolution of the "decideable" is the new car-for-bob.  Knowing that,
   we can tell the car-for-bob to 'drive without a round-trip back to A.

All this so far could have worked if we were only implementing promise
pipelining... without any kind of distributed garbage collection at all.

The problem crops up the following way:

 - If Vat B "loses local interest" in the "decideable"
   promise/resolution pair, it will also forget what it decided as an
   answer.

 - If Vat A then continues to send pipelined messages that hinge on that
   decision, there is a race condition between when Vat B may have
   forgotten what it decided... thus being unable to complete the
   pipelining without round tripping back to Vat A again to ask.  "Hey,
   I know I decided this... but I forgot what I said.  Do you remember?"
   Hardly a good situation to be in given the reduction of round trips
   that promise pipelining aims to provide!

So this solution wouldn't have worked.  I understand the distinction now
between the tables on:

  http://erights.org/elib/distrib/captp/dagc.html

 - imports/exports can have the importer lose local interest, because
   the importer doesn't really store any of its own data about the thing
   on the other end, so if it dropped it but then is told to re-allocate
   it, fine, no big deal.

 - questions/answers however are in a curious situation: they glue
   together all of a promise and resolution from the questioning vat
   with an answer that will be provided by the second vat.  So both
   sides must hold onto something, which sounds scarily like a cycle.
   However it isn't so bad because questions/answers are a *special kind
   of promise/resolver pair*... ones only ever introduced by CapTP.
   Even though both the questioning and answering side both hold data
   relevant to the question and answer, we know that the questioning
   side is the only one which will continue to use the answer for the
   sake of future pipelined messages.  Thus if the questioning side
   knows it has no more questions, it also knows it is safe to tell the
   recieving side that it can forget the answer.

So I get it now.  This makes a lot of sense.  I think the
questions/answers table is a great way to solve that.

... assuming I understand it now, that is ;)

 - Christine