From markm@eros.cs.jhu.edu Wed May 9 00:15:31 2001 Received: from mail.eros-os.org (IDENT:root@EROS.CIS.UPENN.EDU [158.130.6.119]) by eros.cs.jhu.edu (8.11.0/8.11.0) with ESMTP id f494FVK26630 for ; Wed, 9 May 2001 00:15:31 -0400 Received: from eros.cs.jhu.edu (IDENT:root@eros.cs.jhu.edu [128.220.223.245]) by mail.eros-os.org (8.9.3/8.9.3) with ESMTP id AAA00778 for ; Wed, 9 May 2001 00:05:43 -0400 From: markm@eros.cs.jhu.edu Received: (from markm@localhost) by eros.cs.jhu.edu (8.11.0/8.11.0) id f494FR926625 for e-cvs@eros-os.org; Wed, 9 May 2001 00:15:27 -0400 Date: Wed, 9 May 2001 00:15:27 -0400 Message-Id: <200105090415.f494FR926625@eros.cs.jhu.edu> To: e-cvs@eros-os.org Subject: [E-cvs] cvs commit: e/doc/elang/kernel index.html Sender: e-cvs-admin@mail.eros-os.org Errors-To: e-cvs-admin@mail.eros-os.org X-BeenThere: e-cvs@mail.eros-os.org X-Mailman-Version: 2.0beta5 Precedence: bulk List-Id: markm 01/05/09 00:15:27 Modified: doc/elang/kernel index.html Log: Added start production to BNF. Thanks to Sergey Ivanov Revision Changes Path 1.44 +6 -0 e/doc/elang/kernel/index.html Index: index.html =================================================================== RCS file: /cvs/e/doc/elang/kernel/index.html,v retrieving revision 1.43 retrieving revision 1.44 diff -u -r1.43 -r1.44 --- index.html 2001/04/15 20:01:16 1.43 +++ index.html 2001/05/09 04:15:26 1.44 @@ -102,6 +102,12 @@ to non-terminals, and to Minimal-XML elements containing other elements.

+ + + + From markm@eros.cs.jhu.edu Wed May 9 03:14:18 2001 Received: from mail.eros-os.org (IDENT:root@EROS.CIS.UPENN.EDU [158.130.6.119]) by eros.cs.jhu.edu (8.11.0/8.11.0) with ESMTP id f497EIK28650 for ; Wed, 9 May 2001 03:14:18 -0400 Received: from eros.cs.jhu.edu (IDENT:root@eros.cs.jhu.edu [128.220.223.245]) by mail.eros-os.org (8.9.3/8.9.3) with ESMTP id DAA00873 for ; Wed, 9 May 2001 03:04:29 -0400 From: markm@eros.cs.jhu.edu Received: (from markm@localhost) by eros.cs.jhu.edu (8.11.0/8.11.0) id f497EI528645 for e-cvs@eros-os.org; Wed, 9 May 2001 03:14:18 -0400 Date: Wed, 9 May 2001 03:14:18 -0400 Message-Id: <200105090714.f497EI528645@eros.cs.jhu.edu> To: e-cvs@eros-os.org Subject: [E-cvs] cvs commit: e/doc/elib/distrib pipeline.html Sender: e-cvs-admin@mail.eros-os.org Errors-To: e-cvs-admin@mail.eros-os.org X-BeenThere: e-cvs@mail.eros-os.org X-Mailman-Version: 2.0beta5 Precedence: bulk List-Id: markm 01/05/09 03:14:18 Modified: doc/elib/capability/ode ode-bearer.html ode-objects.html doc/elib/concurrency semi-transparent.html doc/elib/distrib pipeline.html Log: more typos. Thanks to Darius Bacon Revision Changes Path 1.38 +210 -210 e/doc/elib/capability/ode/ode-bearer.html Index: ode-bearer.html =================================================================== RCS file: /cvs/e/doc/elib/capability/ode/ode-bearer.html,v retrieving revision 1.37 retrieving revision 1.38 diff -u -r1.37 -r1.38 --- ode-bearer.html 2001/04/08 18:41:18 1.37 +++ ode-bearer.html 2001/05/09 07:14:17 1.38 @@ -47,201 +47,201 @@

eExpr: any of the following
Kernel-E-Program:	+ seqExpr +

- +

From Stuff to Financial Instruments and Smart Contracts

Real world markets started out with direct trade of physical objects. - To oversimplify greatly, ownership usually went along with possession - and use, and, because of the locality of matter, all three together were - exclusive. The user interface was intuitive -- you knew what rights you - had because you could see your stuff. For Alice to transfer ownership - of a cow to Bob, Alice and Bob would move the cow's physical location - from Alice's territory to Bob's. Both would then effortlessly have common - knowledge that the transfer had occurred, and who had which cows. Absent - theft, possession would be an adequate record of ownership. Cows were - bearer instruments. (There is some evidence that the first money was - coins redeemable for cows [Selgin88].) - Over time, of course, more abstract rights were invented, as were more - complex arrangements for their transfer, usually with ghastly user interfaces +

Real world markets started out with direct trade of physical objects. + To oversimplify greatly, ownership usually went along with possession + and use, and, because of the locality of matter, all three together were + exclusive. The user interface was intuitive -- you knew what rights you + had because you could see your stuff. For Alice to transfer ownership + of a cow to Bob, Alice and Bob would move the cow's physical location + from Alice's territory to Bob's. Both would then effortlessly have common + knowledge that the transfer had occurred, and who had which cows. Absent + theft, possession would be an adequate record of ownership. Cows were + bearer instruments. (There is some evidence that the first money was + coins redeemable for cows [Selgin88].) + Over time, of course, more abstract rights were invented, as were more + complex arrangements for their transfer, usually with ghastly user interfaces and more room for misunderstandings and disputes.

A major aspect of the emergence of capitalism from feudalism was the - rise of contract. By creating a contract, you could define and transfer - an arbitrary bundle of rights. The complexity of trade could now bloom, - unrestrained by the simple limits of physical matter. During the twentieth - century, a great variety of financial instruments were invented. These - instruments represent the discovery of many new kinds of rights, and ways - of deriving these rights from more primitive rights. We should hope the - growth of financial cryptography will only accelerate this trend. For - this hope to be realized, we should seek not just the secure computational - expression of the contracts representing existing instruments, but the - creation of secure material from which similar new contracts can easily - be built. Following Nick Szabo [Szabo97], - we refer to a partially self-enforcing computational embodiment of a contract +

A major aspect of the emergence of capitalism from feudalism was the + rise of contract. By creating a contract, you could define and transfer + an arbitrary bundle of rights. The complexity of trade could now bloom, + unrestrained by the simple limits of physical matter. During the twentieth + century, a great variety of financial instruments were invented. These + instruments represent the discovery of many new kinds of rights, and ways + of deriving these rights from more primitive rights. We should hope the + growth of financial cryptography will only accelerate this trend. For + this hope to be realized, we should seek not just the secure computational + expression of the contracts representing existing instruments, but the + creation of secure material from which similar new contracts can easily + be built. Following Nick Szabo [Szabo97], + we refer to a partially self-enforcing computational embodiment of a contract as a smart contract.

To understand the job ahead of us, we start by classifying the characteristics +

To understand the job ahead of us, we start by classifying the characteristics of rights.

A Taxonomy of Kinds of Rights

