[E-Lang] New Page: Partially Ordered Message Delivery

Tyler Close tclose@oilspace.com
Tue, 27 Feb 2001 14:39:48 -0000


This is a multi-part message in MIME format.

------=_NextPart_000_0004_01C0A0CB.225D02A0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit

Markm wrote:
> 2) Your transform of this scenario, in which Alice
> eventually sends (<-)
> this reference to Bob in message Y after she has eventually
> sent X to Carol.
> The semantics guarantee that Bob will not be able to use
> this reference to
> deliver W before X.  Since a NEAR reference would give Bob
> the ability to
> deliver W immediately (via a call), the semantics require
> that the reference
> delivered to Bob not be NEAR until after X has been delivered.

This is actually the case that I am thinking about. The confusion is
about what "the semantics require". Take this adaptation of your code.

     define alice {
         to doSomething() {
             myCarol <- X
             myBob <- Y(myCarol)
         }
     }

Assume Alice, Bob and Carol are all in the same Vat.

After sending Y to Bob, Alice is free to do a synchronous invocation
with myCarol. I assume that as soon as Bob gets his copy of myCarol,
Bob will also be able to do a synchronous invocation with myCarol. Bob
should get exactly what Alice sent him. Alice could do a synchronous
invocation, so Bob can too. The delivery of X to Carol is not an
element of this timeline.

I am guessing that when you say "the semantics require", you are
saying that the semantics require that Bob gets a reference that is
not able to do an eventual invocation that arrives before the last
eventual invocation by Alice. You are then using this condition to
justify the creation of a temporarily non-NEAR reference. It is this
last step that does not seem clear to me. Alice sent a NEAR reference.
Why does Bob (in the same Vat) get a non-NEAR reference? Just looking
at the code, I see nothing that implies this transformation. The raw
code suggests to me that Bob gets the powers Alice gave to him, which
included the ability to do a synchronous invocation. Bob is granted
access to pre-X Carol.

> >> When we tried to build it without
> >> these ordering
> >> guarantees, we had a hell of a time.
> >>
> >> The ordering guarantees originated in syntactic sugar used
> >> in the Joule user
> >> language (though I don't think they are in the on-line
> >> manual).  When we
> >> added these guarantees to Original-E and used them,
> >> suddenly a whole mess of
> >> n-party (for n >= 3) concurrency problems went away.
> >
> >Are these problems adequately solved by the multi-promise resolve
> >sugar you recently introduced?
>
> No.  They solve a different issue -- waiting for multiple
> separate things to
> be resolved before taking some action.

Could you give me an example of the type of problem you are thinking
about?

> >[...] In Droplets, the
> >Carol reference is just another sturdy reference that lives for as
> >long as the Bob Vat is willing to let it live. This makes surviving
> >temporary partitions a lot easier.
> >
> >In E, the advent of partition means that you have to tear down the
> >entire structure of "live" references that you've built up
> and rebuild
> >it from scratch when the partition is fixed. In Droplets,
> you may get
> >a few smashed return values; however, you might be able to
> carry on as
> >you were when the partition is fixed. Your pointers may
> still be good.
> >E pointers that suffered a smashed return value are permanently
> >broken.
>
> In some sense, the whole point of the E mechanism is to
> "tear down the
> entire structure of 'live' references that you've built up"
> and make the
> programmer "rebuild it from scratch when the partition is
> fixed."  Rather
> than have all references be somewhat flaky all the time,
> and make the
> programmer have to deal with this flakiness everywhere,

So, if we are working in a network environment where the references
are behaving as if they were "somewhat flaky", then we are working in
a network environment in which an E program would be continually
building up and tearing down its entire program structure.

I terms of "dealing with flakiness", I think the E strategy is more
difficult. Every part of an E program must know how to recapture its
state from the sturdy references. This means that the logic of every
part of the program is coupled with the "rebuild" logic.

In a Droplets program, individual parts of the program can assume that
they will recover from temporary partitions and assume that if they
cannot recover, something truly catastrophic has happened and they are
unable to recover.

I want to show an example of this, but I first have to explain one
other feature of a Droplets reference.

Consider:

	def r := foo <- bar()

The programmer can assume that if "bar()" gets to "foo", "r" will
eventually resolve to the return value of "bar()". If "r" is smashed,
the programmer can assume that one of the following is true:

1) "bar()" was never delivered to "foo", so there is no return value.
2) "bar()" was delivered and it produced an exception.
3) "foo" is also smashed.

When writing code, this means that the programmer does not need to
think about how to recover from partition. If "r" is smashed, then the
situation is not recoverable. If "r" is not smashed, then you carry on
without ever noticing the partition.

At the implementation level, the Cistern implements this by sending
the "yourself" message on the return value promises that it was
waiting on when the partition occured. These return values are then
substituted for those of the actual method invocations.

Now let's do an example. I suggest a Bank. The Bank hosts a brand of
erights that is redeemable upon demand for a brand of erights hosted
on a remote machine. I'll use my version of the ERTP and a
Droplets-like E notation. I've attached the version of Commodity that
this code uses.