By contrasting some of the rights and rights-transfer mechanisms we have - already seen -- capability-passing vs. SPKI certificates vs. - our example money -- we can start to develop a taxonomy of rights. (Economics - elaborates this taxonomy much more fully, but we will only present the +

By contrasting some of the rights and rights-transfer mechanisms we have + already seen -- capability-passing vs. SPKI certificates vs. + our example money -- we can start to develop a taxonomy of rights. (Economics + elaborates this taxonomy much more fully, but we will only present the subset relevant to this paper.)

- + - - + - + - - - - + - + - - - - + - + - - - - - + - + - - - - +
Capabilities SPKI Example Purse-Money
+

shareable vs. exclusive Alice shares with Bob her right to access Carol. Issuer shares with Subject the authorization + Issuer shares with Subject the authorization to the Resource. When Bob deposits the payment from Alice, he knows + When Bob deposits the payment from Alice, he knows he has excluded anyone else from using that money.
-
In the capability case, if Alice drops the capability after passing - it to Bob, Bob happens to have exclusive access to Carol, but this - isn't an exclusive right since Bob is unable to know that he is +
+
In the capability case, if Alice drops the capability after passing + it to Bob, Bob happens to have exclusive access to Carol, but this + isn't an exclusive right since Bob is unable to know that he is the only one who has it.
- In the real world, information is sharable and physical objects are - exclusive. + In the real world, information is sharable and physical objects are + exclusive.

specific vs. fungible A capability designates a specific object. Authorization can be for specific objects, or for some + Authorization can be for specific objects, or for some number of units. Money is fungible, since we care only about + Money is fungible, since we care only about quantity, not individual bills.
In the real world, real estate is specific and barrels - of (a given grade of) oil are fungible. Peaches in the supermarket - are specific -- you buy the ones you pick out. Peaches ordered over - Peapod are fungible -- you order only by quantity. +
In the real world, real estate is specific and barrels + of (a given grade of) oil are fungible. Peaches in the supermarket + are specific -- you buy the ones you pick out. Peaches ordered over + Peapod are fungible -- you order only by quantity.

opaque vs. assayable A capability is opaque, since from the capability - alone all you can determine is what the designated object alleges + A capability is opaque, since from the capability + alone all you can determine is what the designated object alleges about itself. An authorization can be read as well as used. Reading + An authorization can be read as well as used. Reading it may suffice to assay what value it would provide. Bob can reliably assay the amount in an alleged + Bob can reliably assay the amount in an alleged purse only by transferring into a purse he trusts.
Assayability is needed for trade, since you must be - able to determine what you would be getting before deciding - to purchase. However, exclusive rights can only be reliably assayed - by actually obtaining exclusive access to them, since otherwise, after - you've assayed them, someone else may gain the exclusive, cutting - you out. Trade of exclusives may therefor require a trusted third - party who can hold them in escrow. +
Assayability is needed for trade, since you must be + able to determine what you would be getting before deciding + to purchase. However, exclusive rights can only be reliably assayed + by actually obtaining exclusive access to them, since otherwise, after + you've assayed them, someone else may gain the exclusive, cutting + you out. Trade of exclusives may therefor require a trusted third + party who can hold them in escrow.

exercisable vs. symbolic A capability has value only because it can be exercised, + A capability has value only because it can be exercised, by sending a message to the object it designates. An authorization may be for either or both. As with fiat money, our example money is purely symbolic, + As with fiat money, our example money is purely symbolic, since one can't do anything with it other than transfer it further.
There are many goods that are both exercisable and have - symbolic value. For example, gold is commonly used as a pure symbol - of value, but gold is also used to create electronic hardware and - decorative jewelry. +
There are many goods that are both exercisable and have + symbolic value. For example, gold is commonly used as a pure symbol + of value, but gold is also used to create electronic hardware and + decorative jewelry.

-
It is curious that our example money is so different from capabilities, - when the money is trivially built out of capabilities. More puzzling is - the transfer. Alice passed to Bob only a capability, which therefor had - all the rights-transfer properties of our first column. However, by doing - so, she also paid him money, which has all the properties of the last - column. Unsurprisingly, to resolve this we have to think in terms of two - levels of abstraction. We must understand how these levels relate to each +
It is curious that our example money is so different from capabilities, + when the money is trivially built out of capabilities. More puzzling is + the transfer. Alice passed to Bob only a capability, which therefor had + all the rights-transfer properties of our first column. However, by doing + so, she also paid him money, which has all the properties of the last + column. Unsurprisingly, to resolve this we have to think in terms of two + levels of abstraction. We must understand how these levels relate to each other, but we must keep them distinct.
-
At the capability level, Alice is sharing with Bob the specific - right to (at the money level) gain an exclusive on 10 fungible - units of a particular currency. At the moment when Bob's foo - method binds the incoming purse to the payment parameter-variable, - Bob is now (capability level) sharing with Alice this specific right. - In the next statement, where Bob deposits the money into his own purse, - he is exercising this right to gain an exclusive, and thereby obtaining +
At the capability level, Alice is sharing with Bob the specific + right to (at the money level) gain an exclusive on 10 fungible + units of a particular currency. At the moment when Bob's foo + method binds the incoming purse to the payment parameter-variable, + Bob is now (capability level) sharing with Alice this specific right. + In the next statement, where Bob deposits the money into his own purse, + he is exercising this right to gain an exclusive, and thereby obtaining exclusive rights.
-
To discuss the instruments presented below, we need to exercise similar +
To discuss the instruments presented below, we need to exercise similar care in keeping the levels straight.

Options
-
From the point of view of a buyer, an option is the right to buy or sell - some amount of some underlying instrument, such as stock, for a fixed - price, within a period of time. From the point of view of the seller (called - an option-writer), it is an offer to sell or buy at a locked in price, - where the offer expires at a future time. Here we deal only with a covered - call option. Call means the option holder may buy the stock. Covered - means that the option seller puts aside stock to cover the possible exercise - of the option as long as the option is outstanding, ensuring that he has +
From the point of view of a buyer, an option is the right to buy or sell + some amount of some underlying instrument, such as stock, for a fixed + price, within a period of time. From the point of view of the seller (called + an option-writer), it is an offer to sell or buy at a locked in price, + where the offer expires at a future time. Here we deal only with a covered + call option. Call means the option holder may buy the stock. Covered + means that the option seller puts aside stock to cover the possible exercise + of the option as long as the option is outstanding, ensuring that he has the stock to sell should the option holder exercise her rights to buy.
-
Due to space limitations, the following is an idealization which nevertheless - should present the essence of a covered call option as a smart contract. - Assume the existence of a broker mutually trusted by the option buyer - and seller. The option seller "writes" the contract by delivering - to the broker the last four parameters of the CoveredCallOptionMaker - below. (The first three parameters come from the broker.) The broker invokes - a CoveredCallOptionMaker within a vat he is running (so the - mutual trust of the contract-platform can be inherited from mutual trust - in the broker), and delivers to the option buyer the resulting CoveredCallOption. - The option buyer can exercise the option, paying the exercise price and - gaining the stock, by calling the exercise method before +
Due to space limitations, the following is an idealization which nevertheless + should present the essence of a covered call option as a smart contract. + Assume the existence of a broker mutually trusted by the option buyer + and seller. The option seller "writes" the contract by delivering + to the broker the last four parameters of the CoveredCallOptionMaker + below. (The first three parameters come from the broker.) The broker invokes + a CoveredCallOptionMaker within a vat he is running (so the + mutual trust of the contract-platform can be inherited from mutual trust + in the broker), and delivers to the option buyer the resulting CoveredCallOption. + The option buyer can exercise the option, paying the exercise price and + gaining the stock, by calling the exercise method before the deadline has expired.
-
Among the simplifications: This protocol assumes share ownership is handled - using the same code we've been using for money. This seems plausible, - as stock ownership is also exclusive, fungible, and assayable. However, - it is also exercisable -- by voting and collecting dividends [MacKenzie99]. - When stock is put aside to cover a call, the owner loses the right to - sell it, but, until the option is exercised, retains the exercise rights +
Among the simplifications: This protocol assumes share ownership is handled + using the same code we've been using for money. This seems plausible, + as stock ownership is also exclusive, fungible, and assayable. However, + it is also exercisable -- by voting and collecting dividends [MacKenzie99]. + When stock is put aside to cover a call, the owner loses the right to + sell it, but, until the option is exercised, retains the exercise rights of the stock. The following code ignores this issue.
-
The only abstraction used below that is not yet explained is timer. - timer provides access to real-world time. Its relevant operations +
The only abstraction used below that is not yet explained is timer. + timer provides access to real-world time. Its relevant operations are:
-
-
+
+
- - + - - - + - - + @@ -249,17 +249,17 @@
+

timer after(duration, thunk)
This tells the timer to call thunk after duration + This tells the timer to call thunk after duration time has passed. (A thunk is a no-argument procedure, such as cancel().)
+

timer now()
What's the current time?
+

timer date(time)

-
In a typical object system, such a timer service might be globally accessible, - but this would violate the capability constraints. No amount of internal - computation would enable an object to determine the time, so access to - time gives the object the ability to be affected by the outside world. - By making this access into a first class object, we can instead supply +
In a typical object system, such a timer service might be globally accessible, + but this would violate the capability constraints. No amount of internal + computation would enable an object to determine the time, so access to + time gives the object the ability to be affected by the outside world. + By making this access into a first class object, we can instead supply other sources of time, as would be required, e.g., for deterministic replay.
-
Again due to space limitations, the following code ignores distribution +
Again due to space limitations, the following code ignores distribution and concurrency issues.

An Options Smart Contract
-
-
+
+

def CoveredCallOptionMaker(timer, # access to a real-world time service escrowedStock, # reserves stock while offer is OPEN escrowedMoney # intermediate money-transfer purse @@ -313,45 +313,45 @@ }

-
When the option is written, the stock in the purse provided by the option - seller is put into escrow within the returned CoveredCallOption, - but the original purse is remembered in case the stock needs to be returned. - The CoveredCallOption and the cancel function - share the same state. They can be seen as facets of the option-composite. +
When the option is written, the stock in the purse provided by the option + seller is put into escrow within the returned CoveredCallOption, + but the original purse is remembered in case the stock needs to be returned. + The CoveredCallOption and the cancel function + share the same state. They can be seen as facets of the option-composite. Only the timer holds a reference to the cancel facet.
-
If the option holder calls exercise, then the option will - first attempt to deposit from the holder's moneySrc purse - into the broker's empty escrowedMoney purse. Only - if this succeeds does the option then transfer the money and stock from - the purses in which they are escrowed into the writer's moneyDest - purse and the holder's stockDest purse, respectively, and - close the option. If the money is not successfully escrowed, the stock +
If the option holder calls exercise, then the option will + first attempt to deposit from the holder's moneySrc purse + into the broker's empty escrowedMoney purse. Only + if this succeeds does the option then transfer the money and stock from + the purses in which they are escrowed into the writer's moneyDest + purse and the holder's stockDest purse, respectively, and + close the option. If the money is not successfully escrowed, the stock isn't transferred and the option remains open.
-
Alternatively, if the deadline passes before the option is exercised, - the escrowed stock is transferred back into the purse it came from and +
Alternatively, if the deadline passes before the option is exercised, + the escrowed stock is transferred back into the purse it came from and the option is cancelled.
-
So what kind of a right have we created here? It is specific, but fungible - options can be created. It isn't quite assayable, as the options holder - cannot reliably tell which stock is being offered or which currency is - demanded in exchange, but a more complex contract in the spirit of the - above code can provide full assayability (given trust in the broker, of - course). It is certainly exercisable! It also introduces a new dimension - -- it is perishable rather than durable. The right to exercise spoils +
So what kind of a right have we created here? It is specific, but fungible + options can be created. It isn't quite assayable, as the options holder + cannot reliably tell which stock is being offered or which currency is + demanded in exchange, but a more complex contract in the spirit of the + above code can provide full assayability (given trust in the broker, of + course). It is certainly exercisable! It also introduces a new dimension + -- it is perishable rather than durable. The right to exercise spoils after a time.
-
However, unlike a real-world option, it is sharable rather than exclusive. - If Alice, the initial options holder, wishes to give Bob the option, Bob - must assume that Alice still holds it, and therefor may still exercise - it. As with the purse, they are sharing rights to manipulate exclusive - rights. However, Bob cannot cope in the same manner, since the exclusive - he wants now is not an exclusive on the underlying stock but an exclusive +
However, unlike a real-world option, it is sharable rather than exclusive. + If Alice, the initial options holder, wishes to give Bob the option, Bob + must assume that Alice still holds it, and therefor may still exercise + it. As with the purse, they are sharing rights to manipulate exclusive + rights. However, Bob cannot cope in the same manner, since the exclusive + he wants now is not an exclusive on the underlying stock but an exclusive on the right to exercise the option. How can we make an exclusive option?
-
We could try rewriting the above code to provide exclusivity as well, - but the result would mix separate concerns into one abstraction. Better - to add exclusivity to the above code by composition. Here's an adaptation - of our money code to provide exclusivity for a single specific exercisable +
We could try rewriting the above code to provide exclusivity as well, + but the result would mix separate concerns into one abstraction. Better + to add exclusivity to the above code by composition. Here's an adaptation + of our money code to provide exclusivity for a single specific exercisable object:
-
-
+
+

def TitleCompanyMaker(precious, name) :any { require(precious != null, _{"must provide an object"}) def [sealer, unsealer] := BrandMaker pair(name) @@ -380,56 +380,56 @@ }

-
Given a single object, this returns an initial purse holding this object. - This purse is able to sprout other empty purses all able to hold only - this object. Among such sibling purses, only one holds the object at a - time. To move the object from one purse to another, one must have both +
Given a single object, this returns an initial purse holding this object. + This purse is able to sprout other empty purses all able to hold only + this object. Among such sibling purses, only one holds the object at a + time. To move the object from one purse to another, one must have both purses.
-
Such a purse is also an exercisable right. The holder of a purse may - invoke any method on the underlying object. Care must be taken when programming - objects that are intended to be held in such purses -- they should be - designed not to return references to themselves as the result of any operation, +
Such a purse is also an exercisable right. The holder of a purse may + invoke any method on the underlying object. Care must be taken when programming + objects that are intended to be held in such purses -- they should be + designed not to return references to themselves as the result of any operation, as this would invalidate the exclusivity property.
-
Once the broker creates the option, using the arguments from the option - seller, it wouldn't release this non-exclusive options object to the first - buyer, because the first buyer would then be unable to resell it. Instead, - it would call TitleCompanyMaker(option, ...) and give - the first buyer, Alice, the resulting purse. It would also hold on to +
Once the broker creates the option, using the arguments from the option + seller, it wouldn't release this non-exclusive options object to the first + buyer, because the first buyer would then be unable to resell it. Instead, + it would call TitleCompanyMaker(option, ...) and give + the first buyer, Alice, the resulting purse. It would also hold on to this purse, indexed by a description of the option it created.
-
When Bob wants to buy an exclusive on the option from Alice, Bob would - first go to the broker to acquire an empty purse for holding the option - that meets his description. The broker looks up the original purse from - the description, and gives Bob a new sprout of this purse. When Alice - gives Bob her option-holding, he deposits it into the purse he got from - the broker. If this succeeds, he knows he now has an exclusive on the - option to gain an exclusive on some amount of stock.
+
When Bob wants to buy an exclusive on the option from Alice, Bob would + first go to the broker to acquire an empty purse for holding the option + that meets his description. The broker looks up the original purse from + the description, and gives Bob a new sprout of this purse. When Alice + gives Bob her option-holding purse, he deposits it into the purse he got + from the broker. If this succeeds, he knows he now has an exclusive on + the option to gain an exclusive on some amount of stock.

Composable Security, Readable Contracts
-
The kind of composition of abstractions demonstrated above is familiar - in the object programming world, but without the security shown. The creation - of cryptographic protocols for securely trading a variety of financial - instruments is familiar in the financial cryptography world, but without - the separation of concerns and easy composability shown. The best capability - operating system work [Hardy85] - does combine abstraction and security in this way, but without a notation - to make the issues clear, and only when all parties fully trust one common +
The kind of composition of abstractions demonstrated above is familiar + in the object programming world, but without the security shown. The creation + of cryptographic protocols for securely trading a variety of financial + instruments is familiar in the financial cryptography world, but without + the separation of concerns and easy composability shown. The best capability + operating system work [Hardy85] + does combine abstraction and security in this way, but without a notation + to make the issues clear, and only when all parties fully trust one common platform.
-
By using the Granovetter Operator as a bridge, we are able to apply strengths - from all three worlds synergistically to the engineering of a single integrated +
By using the Granovetter Operator as a bridge, we are able to apply strengths + from all three worlds synergistically to the engineering of a single integrated system.
-
Financial cryptography is a broad field encompasing a wide range of more - specialized problem areas: cryptosystems, transactional protocols, user - interface design, interface with existing financial and legal institutions, - accounting, interface with legacy systems, creation of innovative financial - instruments and institutions, the list is endless. However, the benefits - achievable from specialization in any of these subfields have been limited - by the costs of systems integration. It has hitherto been difficult to - layer abstractions so that one can think clearly about one part of a system - design without having to think about all the other parts of the system - design simultaneously. This is especially troublesome in the development - of financial systems where developers must proceed very cautiously due - to the enormous potential cost of errors. It is our hope that the abstractions, - tools and notation we have presented here will go a long way towards filling - the need for the kinds of compositional power that will enable us to realize +
Financial cryptography is a broad field encompassing a wide range of + more specialized problem areas: cryptosystems, transactional protocols, + user interface design, interface with existing financial and legal institutions, + accounting, interface with legacy systems, creation of innovative financial + instruments and institutions, the list is endless. However, the benefits + achievable from specialization in any of these subfields have been limited + by the costs of systems integration. It has hitherto been difficult to + layer abstractions so that one can think clearly about one part of a system + design without having to think about all the other parts of the system + design simultaneously. This is especially troublesome in the development + of financial systems where developers must proceed very cautiously due + to the enormous potential cost of errors. It is our hope that the abstractions, + tools and notation we have presented here will go a long way towards filling + the need for the kinds of compositional power that will enable us to realize the tremendous promise of the world of electronic commerce.
1.33 +1 -1 e/doc/elib/capability/ode/ode-objects.html Index: ode-objects.html =================================================================== RCS file: /cvs/e/doc/elib/capability/ode/ode-objects.html,v retrieving revision 1.32 retrieving revision 1.33 diff -u -r1.32 -r1.33 --- ode-objects.html 2001/04/08 18:41:18 1.32 +++ ode-objects.html 2001/05/09 07:14:17 1.33 @@ -270,7 +270,7 @@ ? def carol := CounterMaker() # value: <counter> -? carol getCount +? carol getCount() # value: 0 ? carol incr() 1.9 +14 -14 e/doc/elib/concurrency/semi-transparent.html Index: semi-transparent.html =================================================================== RCS file: /cvs/e/doc/elib/concurrency/semi-transparent.html,v retrieving revision 1.8 retrieving revision 1.9 diff -u -r1.8 -r1.9 --- semi-transparent.html 2001/05/09 05:00:41 1.8 +++ semi-transparent.html 2001/05/09 07:14:17 1.9 @@ -81,15 +81,15 @@ would suggest, nevertheless, E gives up on full transparency for the same reasons as what we take to be the main argument of the paper: There are compellingly useful features of local (single machine or single address - space) computation that are either not naturally available for distributed - computation. It is too expensive to give up these features in the local - case, where they are cheap, and for many of these, it is impossible or - prohibitively expensive to support them in the distributed case. In order - to support them in both cases, we must introduce a semantic non-uniformity - between the two cases. (For a related but different case against full - transparency, see Doug Lea's Design + space) computation that are not naturally available for distributed computation. + It is too expensive to give up these features in the local case, where + they are cheap, and for many of these, it is impossible or prohibitively + expensive to support them in the distributed case. In order to support + them in both cases, we must introduce a semantic non-uniformity between + the two cases. (For a related but different case against full transparency, + see Doug Lea's Design for Open Systems in Java.)
-
However, we can give up on full tranparency without giving up all the +
However, we can give up on full transparency without giving up all the benefits of transparency. We define semi-transparent network programming as the second half of the above definition: Any correct program written for a bunch of objects distributed over the network will remain @@ -132,7 +132,7 @@

Avoids temporal inconsistency -- Likewise, no hardware failure can sever the reference between caller and callee without killing - the both. Therefore they are always in contact when they should be + them both. Therefore they are always in contact when they should be in contact, and can thereby safely make coordinated changes to their state.

@@ -168,7 +168,7 @@

Partial failure: Communication lines can temporarily go out, partitioning one part of the network from another. Machine can fail: - in a trasient fashion, rolling back to a previous stable state; or + in a transient fashion, rolling back to a previous stable state; or permanently, making the objects they host forever inaccessible. From a machine not able to reach a remote object, it is generally impossible to tell which of these failure scenarios is occurring. The system @@ -189,12 +189,12 @@ which means their apps can get wedged during a partition.) The burden of choosing failure-visibility is that E must provide the programmer tools that can be used reliably at reasonable effort to recover distributed - consistency on their own. Given the visibly of failure, such recovery + consistency on their own. Given the visibility of failure, such recovery is necessarily specific to the semantics of a given distributed app.

E handles this set of differences by adding surprisingly few new abstractions to the conventional set of single-addess space sequential pure object - programming abstactions. In addition to the conventional NEAR + programming abstractions. In addition to the conventional NEAR reference, having all the synchrony and reliability properties available in a single address space, E introduces a reference taxonomy of other reference types including the EVENTUAL @@ -281,13 +281,13 @@ to the stack frame, implying that the stack frame waits for a response to be sent to it along this arrow.

On the right, nothing points at the sending stack frame, so it continues - after emitting the message. Moreever, this stack frame continues holding + after emitting the message. Moreover, this stack frame continues holding a promise for the outcome of the message -- the tail of the arrow -- even though the outcome itself hasn't been determined yet. The arrowhead with the gray halo is the ability to determine the resolution of the promise. It serves in the continuation-role of the message delivered to Bob. Messages sent on the arrowtail of a reference always move towards the arrowhead, - even while the arrowhead is on route. This is the basis for E's Message + even while the arrowhead is en-route. This is the basis for E's Message Pipelining.

When Bob finishes reacting to a message, he reports an outcome to the message's continuation. On the left, Alice's stack frame resumes by reacting 1.4 +2 -2 e/doc/elib/distrib/pipeline.html Index: pipeline.html =================================================================== RCS file: /cvs/e/doc/elib/distrib/pipeline.html,v retrieving revision 1.3 retrieving revision 1.4 diff -u -r1.3 -r1.4 --- pipeline.html 2001/04/24 02:42:33 1.3 +++ pipeline.html 2001/05/09 07:14:18 1.4 @@ -121,7 +121,7 @@ components. Fortunately, these three should correlate, and do in practice.

But we'd also like to spread our distributed computations - across separate machines according to the performace consequences. The + across separate machines according to the performance consequences. The key performance issue is often latency. And as hardware improves, latency will clearly dominate as the limiting factor. At the endpoints, processing will be ever cheaper and buffers larger, with the limits still many orders @@ -138,7 +138,7 @@ rather than mechanism. Good modular systems of abstractions should normally export orthogonal composable primitives which are useful only when composed, but leave it to their clients to determine which composition - to use. But this causes the client to compose several invocation to do + to use. But this causes the client to compose several invocations to do any one useful thing.

When this tension gets severe, the only real way to resolve it is with real mobile code. The client sends code to the server, such From markm@eros.cs.jhu.edu Wed May 9 01:00:43 2001 Received: from mail.eros-os.org (IDENT:root@EROS.CIS.UPENN.EDU [158.130.6.119]) by eros.cs.jhu.edu (8.11.0/8.11.0) with ESMTP id f4950hK26837 for ; Wed, 9 May 2001 01:00:43 -0400 Received: from eros.cs.jhu.edu (IDENT:root@eros.cs.jhu.edu [128.220.223.245]) by mail.eros-os.org (8.9.3/8.9.3) with ESMTP id AAA00691 for ; Wed, 9 May 2001 00:50:54 -0400 From: markm@eros.cs.jhu.edu Received: (from markm@localhost) by eros.cs.jhu.edu (8.11.0/8.11.0) id f4950gk26832 for e-cvs@eros-os.org; Wed, 9 May 2001 01:00:42 -0400 Date: Wed, 9 May 2001 01:00:42 -0400 Message-Id: <200105090500.f4950gk26832@eros.cs.jhu.edu> To: e-cvs@eros-os.org Subject: [E-cvs] cvs commit: e/doc/elib/distrib obj-passing.html Sender: e-cvs-admin@mail.eros-os.org Errors-To: e-cvs-admin@mail.eros-os.org X-BeenThere: e-cvs@mail.eros-os.org X-Mailman-Version: 2.0beta5 Precedence: bulk List-Id: markm 01/05/09 01:00:42 Modified: doc toc.txt doc/elang/concurrency epimenides.html introducer.html doc/elib/concurrency event-loop.html msg-passing.html partial-order.html semi-transparent.html turns.html vat.html doc/elib/distrib obj-passing.html Log: lots of typos. Thanks to Darius Bacon Revision Changes Path 1.40 +1 -0 e/doc/toc.txt Index: toc.txt =================================================================== RCS file: /cvs/e/doc/toc.txt,v retrieving revision 1.39 retrieving revision 1.40 diff -u -r1.39 -r1.40 --- toc.txt 2001/05/07 08:29:24 1.39 +++ toc.txt 2001/05/09 05:00:41 1.40 @@ -65,6 +65,7 @@ GCAnswerOp.html ShutdownOp.html TerminatedOp.html + WormholeOp.html # NewFarDesc.html NewRemoteVowDesc.html 1.27 +10 -10 e/doc/elang/concurrency/epimenides.html Index: epimenides.html =================================================================== RCS file: /cvs/e/doc/elang/concurrency/epimenides.html,v retrieving revision 1.26 retrieving revision 1.27 diff -u -r1.26 -r1.27 --- epimenides.html 2001/04/30 20:36:05 1.26 +++ epimenides.html 2001/05/09 05:00:41 1.27 @@ -108,7 +108,7 @@ her reference to Bob is a local reference. A reference is local if

-
both the arrow head and the arror tail are in the same Vat, and
+
both the arrow head and the arrow tail are in the same Vat, and

if the arrow head is already attached to an object.

Once a reference is local it will be forever local, and it will always @@ -116,15 +116,15 @@ a message sent on it to this object. Conventional single-address-space object-oriented programming (sasoop) has only the equivalent of local references.
-
The other possible states for a reference are deferred and broken. - A reference that crosses between machines is deferred, as is a reference - whose arrow head isn't yet attached to an object. When you use a variable - on the right side of a definition that will be defined on the left side, - during the execution of this right side, the value of variable is a deferred - reference designating the object that the variable will be initialized - to. It is the tail of an arrow whose head will be hooked by, but it doesn't - get hooked up until after the right side finishes executing. We also refer - to this as a promise for the value of the variable.
+
The other possible states for a reference are deferred and broken. + A reference that crosses between machines is deferred, as is a reference + whose arrow head isn't yet attached to an object. When you use a variable + on the right side of a definition that will be defined on the left side, + during the execution of this right side, the value of the variable is + a deferred reference designating the object that the variable will be + initialized to. It is the tail of an arrow whose head will be hooked up, + but it doesn't get hooked up until after the right side finishes executing. + We also refer to this as a promise for the value of the variable.

Since there's not yet an object on the other side of the arrow, a do it now message pass results in the above error. However, we can use E's do it eventually message pass, the asynchronous send operator:
1.33 +7 -7 e/doc/elang/concurrency/introducer.html Index: introducer.html =================================================================== RCS file: /cvs/e/doc/elang/concurrency/introducer.html,v retrieving revision 1.32 retrieving revision 1.33 diff -u -r1.32 -r1.33 --- introducer.html 2001/04/13 19:23:51 1.32 +++ introducer.html 2001/05/09 05:00:41 1.33 @@ -206,13 +206,13 @@

-
Alternatively, if you have windows to both processes in front of you, - you can just copy and paste from one two the other. Or you could email - the uri to an account you can read on the other machine -- whatever works. - This is the act of initial introduction. In situations where security - is important you must convey this string from one process to the other - in a secure manner, such as in a PGP-encrypted email message. Assuming - this has been done, E ensures that all further communication between these +
Alternatively, if you have windows to both processes in front of you, + you can just copy and paste from one to the other. Or you could email + the uri to an account you can read on the other machine -- whatever works. + This is the act of initial introduction. In situations where security + is important you must convey this string from one process to the other + in a secure manner, such as in a PGP-encrypted email message. Assuming + this has been done, E ensures that all further communication between these processes remains secure.

This act of introduction is another example of the Granovetter 1.7 +2 -2 e/doc/elib/concurrency/event-loop.html Index: event-loop.html =================================================================== RCS file: /cvs/e/doc/elib/concurrency/event-loop.html,v retrieving revision 1.6 retrieving revision 1.7 diff -u -r1.6 -r1.7 --- event-loop.html 2001/02/26 08:31:25 1.6 +++ event-loop.html 2001/05/09 05:00:41 1.7 @@ -93,7 +93,7 @@
(For more on steps 1, 2, and 3, see this.)
-
Much of the charm of pure Lambda Calculus is its blissfully ignorance +
Much of the charm of pure Lambda Calculus is its blissful ignorance of all issues of time and execution order. Arithmetic is beautifully timeless in the same sense. Unfortunately, once we add side-effects, we have to come to terms with these issues. Solutions that enable us, @@ -180,7 +180,7 @@ method must obtain a lock on the counter object as a whole before proceeding into the method body, and that it should release this lock on exit. For this counter, the above code is unproblematic. However, in general the - method body with call other methods on other objects. This means the thread + method body will call other methods on other objects. This means the thread will be holding some locks (on objects whose synchronized methods are part-way through execution) while waiting to obtain other locks. This is a formula for deadly embrace. To write correct thread-based programs, 1.13 +173 -173 e/doc/elib/concurrency/msg-passing.html Index: msg-passing.html =================================================================== RCS file: /cvs/e/doc/elib/concurrency/msg-passing.html,v retrieving revision 1.12 retrieving revision 1.13 diff -u -r1.12 -r1.13 --- msg-passing.html 2001/04/17 23:08:29 1.12 +++ msg-passing.html 2001/05/09 05:00:41 1.13 @@ -46,60 +46,60 @@
- +
Taxonomy of Messaging Primitives

E has the following message passing primitives,
-
+

-
i) the synchronous immediate call +
i) the synchronous immediate call (*)
-
ii) the synchronous outcome, which has - three sub-cases +
ii) the synchronous outcome, which has + three sub-cases

Success: evaluation to a result

Failure: throw()ing a problem report

Escape: like break() or continue()

-
iii) the asynchronous eventual ("<-") send, - where an outcome report +
iii) the asynchronous eventual ("<-") send, + where an outcome report

is not expected -- the sendOnly.
-
may be expected -- the pipelined send +
may be expected -- the pipelined send (*)

-
For all of these, a message is conveyed to an individual recipient, and - contains at least a verb (a String) and a tuple of arguments. A message - often represents a request (identified by the verb and the number of arguments, - but not their types), so the recipient generally knows why it is receiving - new authority. This facilitates the programming of non-confusable deputies. - For the cases marked with (*), the message additionally contains a continuation - -- the object to which the outcome of performing the request should be +
For all of these, a message is conveyed to an individual recipient, and + contains at least a verb (a String) and a tuple of arguments. A message + often represents a request (identified by the verb and the number of arguments, + but not their types), so the recipient generally knows why it is receiving + new authority. This facilitates the programming of non-confusable deputies. + For the cases marked with (*), the message additionally contains a continuation + -- the object to which the outcome of performing the request should be reported.
-
E - computation only occurs within a stack frame -- shown as a lightning bolt - within an object. A stack frame happens when an object receives a call - or send/sendOnly. Recall that an object is an instance of an object expression, - and combines the behavior this expression describes with the state from - its instantiating context (the scope in which the object expression was - evaluated). Similarly, a stack frame can be seen as an instance of the - method or matcher corresponding to the received message, and combines - the described behavior with state as well. The stack frame�s state is - the object�s state plus the state resulting from matching the incoming - message with the head of the method or matcher. During its execution, - a stack frame can accumulate more state by defining new variables. -
Since all computation happens only within stack frames, - all messages are emitted only from stack frames. When object-granularity - analysis suffices, as it often does for security reasoning, we often skip - illustrating the stack frames, as in the Granovetter - Diagram. +
E + computation only occurs within a stack frame -- shown as a lightning bolt + within an object. A stack frame happens when an object receives a call + or send/sendOnly. Recall that an object is an instance of an object expression, + and combines the behavior this expression describes with the state from + its instantiating context (the scope in which the object expression was + evaluated). Similarly, a stack frame can be seen as an instance of the + method or matcher corresponding to the received message, and combines + the described behavior with state as well. The stack frame�s state is + the object�s state plus the state resulting from matching the incoming + message with the head of the method or matcher. During its execution, + a stack frame can accumulate more state by defining new variables. +
Since all computation happens only within stack frames, + all messages are emitted only from stack frames. When object-granularity + analysis suffices, as it often does for security reasoning, we often skip + illustrating the stack frames, as in the Granovetter + Diagram.
i) The Immediate Call
-
The above diagram and the following code illustrates Alice - synchronously calling Bob: -
-
+
The above diagram and the following code illustrates Alice + synchronously calling Bob: +
+