# Constructs a new Bank.
# @param    base        The contract for the base erights.
# @param    escrow      The Conduit for the base erights.
# @param    reserve     The reserve Purse for the base erights.
# @return   The [ Bank, Bank PurseFactory, Bank Conduit ]
def Bank(base, escrow, reserve) {
    def Self;
    def [ mint, factory, pay ] := Commodity(Self)
    def Self {

        # Gets the contract associated with the base erights.
        to getBaseContract() :any { base }

        # Purchase local currency.
        # @param    amount      The amount of the base currency to
transfer.
        # @param    src         The remote Purse containing the
purchase erights.
        # @param    dst         The local destination Purse for the
purchased erights.
        # @return   The amount of currency received from the src
Purse.
        to deposit(amount, src, dst) :any {
            def deposited_p := escrow <- transfer(1, amount, src,
reserve)
            when (deposited_p) -> done(deposited) {
                pay transfer(1, Assay(mint getContract(), deposited
getValue()), mint, dst)
            }
            deposited_p
        }

        # Redeems local currency for base currency.
        # @param    amount      The amount of the local currency to
redeem.
        # @param    src         The local Purse containing the erights
to redeem.
        # @param    dst         The destination Purse for the redeemed
erights.
        # @return   The amount of currency added to the dst Purse.
        to withdraw(amount, src, dst) :any {
            def withdrawn := pay transfer(1, amount, src, mint)
            def redeemed_p := escrow <- transfer(1, Assay(base,
withdrawn getValue()), reserve, dst)
            when (redeemed_p) -> done(redeemed) {
            } catch problem {
                pay transfer(1, withdrawn, mint, src)
            }
            redeemed_p
        }
    }
    [ Self, factory, pay ]
}

I contend that this simple program correctly handles all error
conditions. Moreover, if the "base" currency is in the same Cistern
(Vat) as the Bank, then the code does not impose unneeded overhead
(ie: creation of temporary Purses). I challenge you to write the same
in E. You can use your or my ERTP.

> This reproduces the valuable part of distributed atomic
> transactions --
> abort (throwing away questionable state) and recovery
> (rebuilding from
> relatively stable things) -- while not taking on any
> impossible problems.

The question is how precisely you can limit what the "questionable
state" is. I think E often throws the baby out with the bathwater. A
lot of the destroyed state was still good. A lot of the questionable
stuff can be automatically validated.

> >The Internet being what it is, I think the ability to easily handle
> >temporary partitions is an important feature.
>
> I agree that handling partitions is important.  That's the
> point!  I claim
> that the effort needed to correctly maintain consistency
> despite partitions
> is lower with the E pattern than with the Droplets pattern.

;) Well, lets see your Bank first.

>  With less than
> this effort, the path of least resistance using the E
> pattern leads to an
> application that safely disconnects.  But using the
> Droplets pattern, the
> corresponding path of least resistance leads to an application that
> innocently continues in a confused state.

You haven't made an argument for confusion, just asserted it. I don't
understand how the confusion could arise.

I contend that the E pattern is too difficult to use. You can easily
get yourself into a situation where it is impossible to fully recover
from a temporary partition. Analyzing a program for such conditions is
difficult work that is beyond the abilities of your target audience.
Moreover, the E pattern requires that the host service's API be
constructed a priori to anticipate all the possible conditions and
provide "sturdyVouch"-like services to enable recovery. Failure to
anticipate a possible use of your service means that all clients will
be vulnerable to untimely partitions that are unrecoverable.

Tyler

------=_NextPart_000_0004_01C0A0CB.225D02A0
Content-Type: text/x-escript;
	name="Commodity.e"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="Commodity.e"

def Assay(contract, value) : any {
    def Self {
        to openState :any { meta scope }
        to openSource :any { meta sourceTree(self) }
        to printOn(out) { out print("<Assay: " + value + " " + contract =
+ ">") }
        to compareTo(other) :any { value compareTo(other getValue) }
        to isEmpty :boolean { value =3D=3D 0 }
        to getContract() :any { contract }
        to getValue() :any { value }
    }
}

def Commodity(contract) :any {
    def [ sealer, unsealer ] :=3D BrandMaker pair(contract)
    def Purse(mint :boolean) {
        var balance :int :=3D 0
        var observers :=3D [  ] toFIFO
        def Private {
            to getValue() :int { balance }
            to withdraw(amount :(int >=3D 0)) :void {=20
                if(balance < amount && !mint) {
                    throw(InsufficientErights("" + amount + " > " + =
balance))
                }
                balance -=3D amount=20
                for x in observers {
                    x <- withdrawn(Assay(contract, amount))
                }
            }=20
            to deposit(amount :(int >=3D 0)) :void {=20
                balance +=3D amount=20
                for x in observers {
                    x <- deposited(Assay(contract, amount))
                }
            }
        }
        def Self{
            to getBalance() :any { Assay(contract, balance) }
            to getContract() :any { contract }
            to observe(observer) :void { observers +=3D observer }
            to pack() :any { sealer seal(Private) }
        }
    }
    def PurseFactory {
        to getContract() :any { contract }
        to makePurse() :any { Purse(false) }
    }
    def Conduit {
        to getContract() :any { contract }
        to makeEmptyAssay() :any { Assay(contract, 0) }
        to deliver(src, dst) :any {
            def src_balance :=3D unsealer unseal(src pack)
            def dst_balance :=3D unsealer unseal(dst pack)
            def delta :=3D src_balance getValue
            src_balance withdraw(delta)
            dst_balance deposit(delta)
            Assay(contract, delta)
        }
        to transfer(n :(int >=3D 0), amount, src, dst) :any {
            assert(contract =3D=3D amount getContract) # Just for =
debugging.
            def src_balance :=3D unsealer unseal(src pack)
            def dst_balance :=3D unsealer unseal(dst pack)
            def delta :=3D n * amount getValue
            src_balance withdraw(delta)
            dst_balance deposit(delta)
            Assay(contract, delta)
        }
    }
    [ Purse(true), PurseFactory, Conduit ]
}

------=_NextPart_000_0004_01C0A0CB.225D02A0--