def alice { to msg1() { def result := bob msg2(carol) @@ -107,51 +107,51 @@ } }

-
The call is only allowed if the reference to the recipient - is NEAR. Otherwise, the attempt to - call instead throws an appropriate exception. -
Besides - the components shared by all messages, a synchronous call contains an - additional special argument -- the continuation -- that points at the - caller�s stack frame. The call also turns the calling stack frame from - active to suspended. Computation in fact occurs only in active stack frames. - A suspended stack frame must be pointed to exactly by one special continuation - argument. An active stack frame is not pointed at. There can be at most - one active stack frame in a Vat, and all stack frames are in a linear - chain between it and a top stack frame -- a stack frame directly - spawned to service a pending delivery. (When between turns, there are - no stack frames, as happens when the queue is empty, or when a Vat is - sitting on disk waiting to be revived from checkpoint.) -
The message passed in a call need not be allocated as a - separate object, as no time passes between departing from the caller and - arriving at the callee. Rather, the act of calling simultaneously creates - the receiving stack frame in the callee. All stack frames contain the - special continuation argument from the message they received, but -- unlike - the other arguments received from the message -- the continuation is not - explicitly accessible to the program. -
See also the Kernel-E - Call Expression. -
ii) Synchronous Outcome of Stack-Frame +
The call is only allowed if the reference to the recipient + is NEAR. Otherwise, the attempt to + call instead throws an appropriate exception. +
Besides + the components shared by all messages, a synchronous call contains an + additional special argument -- the continuation -- that points at the + caller�s stack frame. The call also turns the calling stack frame from + active to suspended. Computation in fact occurs only in active stack frames. + A suspended stack frame must be pointed to by exactly one special continuation + argument. An active stack frame is not pointed at. There can be at most + one active stack frame in a Vat, and all stack frames are in a linear + chain between it and a top stack frame -- a stack frame directly + spawned to service a pending delivery. (When between turns, there are + no stack frames, as happens when the queue is empty, or when a Vat is + sitting on disk waiting to be revived from checkpoint.) +
The message passed in a call need not be allocated as a + separate object, as no time passes between departing from the caller and + arriving at the callee. Rather, the act of calling simultaneously creates + the receiving stack frame in the callee. All stack frames contain the + special continuation argument from the message they received, but -- unlike + the other arguments received from the message -- the continuation is not + explicitly accessible to the program. +
See also the Kernel-E + Call Expression. +
ii) Synchronous Outcome of Stack-Frame Completion
-
The callee can use the continuation only by completing the - execution of its stack frame, thereby also causing it to be discarded. - The nature of this completion implicitly passes an outcome message to - the continuation. Unlike calls and returns, outcome messages have no hidden - arguments. There are three kinds of outcome, each represented with its - own outcome message. When the continuation is a stack frame, these outcome - messages are only for expository purposes, as neither the caller nor callee - can deal with them explicitly. We choose describe these as messages so - we can understand all transfer of authority in terms of the Granovetter - diagram. -
+
The callee can use the continuation only by completing the + execution of its stack frame, thereby also causing it to be discarded. + The nature of this completion implicitly passes an outcome message to + the continuation. Unlike calls and returns, outcome messages have no hidden + arguments. There are three kinds of outcome, each represented with its + own outcome message. When the continuation is a stack frame, these outcome + messages are only for expository purposes, as neither the caller nor callee + can deal with them explicitly. We choose describe these as messages so + we can understand all transfer of authority in terms of the Granovetter + diagram. +

-
Success, - corresponding to �falling off the end� and represented by passing a - �resolve(result)� message to the continuation. The diagram - and the following code illustrate Bob returning Dana as a successful - result to Alice: -
-
+
Success, + corresponding to �falling off the end� and represented by passing a + �resolve(result)� message to the continuation. The diagram + and the following code illustrate Bob returning Dana as a successful + result to Alice: +
+

def bob { to msg2(carol) { ... //whatever @@ -159,16 +159,16 @@ } }

-
In this case, the call expression with which Alice called Bob evaluates - to this result, and the stack frame in Alice suspended on this call +
In this case, the call expression with which Alice called Bob evaluates + to this result, and the stack frame in Alice suspended on this call expression continues from this point.
-
-
Failure, as a result of - execution of a �throw(problem)� and represented by passing - a �smash(problem)� message to the continuation. The following - code: -
-
+
+
Failure, as a result of + execution of a �throw(problem)� and represented by passing + a �smash(problem)� message to the continuation. The following + code: +
+

def bob { to msg2(carol) { ... //whatever @@ -177,72 +177,72 @@ } }

-
can be illustrated with the same diagram, but the verb - is now �smash� instead of �resolve�. Execution - within Alice's stack frame now skips to the closest enclosing try-catch - or try-finally expression. - If these are none, then Alice's stack frame completes in failure as - well, and the smash(problem) message gets forwarded to - Alice's stack frame's continuation, if any. -
-
-
Escape, corresponding to - invoking a non-disabled ejector (as created by an escape - expression), and represented by passing �eject(ejection)� - to the continuation. (** need explanation of Ejectors and ejections) -
+
can be illustrated with the same diagram, but the verb + is now �smash� instead of �resolve�. Execution + within Alice's stack frame now skips to the closest enclosing try-catch + or try-finally expression. + If these are none, then Alice's stack frame completes in failure as + well, and the smash(problem) message gets forwarded to + Alice's stack frame's continuation, if any. +
+
+
Escape, corresponding to + invoking a non-disabled ejector (as created by an escape + expression), and represented by passing �eject(ejection)� + to the continuation. (** need explanation of Ejectors and ejections) +

-
Both Failure and Escape are forms of non-local exit. -
Other than by invoking its continuation, the callee cannot - stop executing, even on I/O. I/O operations that would normally block - are instead handled by requesting notification be delivered -- by sending - -- to a designated object. As a result, E is strongly deadlock-free (but - is still subject to live-lock by infinite loops). +
Both Failure and Escape are forms of non-local exit. +
Other than by invoking its continuation, the callee cannot + stop executing, even on I/O. I/O operations that would normally block + are instead handled by requesting notification be delivered -- by sending + -- to a designated object. As a result, E is strongly deadlock-free (but + is still subject to live-lock by infinite loops).
iii) The Eventual Send

-
Returning to the human world for a moment, as I schedule - my time, I find I mainly use two patterns: If in performing task X I find - I�m blocked on the outcome of a subtask Y, I put the X aside for awhile, - work on Y until its done, and then continue with X. This corresponds to - synchronous do it immediately, or call-return scheduling as explained - above. The other pattern is that, in performing task X, I come to realize - another task Y I need to perform, but I don�t need to do Y now. To ensure - I don�t forget Y, I jot a note on a to-do list, and then continue with - my present task. -
This latter pattern corresponds to asynchronous do it - eventually scheduling, as supported by the eventual send. A send is - written like a synchronous call, but with a �<-�, the eventually - operator, between the recipient and the message. A record that this message - must be delivered to this recipient is duly noted, but then the original - turns continues about its business unaffected. -
There - are two forms of eventual send, written the same way, but distinguished - by whether the value of send expression appears to be needed. -
-
+
Returning to the human world for a moment, as I schedule + my time, I find I mainly use two patterns: If in performing task X I find + I�m blocked on the outcome of a subtask Y, I put the X aside for awhile, + work on Y until it's done, and then continue with X. This corresponds + to synchronous do it immediately, or call-return scheduling as + explained above. The other pattern is that, in performing task X, I come + to realize another task Y I need to perform, but I don�t need to do Y + now. To ensure I don�t forget Y, I jot a note on a to-do list, and then + continue with my present task. +
This latter pattern corresponds to asynchronous do it + eventually scheduling, as supported by the eventual send. A send is + written like a synchronous call, but with a �<-�, the eventually + operator, between the recipient and the message. A record that this message + must be delivered to this recipient is duly noted, but then the original + turn continues about its business unaffected. +
There + are two forms of eventual send, written the same way, but distinguished + by whether the value of send expression appears to be needed. +
+

-
-
sendOnly. When a send expression appears - in a context where it is statically apparent that the value of the +
+
sendOnly. When a send expression appears + in a context where it is statically apparent that the value of the send expression will be unused, such as to the left of a semi-colon:
-
+

bob <- foo(carol); ...

-
then the message is a pure one-way message containing only the verb - ("foo") and a list of the explicit arguments ([carol]), - just as shown in the basic Granovetter diagram. The only feedback - Alice can get from the performance of the message is that she explicitly - arranges for. When Bob finishes processing the message, he reports - the outcome of the turn to no one.
+
then the message is a pure one-way message containing only the verb + ("foo") and a list of the explicit arguments ([carol]), + just as shown in the basic Granovetter diagram. The only feedback + Alice can get from the performance of the message is that which she + explicitly arranges for. When Bob finishes processing the message, + he reports the outcome of the turn to no one.

-
-
The pipelined send. When a - send expression appears in a context where it is not statically apparent - that the value of the send expression will be unused, ie, where static - analysis does not rule out that the value may be used, such as on +
+
The pipelined send. When a + send expression appears in a context where it is not statically apparent + that the value of the send expression will be unused, ie, where static + analysis does not rule out that the value may be used, such as on the right side of a def:
-
+

def promise := bob <- foo(carol);

then, @@ -257,40 +257,40 @@

Turning Control-Flow into Semi-Data-Flow
-
Since Ejectors are only dynamic in extent -- they only remain valid until - their spawning escape expression completes -- the outcome of a turn cannot - be an escape, only success or failure. Therefore, the Resolver only needs - to respond to "resolve(result)" and "smash(problem)". - In the first case, the promise becomes equivalent to result. - In the second, the promise becomes broken, and problem is reported as +
Since Ejectors are only dynamic in extent -- they only remain valid until + their spawning escape expression completes -- the outcome of a turn cannot + be an escape, only success or failure. Therefore, the Resolver only needs + to respond to "resolve(result)" and "smash(problem)". + In the first case, the promise becomes equivalent to result. + In the second, the promise becomes broken, and problem is reported as the reason.
-
Assume that brokenRef is a reference broken with problem. - Note that a stack-frame as continuation reacts differently to "resolve(brokenRef)" - and "smash(problem)" -- the first causes successful evaluation - to brokenRef while the second causes exceptional flow of control. On the - other hand, A Resolver reacts to these two messages identically. As a - result, Alice cannot distinguish between these two ways Bob may have reported +
Assume that brokenRef is a reference broken with problem. + Note that a stack-frame as continuation reacts differently to "resolve(brokenRef)" + and "smash(problem)" -- the first causes successful evaluation + to brokenRef while the second causes exceptional flow of control. On the + other hand, A Resolver reacts to these two messages identically. As a + result, Alice cannot distinguish between these two ways Bob may have reported a problematic outcome.
-
All messages sent on a reference arrow move towards the - arrowhead in order to eventually be delivered to the object pointed at. - Messages sent on an unresolved promise do likewise, but wait behind the - unbound arrowhead until the promise is resolved. Once the promise is resolved, - all messages sent on the promise may now be delivered to this resolution. - In the control-flow programming we started with the caller waits for the - recipeint to be determined. By contrast, with semi-data-flow programming - -- the message, not the sender, waits for the recipient to be determined. +
All messages sent on a reference arrow move towards the + arrowhead in order to eventually be delivered to the object pointed at. + Messages sent on an unresolved promise do likewise, but wait behind the + unbound arrowhead until the promise is resolved. Once the promise is resolved, + all messages sent on the promise may now be delivered to this resolution. + In the control-flow programming we started with the caller waits for the + recipient to be determined. By contrast, with semi-data-flow programming + -- the message, not the sender, waits for the recipient to be determined.
-
(We call this semi-data-flow to distinguish it from - conventional data flow. In conventional data flow, a message would not - be delivered until the recipient and all its arguments were resolved. - This cannot be reconciled with E's partial ordering constraints, and is - undesirable on other grounds as well. On those occasions where it is desired, - it may easily be programmed in E. See the promiseAllDone +
(We call this semi-data-flow to distinguish it from + conventional data flow. In conventional data flow, a message would not + be delivered until the recipient and all its arguments were resolved. + This cannot be reconciled with E's partial ordering constraints, and is + undesirable on other grounds as well. On those occasions where it is desired, + it may easily be programmed in E. See the promiseAllDone (*** link needed) pattern.)

Turning Semi-Data-Flow back into Control-Flow
-
In our story so far, there is a puzzling contagion of eventual-ness. - Once you have a reference that might be eventual, you must send rather - than call on it; and when you do so, you get back another eventual reference +
In our story so far, there is a puzzling contagion of eventual-ness. + Once you have a reference that might be eventual, you must send rather + than call on it; and when you do so, you get back another eventual reference as a promise for the result.

when-catch

whenResolved & whenMoreResolved
1.10 +5 -5 e/doc/elib/concurrency/partial-order.html Index: partial-order.html =================================================================== RCS file: /cvs/e/doc/elib/concurrency/partial-order.html,v retrieving revision 1.9 retrieving revision 1.10 diff -u -r1.9 -r1.10 --- partial-order.html 2001/05/07 08:29:25 1.9 +++ partial-order.html 2001/05/09 05:00:41 1.10 @@ -91,7 +91,7 @@ that reference to send message W to Carol, the happenstance of variable network delays may result in W arriving before X. The reference as handed to Bob gave Bob a dangerous possibility -- of delivering - a message ahead of X -- that was beyonds Alice's notion of the reference's + a message ahead of X -- that was beyond Alice's notion of the reference's meaning. This would be dangerous.

Instead, when a reference is included as an argument of an eventually sent message (as Alice's reference to Carol is included in message @@ -104,7 +104,7 @@ ordering guarantees E provides. The tree of messages connected by a reference topology is the partial order itself.

As of any visualized state, the messages that may be delivered - to Carol are those that have to messages ahead of them in the reference + to Carol are those that have no messages ahead of them in the reference topology. In diagrams #1 and #2, this is only message X. The transition to diagram #3 shows message X being delivered to Carol. Following this, we see in diagram #3 that both messages W and Z are candidates @@ -127,9 +127,9 @@ The implementation is free to deliver messages to Carol in any full order consistent with the specified partial order. It can therefore collapse partial orders to full orders whenever convenient, consistent with these - constraints. As Bill Frantz observed, this one of those rare cases where - the specification is much more "expensive" than the implementation.
-
Although the motivation for these rules is correctness in the face or + constraints. As Bill Frantz observed, this is one of those rare cases + where the specification is much more "expensive" than the implementation.
+
Although the motivation for these rules is correctness in the face of error, we do tighten the specification to deal with security in the face of malice as well. Even if Bob is hosted in a tampered vat, VatB, that doesn't "play by the rules", the protocol must constrain VatB 1.8 +2 -2 e/doc/elib/concurrency/semi-transparent.html Index: semi-transparent.html =================================================================== RCS file: /cvs/e/doc/elib/concurrency/semi-transparent.html,v retrieving revision 1.7 retrieving revision 1.8 diff -u -r1.7 -r1.8 --- semi-transparent.html 2001/04/14 19:56:57 1.7 +++ semi-transparent.html 2001/05/09 05:00:41 1.8 @@ -74,7 +74,7 @@ of Hewitt's Open Systems.

A Note on Distributed Computing argues, in effect, that the - costs of these restriction are too high for general purpose distributed + costs of these restrictions are too high for general purpose distributed computing. While we disagree with many of the particular arguments in the paper, we find the conclusions phrased much too strongly, and we find the above fully transparent systems much more plausible than this paper @@ -229,7 +229,7 @@
Synchronous call-return:

-
val := bob msg(barol)
+
val := bob msg(carol)

1.11 +19 -19 e/doc/elib/concurrency/turns.html Index: turns.html =================================================================== RCS file: /cvs/e/doc/elib/concurrency/turns.html,v retrieving revision 1.10 retrieving revision 1.11 diff -u -r1.10 -r1.11 --- turns.html 2001/04/14 19:56:57 1.10 +++ turns.html 2001/05/09 05:00:41 1.11 @@ -61,16 +61,16 @@ because of a sequence of turns, and each turn executes with mutually exclusive access to this state, and it executes to completion before before the next turn starts.
-
Although other Vats are executing concurrently, a caller - will only see synchronous side effects caused by its callee. Because Vats - are only asunchronously coupled to each other, an E turn implicitly has - full mutual exclusion on all state to which it has synchronous access - -- which is only state within its Vat. As a result, E execution is not - observably distinguishable (except for timing and the effects of infinite - loops) from an implementation in which, across the universe, only one - Vat at a time takes a turn. E�s turns are therefore atomic serializable - micro-transactions, and E is strongly consistency preserving in the face - of concurrency, without any error-prone fine-grained locking. +
Although other Vats are executing concurrently, a caller + will only see synchronous side effects caused by its callee. Because Vats + are only asynchronously coupled to each other, an E turn implicitly has + full mutual exclusion on all state to which it has synchronous access + -- which is only state within its Vat. As a result, E execution is not + observably distinguishable (except for timing and the effects of infinite + loops) from an implementation in which, across the universe, only one + Vat at a time takes a turn. E�s turns are therefore atomic serializable + micro-transactions, and E is strongly consistency preserving in the face + of concurrency, without any error-prone fine-grained locking.
We say micro-transaction above because we purposely unbundle or avoid the features combined by the classic ACID transaction:
@@ -138,15 +138,15 @@ observable variable�s assigner returned from the assignment. The code containing the assignment was likely written without taking the possibility of such side effects in mind, and this is as it should be. -
When Alice passes a message to Bob in order to subcontract - part of her plan to Bob, she is invoking Bob on her own behalf, and so - would often want to wait for Bob�s side effects and outcome. The immediate - call does precisely this. When Alice passes a message to Bob on Bob�s - behalf, as when Alice is an observable and Bob is an observer, this courtesy - provided to Bob should be minimally disruptive to Alice. The send above - queues, on the queue of the observer's vat, a pending delivery of a valueChanged() - message to this observer. This delivery will happen in its own separate - turn, and cannot effect the turn from which it was sent. +
When Alice passes a message to Bob in order to subcontract + part of her plan to Bob, she is invoking Bob on her own behalf, and so + would often want to wait for Bob�s side effects and outcome. The immediate + call does precisely this. When Alice passes a message to Bob on Bob�s + behalf, as when Alice is an observable and Bob is an observer, this courtesy + provided to Bob should be minimally disruptive to Alice. The send above + queues, on the queue of the observer's vat, a pending delivery of a valueChanged() + message to this observer. This delivery will happen in its own separate + turn, and cannot affect the turn from which it was sent.
We can now understand why the other peculiar thing in the above code is harmless: To illustrate our point, we put the actual assignment after the loop notifying the observers. If we were calling the observers 1.35 +14 -15 e/doc/elib/concurrency/vat.html Index: vat.html =================================================================== RCS file: /cvs/e/doc/elib/concurrency/vat.html,v retrieving revision 1.34 retrieving revision 1.35 diff -u -r1.34 -r1.35 --- vat.html 2001/05/05 23:47:00 1.34 +++ vat.html 2001/05/09 05:00:41 1.35 @@ -101,12 +101,12 @@ a NEAR (green) reference to a copy of this 3 in his own Vat.

-
Each Vat executes concurrently with all other Vats, but - there is no concurrent execution within a Vat. In this sense, a Vat is - vaguely like a traditional OS process -- it bundles together of a single - thread of control and an address space of synchronously accessible data, - and so avoids the need for bug-prone fine-grained locking on this data. - Unlike a traditional OS process, a Vat�s thread is necessarily a non-blocking +
Each Vat executes concurrently with all other Vats, but + there is no concurrent execution within a Vat. In this sense, a Vat is + vaguely like a traditional OS process -- it bundles together a single + thread of control and an address space of synchronously accessible data, + and so avoids the need for bug-prone fine-grained locking on this data. + Unlike a traditional OS process, a Vat�s thread is necessarily a non-blocking event loop servicing a queue of pending deliveries.

Each pending delivery is a pair of a message and a recipient to whom it should be delivered. Each time around the loop, @@ -119,15 +119,14 @@
Game Turns as MicroTransactions explains the strong atomicity properties provided by E, simply, and without explicit locking or mutual exclusion constructs.
- Within a Vat we have a mostly-traditional world of sequential - call-return object programming, which we call Local-E. Between Vats we - only have asynchronous non-blocking message sending: the stubby blue arrow - above is a message transmitted between Vats (whose security provided by - E�s cryptographic implementation of distributed capabilities). When received - by the recipient�s hosting Vat, it will be queued on this Vat�s queue - as a pending delivery of this message to this recipient, to be processes - in its own turn. - + + Within a Vat we have a mostly-traditional world of sequential call-return + object programming, which we call Local-E. Between Vats we only have asynchronous + non-blocking message sending: the stubby blue arrow above is a message transmitted + between Vats (whose security is provided by E�s cryptographic implementation + of distributed capabilities). When received by the recipient�s hosting Vat, + it will be queued on this Vat�s queue as a pending delivery of this message + to this recipient, to be processed in its own turn. 1.7 +1 -1 e/doc/elib/distrib/obj-passing.html Index: obj-passing.html =================================================================== RCS file: /cvs/e/doc/elib/distrib/obj-passing.html,v retrieving revision 1.6 retrieving revision 1.7 diff -u -r1.6 -r1.7 --- obj-passing.html 2001/05/07 08:29:25 1.6 +++ obj-passing.html 2001/05/09 05:00:42 1.7 @@ -57,7 +57,7 @@
PassByConstruction

When a PassByConstruction object is passed between vats, it causes an object to be constructed in the remote vat as its remote presence. - PassByConstruction objects are shown as rectangles in our extended Grannovetter + PassByConstruction objects are shown as rectangles in our extended Granovetter notation.

These presences taken together are the PassByConstruction object as a whole, and the original object is simply the originating presence. From markm@eros.cs.jhu.edu Wed May 9 16:46:29 2001 Received: from mail.eros-os.org (IDENT:root@EROS.CIS.UPENN.EDU [158.130.6.119]) by eros.cs.jhu.edu (8.11.0/8.11.0) with ESMTP id f49KkTK04065 for ; Wed, 9 May 2001 16:46:29 -0400 Received: from eros.cs.jhu.edu (IDENT:root@eros.cs.jhu.edu [128.220.223.245]) by mail.eros-os.org (8.9.3/8.9.3) with ESMTP id QAA00737 for ; Wed, 9 May 2001 16:36:36 -0400 From: markm@eros.cs.jhu.edu Received: (from markm@localhost) by eros.cs.jhu.edu (8.11.0/8.11.0) id f49KkT604060 for e-cvs@eros-os.org; Wed, 9 May 2001 16:46:29 -0400 Date: Wed, 9 May 2001 16:46:29 -0400 Message-Id: <200105092046.f49KkT604060@eros.cs.jhu.edu> To: e-cvs@eros-os.org Subject: [e-cvs] cvs commit: e/doc/elib/equality same-ref.html Sender: e-cvs-admin@mail.eros-os.org Errors-To: e-cvs-admin@mail.eros-os.org X-BeenThere: e-cvs@mail.eros-os.org X-Mailman-Version: 2.0beta5 Precedence: bulk List-Id: markm 01/05/09 16:46:29 Modified: doc/elib/concurrency partial-order.html doc/elib/distrib/captp WormholeOp.html doc/elib/equality same-ref.html Log: a start on wormhole documentation Revision Changes Path 1.11 +1 -1 e/doc/elib/concurrency/partial-order.html Index: partial-order.html =================================================================== RCS file: /cvs/e/doc/elib/concurrency/partial-order.html,v retrieving revision 1.10 retrieving revision 1.11 diff -u -r1.10 -r1.11 --- partial-order.html 2001/05/09 05:00:41 1.10 +++ partial-order.html 2001/05/09 20:46:29 1.11 @@ -47,7 +47,7 @@
-
Two Party Reference:
+
Two Party On-a-Reference:
Full Order

Among messages successively sent on a single reference (ie, using the eventual send operator "<-"), E guarantees 1.2 +159 -6 e/doc/elib/distrib/captp/WormholeOp.html Index: WormholeOp.html =================================================================== RCS file: /cvs/e/doc/elib/distrib/captp/WormholeOp.html,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 --- WormholeOp.html 2001/05/07 09:24:44 1.1 +++ WormholeOp.html 2001/05/09 20:46:29 1.2 @@ -40,7 +40,7 @@ -
CapTP +
CapTP Ops:
WormholeOp @@ -63,11 +63,164 @@
If dest is the receiving vat, then it should try sending this packets data to itself as encrypted VatTP communications originating with source, processing sequence info so that - redundant packets data are simply ignored. Otherwise, if it currently - has a live connection to dest, or if it forms one while still - connected to the requesting vat, then it should wormhole these bytes towards - dest before allowing any further causality to flow from the - requesting vat through the receiving vat to dest. + redundant packets data are simply ignored. The receiving vat should process + this data ahead of processing further requests from the sending vat. +
If dest is not the receiving vat,, and if it + currently has a live connection to dest or if it forms one + while still connected to the requesting vat, then it should wormhole these + bytes towards dest before allowing any further causality + to flow from the requesting vat through the receiving vat to dest. + Otherwise is can discard this data. +
The Conflict Solved by WormholeOp
+
Without the WormholeOp, there are a set of requirements in the E semantics + that are individually quite sensible and compelling, but that jointly + seem to be impossible:
+
+
+
+
Partial + ordering: In a 3-vat Granovetter introduction, that the forked + reference sent to Bob gives Bob access only to post-X Carol, only + enabling messages from Bob to arrive at Carol after X is delivered. + (Even without the WormholeOp, the current implementations of E meet + this requirement.)
+
+
+
Allow services with Near arguments. In order to allow services + like the MintMaker + to be correct when written this simply, we allow it to require its + arguments, such as the src argument of the deposit message, to be + Near. Of course, this requirement can only be satisfied when the argument + Purse is in the same vat as the receiving Purse, but that is the case + here for any valid argument Purse, so no problem. Further, remote + clients need to be able to ensure that the argument as delivered is + Near, even though the argument as sent cannot be. For this we adopt + the argument passing + rule "Going + Home" that says a Far reference (a Resolved remote reference) + sent as an argument in a message sent to the designated object's hosting + vat arrives as a Near reference.
+
In the absence of this requirement, since clients could not ensure + that arguments arrive Near, the remotely invokable interfaces of the + MintMaker would always have to deal with the possibility of Eventual + arguments. It could wait on these arguments, and put the previous + method body in a when/catch clause, but it's worse than that. In a + deposit followed by a withdraw, the withdraw should not fail for insufficient + funds if the deposit would have provided these funds, just because + the deposit hasn't been scheduled yet. This would necessitate rather + complex postponement logic in the MintMaker. But much of the goal + of E is to enable simple secure distributed services to be coded simply. + Therefore, this requirement seems necessary. (Even without the WormholeOp, + the current implementations of E meet this requirement.)
+
+
+
Preserve passability. A PassByCopy object that contains only + passable parts should be passable by copy between vats. The problem + here is a hashtable-based PassByCopy collection, T, (whether the current + EMap or the anticipated + Hydro-based + replacement) that has as one of it's keys a PassByProxy object, let's + say Carol in VatC. If T is passed to Alice in VatA, everything's cool, + and it arrives with a Far reference to Carol as its key. However, + if Alice were to further pass this to Bob in VatB, then, in order + for T to still be operational and the moment of arrival, this key + would have to arrive as a Settled remote reference to Carol, which + is to say, a Far reference. (For reasons explained below, E won't + do this until the WormholeOp is implemented. Instead, in current E + implementations, the reference to Carol will arrive as an Unresolved + remote reference (a RemoteVow), and therefore T will fail to unserialize. + This is the Lost + Resolution bug.)
+
+
+
The conflict arises when, in the Preserve Passability scenario, Alice + had sent messages (like X) to Carol that hadn't yet arrived in Carol's + vat when she sends T to Bob. The reference to Carol that Bob gets in T + must be "behind" X, which would seem to make it different than + other Resolved references Bob might have to Carol. However, since this + new references is Resolved as well, if Bob includes it as an argument + in a message to Carol's vat, it must arrive as a Near reference to Carol. + However, because Near references give immediate access, it may not arrive + as a Near references until all prior messages, such as X from Alice, have + drained out.
+
Three Plausible Engineering Solutions
+
+
+
+
Introduce a new kind of reference into our reference taxonomy: + The Indirect reference is a Settled but not Resolved remote + reference to a PassByProxy object. Dean, MarcS, and I (MarkM) actually + worked out the semantics for this, and earlier in the cvs history + you'll find some corresponding taxonomy diagrams and explanations, + but it just made E too hard to explain.
+
+
+
Block all further communications from VatB to VatC until all communications + from VatA to VatC prior to the introduction have drained out, or + until the VatA/VatC timeout period expires, killing the connection. + This could repeatedly impose a huge cost on VatB for the sake of + only a few objects in VatB. While E avoids making any claims about + resistance to denial of service attack, this would be too aggregious + a vulnerability to such an attack.
+
+
+
When VatA introduces VatB to Carol, she first wormholes the unacknowledged + portion of her outgoing VatA-to-VatC VatTP stream through VatB for + delivery to VatC. VatB then wormholes it towards VatC before acting + on further messages from VatA. VatTP already encrypts this traffic + for secrecy, integrity, authenticity, and protection against replay + attacks, so that this communications can be carried by untrusted + intermediaries. VatB is just another untristed intermediary. If + VatC gets the next communication in the VatA/VatC stream via a wormhole + from VatB, that's fine. It doesn't matter where the bits came from, + as long as they pass all the crypto tests. When these same bits + come in redundantly through another path, they may be safely ignored.
+
+
+
As you've no doubt guessed, we're planning to pursue path #3.
+
Wormhole Introduction Scenario
+
The Wormhole introduction is only needed when VatA sends to VatB a Far + reference for an object on VatC. It isn't needed for any 2-vat introductions, + and it isn't needed when the reference passed from VatA to VatB is Unresolved, + such as a RemoveVow whose Resolver is on VatC, or is travelling to VatC.
+
*** To be written, but involves these CapTP steps:
+
VatA to VatC:
+
+
def vine := NonceLocator <- provideFor(farCarol, + vatBID, + nonce, + carolSwissHash)
+
+
VatA to VatB:
+
+
+WormholeOp(/*unacknowledged encrypted A-to-C traffic*/, + vatAID, + vatCID) +/*some message containing: */ +... LookupDesc(VatCSearchPath, + VatCID, + nonce, + carolSwissHash, + vine) ...
+
+
VatB to VatC:
+
+
WormholeOp(/*unacknowledged encrypted A-to-C traffic*/, + vatAID, + vatCID) +def carolPromise := NonceLocator <- acceptFrom(vatAID, + nonce, + carolSwissHash, + vine)
+ /* carolPromise, a RemoteVow, is then magically turned into farCarol, + a Far reference. */
+
So, if VatA and VatB are cooperative, they are both assured that the + needed provideFor "from" VatA will be processed + by VatC before VatC sees the corresponding acceptFrom from + VatB. If either is uncooperative, they cannot cause damage beyond that + accounted for by the object-level semantics. Because the data takes redundant + paths, neither side will get stuck waiting on the other to timeout.
1.3 +57 -44 e/doc/elib/equality/same-ref.html Index: same-ref.html =================================================================== RCS file: /cvs/e/doc/elib/equality/same-ref.html,v retrieving revision 1.2 retrieving revision 1.3 diff -u -r1.2 -r1.3 --- same-ref.html 2001/05/07 09:32:55 1.2 +++ same-ref.html 2001/05/09 20:46:29 1.3 @@ -83,8 +83,8 @@ but now organized for purposes of reasoning about distributed reference sameness.

-
Vat Independent Semantics
-
Argument Passing Rules
+
Argument Passing Rules
+
Vat Independent Semantics

Implicit in the following rules are that all transformations of arguments and return results must be consistent with both capability rules and E's partial @@ -92,45 +92,58 @@

-
In any immediate message - pass (ie, synchronous: call, success, failure, escape) the arguments - transmitted are the arguments received, and the return results passed - are the return results received.
+
Calls don't fork: In any immediate + message pass (ie, synchronous: + call, success, failure, escape) the arguments transmitted are the + arguments received, and the return results passed are the return results + received.

-
In an eventual-send, the return result always starts as a Promise - for the outcome.
+
Sends make Promises: In + an eventual-send, the return result always starts as a Promise for + the outcome.

-
In any message pass, whether immediate or eventual (ie, asynchronous: - sendOnly, pipelined-send), transmitted Settled arguments are always - received as Settled arguments.
-
-
-
In any message pass, transmitted Resolved arguments are always received - as Resolved (but due to the Lost +
Args stay Resolved: In any + message pass, transmitted Resolved arguments are always received as + Resolved (but due to the Lost Resolution bug, in current E implementations it may be received as a Promise instead).

+
+
Args stay Settled: In any + message pass, whether immediate or eventual (ie, asynchronous: sendOnly, + pipelined-send), transmitted Settled arguments are always received + as Settled arguments.
+

-
In any message pass, transmitted Near references to PassByCopy objects +
PassByCopy args stay Near: + In any message pass, transmitted Near references to PassByCopy objects are always received as Near references to the identical objects. If the message is sent between vats, this means the PassByCopy arguments must be copied by the time the message is delivered.
-
-
-
Putting the above rules together, PassByCopy hashtables can be successfully - passed by copy, because the hashtable insists its keys must be Settled, - and so these keys will also arrive as Settled and designating the - same objects.
-
-
-
In any message pass, transmitted broken references are always received - as broken.
+
Putting the above two rules together, PassByCopy hashtables can be + successfully passed by copy, because the hashtable insists its keys + must be Settled, and so these keys will also arrive as Settled and + designating the same objects.
+
+
+
PBC args stay Near: In any message + pass, transmitted Near references to a PassByConstruction object are + always received as Near references to a Presence of the same + object. If the message is sent between vats, this means the remote + presence of the PassByConstruction argument must be constructed by + the time the message is delivered. (The above PassByCopy rule can + be seen as a special case of this one.)
+
+
+
Once Broken always Broken: In + any message pass, transmitted Broken references are always received + as Broken.

-
Vat-based Rules
+
Vat-based Rules

But first some terminology. To a settled reference, the vat hosting the object it designates is "home". If the reference is in the same vat as the object it designates, it is "at home". A Near @@ -142,20 +155,20 @@

-
Leaving home: (When Carol lives in Alice's vat.) A transmitted - Near reference to a PassByProxy object will arrive as a Far reference - to the same object.
+
Leaving home: (When Carol lives + in Alice's vat.) A transmitted Near reference to a PassByProxy object + will arrive as a Far reference to the same object.

-
Going home: (When Carol lives in Bob's vat.) A Far reference - transmitted as an argument in a message sent towards the reference's - home arrives as a Near reference.
-
-
Travelling: (When Alice, Bob, and Carol are in three separate - vats.) A Far references transmitted as an argument to a third vat must - be received as a Far reference (but due to the - Lost Resolution bug, in current E implementations - it will arrive as a Promise instead).
+
Going home: (When Carol lives in + Bob's vat.) A Far reference transmitted as an argument in a message + sent towards the reference's home arrives as a Near reference.
+ +
Travelling: (When Alice, Bob, and + Carol are in three separate vats.) A Far references transmitted as an + argument to a third vat must be received as a Far reference (but + due to the Lost Resolution bug, in current + E implementations it will arrive as a Promise instead).

Known Implementation Bug:
@@ -166,11 +179,11 @@ Carol that will eventually resolve into a Far reference to Carol. As a result, if Alice sends Bob a hashtable containing the reference to Carol as a key, the hashtable will fail to unserialize in Bob's vat. Although - we know how to fix this problem, we may not fix it quickly due to other - matters being higher priority. If you run into this and need it fixed - now, please let us know so we can consider reprioritizing it, and - can help you figure out how to work around this problem in the meantime. -
+ we know how to fix this problem, + we may not fix it quickly due to other matters being higher priority. + If you run into this and need it fixed now, please let us know + so we can consider reprioritizing it, and can help you figure out how + to work around this problem in the meantime.

whenResolved and when/catch

*** to be written
From markm@eros.cs.jhu.edu Wed May 9 19:13:16 2001 Received: from mail.eros-os.org (IDENT:root@EROS.CIS.UPENN.EDU [158.130.6.119]) by eros.cs.jhu.edu (8.11.0/8.11.0) with ESMTP id f49NDFK05479 for ; Wed, 9 May 2001 19:13:15 -0400 Received: from eros.cs.jhu.edu (IDENT:root@eros.cs.jhu.edu [128.220.223.245]) by mail.eros-os.org (8.9.3/8.9.3) with ESMTP id TAA00966 for ; Wed, 9 May 2001 19:03:20 -0400 From: markm@eros.cs.jhu.edu Received: (from markm@localhost) by eros.cs.jhu.edu (8.11.0/8.11.0) id f49NDEI05474 for e-cvs@eros-os.org; Wed, 9 May 2001 19:13:14 -0400 Date: Wed, 9 May 2001 19:13:14 -0400 Message-Id: <200105092313.f49NDEI05474@eros.cs.jhu.edu> To: e-cvs@eros-os.org Subject: [e-cvs] cvs commit: e/doc/elib/equality/images obj-settling.gif obj-settling.sdr ref-settling.gif ref-settling.sdr Sender: e-cvs-admin@mail.eros-os.org Errors-To: e-cvs-admin@mail.eros-os.org X-BeenThere: e-cvs@mail.eros-os.org X-Mailman-Version: 2.0beta5 Precedence: bulk List-Id: markm 01/05/09 19:13:14 Modified: doc/elib/equality same-object.html same-ref.html doc/elib/equality/images obj-settling.gif obj-settling.sdr ref-settling.gif ref-settling.sdr Log: added PassByCopy to some diagrams Revision Changes Path 1.2 +1 -1 e/doc/elib/equality/same-object.html Index: same-object.html =================================================================== RCS file: /cvs/e/doc/elib/equality/same-object.html,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 --- same-object.html 2001/05/07 08:29:26 1.1 +++ same-object.html 2001/05/09 23:13:14 1.2 @@ -54,7 +54,7 @@ Mechanics page, illustrate the possible transitions between the states of an object, organized for purposes of reasoning about equality.

-
+

PassByProxy Objects

*** To be written

PassByCopy Objects
1.4 +1 -1 e/doc/elib/equality/same-ref.html Index: same-ref.html =================================================================== RCS file: /cvs/e/doc/elib/equality/same-ref.html,v retrieving revision 1.3 retrieving revision 1.4 diff -u -r1.3 -r1.4 --- same-ref.html 2001/05/09 20:46:29 1.3 +++ same-ref.html 2001/05/09 23:13:14 1.4 @@ -82,7 +82,7 @@ illustrates the possible transitions between the states of a Live reference, but now organized for purposes of reasoning about distributed reference sameness.
-
+

Argument Passing Rules

Vat Independent Semantics

Implicit in the following rules are that all transformations of arguments 1.2 +24 -12 e/doc/elib/equality/images/obj-settling.gif Index: obj-settling.gif =================================================================== RCS file: /cvs/e/doc/elib/equality/images/obj-settling.gif,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 Binary files /tmp/cvsbybRkw and /tmp/cvsOZmtsS differ 1.2 +19 -12 e/doc/elib/equality/images/obj-settling.sdr Index: obj-settling.sdr =================================================================== RCS file: /cvs/e/doc/elib/equality/images/obj-settling.sdr,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 Binary files /tmp/cvsGCAmex and /tmp/cvsI1E0jU differ 1.2 +77 -65 e/doc/elib/equality/images/ref-settling.gif Index: ref-settling.gif =================================================================== RCS file: /cvs/e/doc/elib/equality/images/ref-settling.gif,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 Binary files /tmp/cvsThiV7x and /tmp/cvsOZZEZV differ 1.2 +132 -132 e/doc/elib/equality/images/ref-settling.sdr Index: ref-settling.sdr =================================================================== RCS file: /cvs/e/doc/elib/equality/images/ref-settling.sdr,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 Binary files /tmp/cvsI2tJ0A and /tmp/cvsCMxjH1 differ From markm@eros.cs.jhu.edu Wed May 9 23:19:22 2001 Received: from mail.eros-os.org (IDENT:root@EROS.CIS.UPENN.EDU [158.130.6.119]) by eros.cs.jhu.edu (8.11.0/8.11.0) with ESMTP id f4A3JMK06625 for ; Wed, 9 May 2001 23:19:22 -0400 Received: from eros.cs.jhu.edu (IDENT:root@eros.cs.jhu.edu [128.220.223.245]) by mail.eros-os.org (8.9.3/8.9.3) with ESMTP id XAA00876 for ; Wed, 9 May 2001 23:09:26 -0400 From: markm@eros.cs.jhu.edu Received: (from markm@localhost) by eros.cs.jhu.edu (8.11.0/8.11.0) id f4A3JLv06618 for e-cvs@eros-os.org; Wed, 9 May 2001 23:19:21 -0400 Date: Wed, 9 May 2001 23:19:21 -0400 Message-Id: <200105100319.f4A3JLv06618@eros.cs.jhu.edu> To: e-cvs@eros-os.org Subject: [e-cvs] cvs commit: e/src/jsrc/org/erights/e/elib/ref RemoteVow.java FarRef.java Proxy.java ProxyResolver.java Sender: e-cvs-admin@mail.eros-os.org Errors-To: e-cvs-admin@mail.eros-os.org X-BeenThere: e-cvs@mail.eros-os.org X-Mailman-Version: 2.0beta5 Precedence: bulk List-Id: markm 01/05/09 23:19:21 Modified: src Makefile src/jsrc/net/captp/jcomm LookupDesc.java src/jsrc/org/erights/e/elib/ref FarRef.java Proxy.java ProxyResolver.java Added: src/jsrc/org/erights/e/elib/ref RemoteVow.java Log: Cleaned up Proxy vs FarRef vs RemoteVow in preparation for enabling FarRefs to be questions (in the QuestionsTable). Revision Changes Path 1.99 +2 -2 e/src/Makefile Index: Makefile =================================================================== RCS file: /cvs/e/src/Makefile,v retrieving revision 1.98 retrieving revision 1.99 diff -u -r1.98 -r1.99 --- Makefile 2001/04/13 08:08:33 1.98 +++ Makefile 2001/05/10 03:19:21 1.99 @@ -93,9 +93,9 @@ release: - cvs rtag -R -F $(RELEASE)_$(TAGVER) e + cvs rtag -R -F $(RELEASE)_$(TAGVER) e/src ifneq "$(RELEASE)" "working" - cvs rtag -R -F current_release e + cvs rtag -R -F current_release e/src endif 1.3 +9 -9 e/src/jsrc/net/captp/jcomm/LookupDesc.java Index: LookupDesc.java =================================================================== RCS file: /cvs/e/src/jsrc/net/captp/jcomm/LookupDesc.java,v retrieving revision 1.2 retrieving revision 1.3 diff -u -r1.2 -r1.3 --- LookupDesc.java 2001/05/03 18:26:23 1.2 +++ LookupDesc.java 2001/05/10 03:19:21 1.3 @@ -32,7 +32,7 @@ /*package*/ class LookupDesc implements ObjectRefDesc { private ConstList mySearchPath; - private String myVatID; + private String myHostID; private BigInteger myNonce; private BigInteger myOptSwissHash; private Object myOptFarVine; @@ -41,13 +41,13 @@ * Constructor. */ /*package*/ LookupDesc(ConstList searchPath, - String vatID, + String hostID, BigInteger nonce, BigInteger optSwissHash, Object optFarVine) { mySearchPath = searchPath; - myVatID = vatID; + myHostID = hostID; myNonce = nonce; myOptSwissHash = optSwissHash; myOptFarVine = optFarVine; @@ -66,7 +66,7 @@ optVine = new Vine(myOptFarVine); } return conn.getLookup(mySearchPath, - myVatID, + myHostID, myNonce, myOptSwissHash, optVine); @@ -76,10 +76,10 @@ * */ public String toString() { - return "LookupDesc(" + mySearchPath + ",\n " - + myVatID.substring(0,4) + ",\n " - + myNonce + ",\n " - + myOptSwissHash + ",\n " - + myOptFarVine + ")"; + return "LookupDesc(" + mySearchPath + ",\n " + + myHostID.substring(0,4) + ",\n " + + myNonce + ",\n " + + myOptSwissHash + ",\n " + + myOptFarVine + ")"; } } 1.11 +16 -102 e/src/jsrc/org/erights/e/elib/ref/FarRef.java Index: FarRef.java =================================================================== RCS file: /cvs/e/src/jsrc/org/erights/e/elib/ref/FarRef.java,v retrieving revision 1.10 retrieving revision 1.11 diff -u -r1.10 -r1.11 --- FarRef.java 2001/05/03 18:26:23 1.10 +++ FarRef.java 2001/05/10 03:19:21 1.11 @@ -22,12 +22,8 @@ import org.erights.e.elib.prim.E; /** - * A FarRef is intended to be a Ref to a particular PassByProxy object in a - * remote Vat. However, it delegates most of its behavior to its ProxyHandler, - * which may be untrusted code. Therefore, the FarRef itself has - * responsibility for adhering to the Ref contract despite arbitrary behavior - * by its handler. This is a step toward reimplementing CapTP in - * the E language.
+ * A FarRef is a Proxy intended to be a Resolved Ref to a particular + * PassByProxy object in a remote Vat.
* * A FarRef starts out EVENTUAL but may become BROKEN. However, it continues * to have whatever settled identity it was born with, and so may be used as @@ -35,41 +31,28 @@ * connection with its handler. A FarRef is an HONORARY Selfless object * (since it's not transparent -- it encapsulates its myIdentity). * - * A Handler should create and point at its FarRef only using ProxyResolver, so - * it can find out when the FarRef has been GCed, be able to break it, and be - * able to transparently revive it. - * * @author Mark S. Miller */ -/*package*/ class FarRef extends Ref /*XXX instead: extends Proxy*/ { +/*package*/ class FarRef extends Proxy { /** - * My settled identity is derived from this settled object. + * My settled identity is according to .equals() on this settled object. */ /*package*/ final Object myIdentity; /** - * While I'm EVENTUAL, I delegate many of my decisions to my handler. - */ - private ProxyHandler myOptHandler; - - /** - * Once I'm BROKEN, this is my reso

	Capabilities	SPKI	Example Purse-Money
+

shareable vs. exclusive	Alice shares with Bob her right to access Carol.	Issuer shares with Subject the authorization +	Issuer shares with Subject the authorization to the Resource.	When Bob deposits the payment from Alice, he knows +	When Bob deposits the payment from Alice, he knows he has excluded anyone else from using that money.
- In the capability case, if Alice drops the capability after passing - it to Bob, Bob happens to have exclusive access to Carol, but this - isn't an exclusive right since Bob is unable to know that he is +
+ In the capability case, if Alice drops the capability after passing + it to Bob, Bob happens to have exclusive access to Carol, but this + isn't an exclusive right since Bob is unable to know that he is the only one who has it. - In the real world, information is sharable and physical objects are - exclusive. + In the real world, information is sharable and physical objects are + exclusive.
specific vs. fungible	A capability designates a specific object.	Authorization can be for specific objects, or for some +	Authorization can be for specific objects, or for some number of units.	Money is fungible, since we care only about +	Money is fungible, since we care only about quantity, not individual bills.
In the real world, real estate is specific and barrels - of (a given grade of) oil are fungible. Peaches in the supermarket - are specific -- you buy the ones you pick out. Peaches ordered over - Peapod are fungible -- you order only by quantity. +
In the real world, real estate is specific and barrels + of (a given grade of) oil are fungible. Peaches in the supermarket + are specific -- you buy the ones you pick out. Peaches ordered over + Peapod are fungible -- you order only by quantity.
opaque vs. assayable	A capability is opaque, since from the capability - alone all you can determine is what the designated object alleges +	A capability is opaque, since from the capability + alone all you can determine is what the designated object alleges about itself.	An authorization can be read as well as used. Reading +	An authorization can be read as well as used. Reading it may suffice to assay what value it would provide.	Bob can reliably assay the amount in an alleged +	Bob can reliably assay the amount in an alleged purse only by transferring into a purse he trusts.
Assayability is needed for trade, since you must be - able to determine what you would be getting before deciding - to purchase. However, exclusive rights can only be reliably assayed - by actually obtaining exclusive access to them, since otherwise, after - you've assayed them, someone else may gain the exclusive, cutting - you out. Trade of exclusives may therefor require a trusted third - party who can hold them in escrow. +
Assayability is needed for trade, since you must be + able to determine what you would be getting before deciding + to purchase. However, exclusive rights can only be reliably assayed + by actually obtaining exclusive access to them, since otherwise, after + you've assayed them, someone else may gain the exclusive, cutting + you out. Trade of exclusives may therefor require a trusted third + party who can hold them in escrow.
exercisable vs. symbolic	A capability has value only because it can be exercised, +	A capability has value only because it can be exercised, by sending a message to the object it designates.	An authorization may be for either or both.	As with fiat money, our example money is purely symbolic, +	As with fiat money, our example money is purely symbolic, since one can't do anything with it other than transfer it further.
There are many goods that are both exercisable and have - symbolic value. For example, gold is commonly used as a pure symbol - of value, but gold is also used to create electronic hardware and - decorative jewelry. +
There are many goods that are both exercisable and have + symbolic value. For example, gold is commonly used as a pure symbol + of value, but gold is also used to create electronic hardware and + decorative jewelry.

+
timer after(duration, thunk)	This tells the timer to call `thunk` after `duration` +	This tells the timer to call `thunk` after `duration` time has passed. (A thunk is a no-argument procedure, such as `cancel()`.)
+
timer now()	What's the current time?
+
timer date(time)

From Stuff to Financial Instruments and Smart Contracts

A Taxonomy of Kinds of Rights

Options

An Options Smart Contract

Composable Security, Readable Contracts

Taxonomy of Messaging Primitives

i) The Immediate Call

ii) Synchronous Outcome of Stack-Frame Completion

iii) The Eventual Send

Turning Control-Flow into Semi-Data-Flow

Turning Semi-Data-Flow back into Control-Flow

when-catch

whenResolved & whenMoreResolved

PassByConstruction

Two Party Reference: +

Two Party On-a-Reference: Full Order

The Conflict Solved by WormholeOp

Three Plausible Engineering Solutions

Wormhole Introduction Scenario

Vat Independent Semantics

Argument Passing Rules

Argument Passing Rules

Vat Independent Semantics

Vat-based Rules

Vat-based Rules

whenResolved and when/catch

PassByProxy Objects

PassByCopy Objects

Argument Passing Rules

Vat Independent Semantics

Two Party Reference:
+

Two Party On-a-Reference:
Full Order