Hi: Dominic： Thank you very much for your thoughtful comments. I'll just address the first one. For the rest, please give me some time.

ad "New EPR or re-write the current WS-AG document?" during the renegotiation the agreement is in some kind of intermediate change (i.e. it might be in a proposed new status that is not yet accepted by the other party), don't we need a new EPR for that?

The reason that I wanted to re-write the current WS-AG rather than a new EPR was that one could never know who might be using the old EPR. In a complex scenario like the one I mentioned in Business Grid Computing case or some broker case, old EPR might be propagated to other parties who would be using it. So I thought that it would not be realistic to assure that the NEW EPR would be propagated to all the bodies who might be referring to the old EPR. On the other hand, re-writing the current WS-AG document kept by the Agreement Responder does cause a serious race condition when the AR is the requestor for modifying the Agreement. (ie. it must be re-written only after the AI says he agrees, but when?)

What would the ResourceProperties (e.g. the SDTs or GTs) look like in the intermediate state? (DB, 2007/08/22) I am assuming that the service (under the old SLA) is still being provided even while the renegotiation is going on. (If the service is stopped, then we don't need renegotiation. We just terminate the old agreement and create a new agreement)

As for the rest of your comments, essentially I agree with you. The only problemis that some of them seem to be very difficult to address :-( In any case, please give me some time as I can only do this work sporadically. Best regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

-----Original Message----- From: Dominic Battre [mailto:mailinglists@battre.de] Sent: Thursday, August 23, 2007 5:18 AM To: Toshiyuki Nakata Cc: 'GRAAP-WG' Subject: Re: [GRAAP-WG] Modification to the wiki Page on Renegotiating an established Agreement

Hi Toshi,

I did some brainstorming and added some random comments/wishes/ideas. Please have a look whether anything could be useful for the further proceeding. I don't know how much you have discussed and discarded before. Please feel free to ask me, in case my comments are confusing.

Best regards,

Dominic

Toshiyuki Nakata wrote:

...

Hi: I've put up some more things to ponder on the re-negotiation Wiki Page

https://forge.gridforum.org/sf/wiki/do/viewPage/projects.graap -wg/wiki/ReNeg

...

otiationWishlists?_message=1187773027531 esp. No.7 is rather a tough one.

Comments welcome.

Best Regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

-------------------------------------------------------------- ----------

...

-- graap-wg mailing list graap-wg@ogf.org http://www.ogf.org/mailman/listinfo/graap-wg

HI Dominic: Thanx for the response.

For that reason I mentioned the "superseded by" information that could be added to the context. A third party might need to check whether the SLA is superseded by another SLA periodically. Kind of ugly...

I see. I had been wondering what you meant by "superseded by".. It might be necessary to have a Notification sent to all the bodies using the old EPR...

oh, does this imply that you want a simple two way communication?

AI ------ 1. please change SLA like this ------> AR 2. AR changes SLA <------ 3. confirms change ------------------

or

AI ------ 1. please change SLA like this ------> AR 2. AR rejects change <------------- 3. exception ------------------

for AI to AR yes, for AR to AI this becomes a bit more complex.. (Please cf. the ppt attached in the Wiki page)

AI ------ 1. please change SLA like this ------> AR 2. AR decides that it can change SLA 3. AR calculates price of modification <----------- 4. new offer ------------------ 5. AI decides whether change is worth the price --------- 6. confirmation/rejection --------->

I agree that this is more beautiful. OTOH I think that this raises the issue related to two phase commit protocol that had been discussed for a long time and in a heated manner by quite a number of people (before my time actually) and finally got rejected in the original WS-Agreement protocol. I am a bit afraid of waking the sleeping monster, but I welcome people's comments.. Best regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

-----Original Message----- From: Dominic Battre [mailto:mailinglists@battre.de] Sent: Thursday, August 23, 2007 5:25 PM To: Toshiyuki Nakata Cc: 'GRAAP-WG' Subject: Re: [GRAAP-WG] Modification to the wiki Page on Renegotiating an established Agreement

Hi Toshi,

(I am resending this mail because I used the wrong email address and it bounced)

...

Hi: Dominic： Thank you very much for your thoughtful comments. I'll just address the first one. For the rest, please give me some time.

...

ad "New EPR or re-write the current WS-AG document?" during the renegotiation the agreement is in some kind of intermediate change (i.e. it might be in a proposed new status that is not yet accepted by the other party), don't we need a new EPR for that?

The reason that I wanted to re-write the current WS-AG rather than a new EPR was that one could never know who might be using the old EPR. In a complex scenario like the one I mentioned in Business Grid Computing case or some broker case, old EPR might be propagated to other parties who would be using it.

For that reason I mentioned the "superseded by" information that could be added to the context. A third party might need to check whether the SLA is superseded by another SLA periodically. Kind of ugly...

...

So I thought that it would not be realistic to assure that the NEW EPR would be propagated to all the bodies who might be referring to the old EPR.

On the other hand, re-writing the current WS-AG document kept by the Agreement Responder does cause a serious race condition when the AR is the requestor for modifying the Agreement. (ie. it must be re-written only after the AI says he agrees, but when?)

oh, does this imply that you want a simple two way communication?

AI ------ 1. please change SLA like this ------> AR 2. AR changes SLA <------ 3. confirms change ------------------

or

AI ------ 1. please change SLA like this ------> AR 2. AR rejects change <------------- 3. exception ------------------

I am not sure whether this is sufficient. Suppose that the SLA carries a price tag that needs to be calculated by the AR. I would like to see some kind of two phase protocol...

AI ------ 1. please change SLA like this ------> AR 2. AR decides that it can change SLA 3. AR calculates price of modification <----------- 4. new offer ------------------ 5. AI decides whether change is worth the price --------- 6. confirmation/rejection --------->

In my opinion, for negotiation and for renegotiation we need this kind of request-offer-commit protocol. So it is no easier if the AR initiates the renegotiation than if the AI initiates the renegotiation. But I think that we see the same issue there: "What do the resource properties of the agreement look like if an offer has been sent but not confirmed?"

I agree that creating a new agreement EPR is not very beautiful. Maybe one could create such an EPR for negotiation until a party commits. At that time Context, SDTs and GTs are copied to the old agreement.

Best regards,

Dominic

Hi Dominic:

So, yes, there are problems but it looks like a lot of people want to have this extra commit message. Are there any written records on the pros and cons of having the 2PC?

I think this info. is very important. Unfortunately, I am not able to address this issue. Karl or others, please respond.. Best Regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

-----Original Message----- From: Dominic Battre [mailto:mailinglists@battre.de] Sent: Thursday, August 23, 2007 10:09 PM To: Toshiyuki Nakata Cc: 'GRAAP-WG' Subject: Re: [GRAAP-WG] Modification to the wiki Page on Renegotiating an established Agreement

Hi Toshi,

...

...

For that reason I mentioned the "superseded by" information that could be added to the context. A third party might need to check whether the SLA is superseded by another SLA periodically. Kind of ugly...

I see. I had been wondering what you meant by "superseded by".. It might be necessary to have a Notification sent to all the bodies using the old EPR...

Either that or to forward all requests transparently in the Agreement webservice. (i.e. if a message is sent to the old agreement it is automatically forwarded and answered to/by the new agreement).

In case of the notification, we have again the problem that the delay of delivering the notification means that some parties are unaware of the new state for some time.

...

...

AI ------ 1. please change SLA like this ------> AR 2. AR decides that it can change SLA 3. AR calculates price of modification <----------- 4. new offer ------------------ 5. AI decides whether change is worth the price --------- 6. confirmation/rejection --------->

I agree that this is more beautiful. OTOH I think that this raises the issue related to two phase commit protocol that had been discussed for a long time and in a heated manner by quite a number of people (before my time actually) and finally got rejected in the original WS-Agreement protocol.

I am a bit afraid of waking the sleeping monster, but I welcome people's comments..

Yes, I remember the discussion in Leeds. But on the other hand:

"A WS-AGREEMENT BASED RESOURCE NEGOTIATION FRAMEWORK FOR MOBILE AGENTS" by D.G.A. Mobach, B.J. Overeinder, and F.M.T. Brazier introduced the additional commit and argues why it is important.

Oliver's WSAG4J has a commit message in the NegotiationAgreement interface (I don't know whether it is required or whether it is implemented for some historic reasons).

Our Negotiation Manager implementation (online since a few days ago: https://cit-server.cit.tu-berlin.de/trac/negmgr/wiki) needs it.

So, yes, there are problems but it looks like a lot of people want to have this extra commit message. Are there any written records on the pros and cons of having the 2PC?

Best regards,

Dominic

Hi Michael, Thanks for these excellent references -- will be downloading and reading them. My undersstanding of the Mobach et al. paper -- and the reason the 2PC approach was chosen was to satisfy legal constraints that they were working on. Their aim was more to ensure that legally both parties were covered, more than looking into the specifics of constraints of a distributed implementation. I am copying David Mobach and Benno Overeinder. regards Omer On Fri, Aug 24, 2007 at 10:35:50AM +0200, Michael Parkin wrote:

Toshi, Dominic,

As no-one else has replied...

On 23 Aug 2007, at 15:30, Toshiyuki Nakata wrote:

...

...

So, yes, there are problems but it looks like a lot of people want to have this extra commit message. Are there any written records on the pros and cons of having the 2PC?

I think this info. is very important.

A 2PC-type protocol works well when you control everything. However, where autonomous services are involved in (possibly) different administrative domains (such as in a business environment) the cons of using the 2PC style in agreements like this are well understood, for example:

* Skeen's paper [1] on commit protocols describes why 2PC is a blocking protocol.

* Pat Helland (formally Amazon, now Microsoft) describes the 2PC protocol as the "anti-availability protocol" [2] because of the fact it can block the transaction manager (Dominic, this would be the AR in your protocol). As he says: "[2pc] is best used sparingly".

(Toshi - I also direct you to his article on "accountants don't use erasers" [3] about why agreements should not be overwritten).

* Mark McKeown also has a blog article [4] about the difficulty of distributed consensus, which is essentially what you're trying to achieve (FTA: "consensus was originally called agreement").

* If you want a lighter read the Wikipedia article [5] also discusses 2PC's blocking.

About the Mobach, et. al. paper [6] - the last three steps in Figure 2.4 are a 2PC-type protocol. When the 'DC' (from the paper) returns the 'agreement offer' to 'A' they are blocked from offering those resources to anyone else (although this is an assumption because the paper doesn't say explicitly what the 'agreement offer' actually means).

Imagine the scenario: DC returns an offer to A1 saying 'these resources for €10". Meanwhile A2, who is prepared to pay €10,000 for the same resources cannot make the agreement because DC has offered them to A1. A2 then goes and makes an agreement with another DC (e.g. another business) and A1 decides they don't want the resources and return a reject message. DC has lost €10,000 of income it could have made because of the protocol it is using.

If A1 is a proxy for a competitor of DC it could repeatedly keep asking for offers it never intends to agree to meaning DC may loose revenue...

Dominic: before I comment further on your proposed protocol what semantics are you attaching to the 'offer' message that the AR returns to the AI? Does the offer mean 'if you accept I will guarantee providing what is contained in this offer' or does it mean something else?

Michael.

[1] http://www.cs.cornell.edu/courses/cs614/2004sp/papers/Ske81.pdf [2] http://blogs.msdn.com/pathelland/archive/2007/05/20/soa-and- newton-s-universe.aspx [3] http://blogs.msdn.com/pathelland/archive/2007/06/14/accountants- don-t-use-erasers.aspx [4] http://betathoughts.blogspot.com/2007/06/brief-history-of- consensus-2pc-and.html [5] http://en.wikipedia.org/wiki/Two-phase_commit [6] www.iids.org/publications/scpe06.pdf

-- graap-wg mailing list graap-wg@ogf.org http://www.ogf.org/mailman/listinfo/graap-wg

-- http://www.cs.cf.ac.uk/User/O.F.Rana/index.html / work-fax:+44(0)29-2087-4598 work:+44(0)29-2087-5542 / other:+44(0)7956-299981 / distributed collaborative computing / room n2.14 / school of computer science / cardiff university queen's buildings / newport road / cardiff cf24 3aa / wales / uk

Hi Michael, Yes, I off course agree with your statement that all three must be taken into consideration. In practice, many implementations do not follow this line however -- but they should. I guess there is a trade off between making the protocol too complex -- so much so that no one will actually use it -- vs. making it complete -- so that it takes account of everything that is useful. But you are right. Thanks also for the additional links. Seems like I have my reading set out for this w/end. regards Omer Michael Parkin wrote:

Hi Omer,

Thanks for your reply.

On 24 Aug 2007, at 10:53, Omer F Rana wrote:

...

My undersstanding of the Mobach et al. paper -- and the reason the 2PC approach was chosen was to satisfy legal constraints that they were working on. Their aim was more to ensure that legally both parties were covered, more than looking into the specifics of constraints of a distributed implementation.

I believe that the legal, distributed computing _and_ business aspects of agreement must be considered together to design a successful contract negotiation and formation protocol - they cannot be considered separately. When all three aspects are taken into account together it is clear that 2PC-type protocols are inappropriate for cross-administrative domain negotiation because of the risk of blocking that is introduced, as I described in my previous email.

Work we have done [1] together with the School of Law at Manchester University investigates maintaining the legalities of contract negotiation and formation (including adhering to the EU's e-Commerce directive) whilst still allowing the entity supplying the resources/ services not to be blocked, thus satisfying the requirements of business. Section 4.1 of the linked paper discusses blocking.

Dean Kuo (who many of you know...[2]) and I are writing up and formally specifying the protocol we derived from this work and will be submitting this work for publication soon.

Michael.

[1] http://www2.cs.man.ac.uk/~parkinm/publications/ eChallenges_e2006_ref_235.pdf [2] http://www.cs.man.ac.uk/~dkuo/

-- graap-wg mailing list graap-wg@ogf.org http://www.ogf.org/mailman/listinfo/graap-wg

-- http://www.cs.cf.ac.uk/User/O.F.Rana/index.html / work-fax:+44(0)29-2087-4598 work:+44(0)29-2087-5542 / other:+44(0)7956-299981 / distributed collaborative computing / room n2.14 / school of computer science / cardiff university queen's buildings / newport road / cardiff cf24 3aa / wales / uk

Michael: Thank you very much for a thorough introduction of the current art. As Omer says, I'll also study some of the documents which I had not known before.. ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

-----Original Message----- From: Michael Parkin [mailto:parkinm@cs.man.ac.uk] Sent: Friday, August 24, 2007 5:36 PM To: Toshiyuki Nakata; Dominic Battre Cc: GRAAP-WG Subject: Re: [GRAAP-WG] Modification to the wiki Page on Renegotiating an established Agreement

Toshi, Dominic,

As no-one else has replied...

On 23 Aug 2007, at 15:30, Toshiyuki Nakata wrote:

...

...

So, yes, there are problems but it looks like a lot of people want to have this extra commit message. Are there any written records on the pros and cons of having the 2PC?

I think this info. is very important.

A 2PC-type protocol works well when you control everything. However, where autonomous services are involved in (possibly) different administrative domains (such as in a business environment) the cons of using the 2PC style in agreements like this are well understood, for example:

* Skeen's paper [1] on commit protocols describes why 2PC is a blocking protocol.

* Pat Helland (formally Amazon, now Microsoft) describes the 2PC protocol as the "anti-availability protocol" [2] because of the fact it can block the transaction manager (Dominic, this would be the AR in your protocol). As he says: "[2pc] is best used sparingly".

(Toshi - I also direct you to his article on "accountants don't use erasers" [3] about why agreements should not be overwritten).

* Mark McKeown also has a blog article [4] about the difficulty of distributed consensus, which is essentially what you're trying to achieve (FTA: "consensus was originally called agreement").

* If you want a lighter read the Wikipedia article [5] also discusses 2PC's blocking.

About the Mobach, et. al. paper [6] - the last three steps in Figure 2.4 are a 2PC-type protocol. When the 'DC' (from the paper) returns the 'agreement offer' to 'A' they are blocked from offering those resources to anyone else (although this is an assumption because the paper doesn't say explicitly what the 'agreement offer' actually means).

Imagine the scenario: DC returns an offer to A1 saying 'these resources for €10". Meanwhile A2, who is prepared to pay €10,000 for the same resources cannot make the agreement because DC has offered them to A1. A2 then goes and makes an agreement with another DC (e.g. another business) and A1 decides they don't want the resources and return a reject message. DC has lost €10,000 of income it could have made because of the protocol it is using.

If A1 is a proxy for a competitor of DC it could repeatedly keep asking for offers it never intends to agree to meaning DC may loose revenue...

Dominic: before I comment further on your proposed protocol what semantics are you attaching to the 'offer' message that the AR returns to the AI? Does the offer mean 'if you accept I will guarantee providing what is contained in this offer' or does it mean something else?

Michael.

[1] http://www.cs.cornell.edu/courses/cs614/2004sp/papers/Ske81.pdf [2] http://blogs.msdn.com/pathelland/archive/2007/05/20/soa-and- newton-s-universe.aspx [3] http://blogs.msdn.com/pathelland/archive/2007/06/14/accountants- don-t-use-erasers.aspx [4] http://betathoughts.blogspot.com/2007/06/brief-history-of- consensus-2pc-and.html [5] http://en.wikipedia.org/wiki/Two-phase_commit [6] www.iids.org/publications/scpe06.pdf

Karl: thank you very much for the excellent summary. (which I must admit I would need a week to really digest.). One thing that I (and I think you also pointed out ) was that that in the case of AR not agreeing, there were not enough hints for the AI to initiate another request.. Any comments on this? #Also comments to show stopper #7 would be very much appreciated :-) Best Regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

-----Original Message----- From: Karl Czajkowski [mailto:karlcz@univa.com] Sent: Friday, August 24, 2007 6:55 PM To: Toshiyuki Nakata Cc: 'Dominic Battre'; 'GRAAP-WG' Subject: Re: [GRAAP-WG] Modification to the wiki Page on Renegotiating anestablished Agreement

...

Hi Dominic:

...

So, yes, there are problems but it looks like a lot of

On Aug 23, Toshiyuki Nakata modulated: people want to

...

...

have this extra commit message. Are there any written records on the pros and cons of having the 2PC?

I think this info. is very important. Unfortunately, I am not able to address this issue.

Karl or others, please respond..

I definitely don't want to repeat the debate which is in the GRAAP-WG email archives, but let me just summarize what I think were the final observations and conclusions.

WS-Agreement is aimed at a distributed, soft real-time (one might say isochronous) environment with limited trust between peers with bounded rationality. In other words, it is for establishing automated agreement between programmatic systems in an Internet-type environment where the agreement terms may involve wall-clock obligations which are at the root of the problem.

When you boil it all down, there is always going to be a synchronization hazard where due to communication delays or faults, or even intentional decision delays, one party does not know whether the other has accepted the agreement and therefore is at risk to perform according to the terms of agreement when not necessary, or ignore the terms of agreement when bound by them.

WS-Agreement formalizes this hazard to always place the burden on the agreement initiator who makes an offer and is bound by it if the responder accepts. Early drafts, derived from our SNAP work, had an extra signalling step to allow a sort of "pre-initiator" called an invitation. The group felt that this was too complicated to pursue, particularly because it could be approximated via advertisement.

An invitation or advertisement would be a non-binding expression of interest in receiving agreement offers, so that the typical client-server roles could be reversed somewhat. The only difference is that an invitation is seen as usually a 1:1 relationship while an advertisement is 1:many. However, due to the non-binding nature of these signals and the assumption of bounded rationality (we can ignore the possibility of bluffing and other psychological strategies), I am not sure these differences are significant. For privacy, one could imagine secure advertisement channels (with authorization) to further blur the boundaries.

Furthermore, 2PC can be synthesized with two WS-Agreement round-trips and an appropriate domain-specific agreement semantics. So, either advance reservation, combined with the right cost/penalty model, or the underlying invitation system can both look like 2PC in practice:

1.a. initiator offers advance reservation, OR 1.b. advertiser publishes interest

after this first stage, both parties are aware of interest and primed to negotiate...

2.a. responder accepts (or rejects) reservation offer, OR 2.b. initiator offers against advertisement (or ignores it)

after this stage, one party is obligated to satisfy and the other has a choice to make... (For the advance reservation, the initiator has a choice because the reservation includes a cost model with cheap cancellation under reasonable deadlines).

3.a. initiator offers claiming agreement (or cancels reservation), OR 3.b. responder accepts offer (or rejects it)

after this stage, both parties are obligated to satisfy...

4.a. responder accepts claiming agreement (or acknowledges cancellation), OR 4.b. initiator acknowledges receipt (e.g. transport-level ACK)

after this stage, both parties actually know what the other knows...

In case it isn't obvious, advertisement is done via WS-Agreement templates and advance reservation followed by claiming is anticipated in the usage scenario examples as well.

...

Best Regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

karl

p.s. I will add that the fundamental challenge I see for GRAAP-WG and WS-Agreement is that everyone approaches it with the same natural (but incorrect) intuitions about trust, signalling, and consensus. I think there is still a large social experiment to see who can deploy systems which are actually performing distributed agreement without a central authority... economics and our real-life world says it should work, most of the time at least. :-)

-- Karl Czajkowski Software Architect

Univa Corporation 1001 Warrenville Road, Suite 550 Lisle, IL 60532

karlcz@univa.com www.univa.com ________________________________________________________________ www.univa.com.

The Leaders of Open Source Cluster and Grid Software

Hi Karl, Very interesthing thoughts. Just some quick comments below. Karl Czajkowski wrote:

Well, my practical view, keeping in mind bounded-rationality systems, is that if the template was insufficient to guide you to an acceptable agreement offer, then a "hint" would not fair any better. Either the advertiser announces its policies/restrictions in detail sufficient to create an agreement, or it does not. Why would it reveal more information on the next iteration? If you're trying to address intelligent parties who do bluffing and bartering, then your problem is out of scope for WS-Agreement...

It is certainly possible that the detail contained in a template may increase in complexity as interaction between parties proceeds. For instance, one could consider a coarse-grained advertisement that identifies the types of capability that a provider offers, and not necessarily the ranges associated with those capabilities. The hint would then be a subsequent refinement of these capabilities in future interations. Yes, therefore there could be revelation of additional information in subsequent interactions.

Another intractable problem is that the resource manager making the decision may not even be able to formulate a specific reason for "why it didn't match", e.g. in a scheduler that is matching many properties at once against a dynamic load of competing requests, it is not necessarily easy to determine what would need to change to make a request get handled above other requests. Furthermore, it would have race conditions since the dynamic load may be different by the time the next offer arrives.

Yes, agree about the matching problem. However, it is possible to rank matches (or mis-matches) using some "match distance" metric. This can range from a associating as weight with attributes that are of most significance to a particular party -- say, I am more interested in having a certain disk space rather than a specific processor speed. The way to deal with dynamic load -- as often undertaken in other performance prediction efforts -- is to deal with summary and aggregate data -- rather than raw data. Hence, one would base a prediction on average (or some other time-based aggregate statistic) rather than the value at a particular point in time.

So I think in practice, an automated WS-Agreement initiator is going to operate with some narrowly-defined commodity offers and try fallback, retry, and fail-over among responders. If this fails, offline analysis and problem determination will be required to understand what went wrong, and how to improve templates and offering systems to avoid these doomed offers.

Yes, agree with this. In the abscence of well defined constraints, I can see a lot of problems with the approach. There are some automated approaches that can help with doing some of the post-failure analysis. regards Omer -- http://www.cs.cf.ac.uk/User/O.F.Rana/index.html / work-fax:+44(0)29-2087-4598 work:+44(0)29-2087-5542 / other:+44(0)7956-299981 / distributed collaborative computing / room n2.14 / school of computer science / cardiff university queen's buildings / newport road / cardiff cf24 3aa / wales / uk

On Aug 24, Michael Parkin modulated:

Hi Karl,

Sorry, I have a couple of quick questions/observations... Apologies in advance if I have misunderstood anything in your email as sometimes happens.

On 24 Aug 2007, at 11:54, Karl Czajkowski wrote:

<snip/>

...

... However, due to the non-binding nature of these signals and the assumption of bounded rationality (we can ignore the possibility of bluffing and other psychological strategies), I am not sure these differences are significant. For privacy, one could imagine secure advertisement channels (with authorization) to further blur the boundaries.

Are you saying that 'bluffing and other psychological strategies' can be ignored in the negotiation protocol that is used or in the negotiation strategy of each participant? For me, these two aspects of reaching agreement are orthogonal, just like they are in (for example) contract law.

I am saying that we were not considering such strategies as relevant and therefore did not care to have multi-round negotiation to try to support them. It was assumed that someone who did care about these might propose further specifications that might reuse some of the agreement data models from WS-Agreement.

So far you have the messages: offer, advert, cancel, accept and reject... all of which are clear to me.

But can you explain what the 'offers claiming agreement' step (3a) is? I'm sorry, I don't understand what this means - is it an offer, accept or another message being sent from the initiator to the responder?

We have always assumed a notion of chaining agreements, e.g. part of the context of an agreement could be another agreement. In the fully agreement-based advance reservation case, the idiom is that you first get an 'advance reservation' agreement and you then follow it up with one or more 'claiming' agreements. The claiming agreement binds the reservation of resource capabilities to a particular use. There are other usage scenarios where the claiming/binding occurs in other domain-specific protocols instead of via claiming agreements. So it is another offer, with agreement terms which reference the existing reservation agreement. It is implicitly understood that the reservation agreement gives you the "right" to make these claims, subject to the finite capacity limits of the reservation. In essence, the entire reserve+claim process is the 2PC protocol for the actual domain specific agreement on the consumption of resources. You might note, this does imply a general form of multi-round negotiation, if you were to construct domain-specific terms which could refine or augment an existing agreement with more information. Once you had an agreement which could claim on an existing agreement and add more agreeable terms, you could converge towards the point of maximum/optimal agreement, starting with more conservative terms... however, no effort has been put into formalizing such term languages, outside the conventional advance reservation models we inherited into this work.

<snip/>

...

p.s. I will add that the fundamental challenge I see for GRAAP-WG and WS-Agreement is that everyone approaches it with the same natural (but incorrect) intuitions about trust, signalling, and consensus.

Can you explain some more about what you think these shared (but incorrect) intuitions are?

My intuition is to a) trust no-one, b) assume messages ('signals') can be lost, duplicated and re-ordered and c) assume that consensus may or not be reached - it depends :-). Are these the same as yours and/or GRAAP-WG's?

You're ahead of the game, I'd say. :-) The typical intuition people have is that consensus can be reached easily, discounting the byzantine faults of the Internet environment, and having a naive understanding of what agreement and commitment really mean. I have lost track of the number of times people have wanted to jump into the most elaborate negotiation strategies they've ever witnessed in real life, without considering: 1. The messaging (un)reliability model you mention. 2. The difference between intelligent and machine agents in terms of their ability to reason and game one another. 3. The difference between contracts signed by legally responsible entities and the automatic decisions of machines. 4. The realities of over-subscription and risk balancing in realistic economic environments (e.g. dealing in real numbered costs and benefits instead of hard absolutes). 5. The desired/expected/acceptable behavior for a large-scale system with many of their proposed agents functioning simultaneously. What I see is that people who focus on this area intensely will all eventually start to see the same general solutions, but these are not very compatible with what the naive user wants. So real deployment faces the challenge of users who do not appreciate the value of these systems nor the theoretical impossibility of what they desire.

Michael.

karl -- Karl Czajkowski Software Architect Univa Corporation 1001 Warrenville Road, Suite 550 Lisle, IL 60532 karlcz@univa.com www.univa.com ________________________________________________________________ www.univa.com. The Leaders of Open Source Cluster and Grid Software

Toshi, I have the following comments/observations after reviewing your wiki page... sorry I have not been able to keep a close watch on the recent activities of the group. 1. The idea of negotiation of alternatives is difficult and I think requires a better negotiation protocol. After much debate, as I recall, we limited WS-Agreement to simple acceptance of an offer. If the offer has alternatives in it, then the responder is accepting to satisfy this compound expression in any way he sees fit, with no information about how, or indeed whether his solution might vary over time and be satisfied by different clauses in the compound rules! It would take domain-specific interpretation of the SDTs to somehow fix this solution, as there is nothing in the protocol to communicate a "lowering" or simplification of the alternatives expression. (For example, I anticipated that in a basic use of JSDL for a job term, the interpretation could be defined that the service terms are chosen at job-start time and frozen, as is a typical implementation requirement for HPC resources... you would know they are not time-varying, though there is still no facility to communicate which exact parameters were chosen.) What I would suggest is that you try to keep this aspect of negotiation protocol orthogonal to the underlying notion of renegotiation. First, work on the semantics for renegotiation of an agreement as you have done, e.g. replacement/superceding of an agreement. Then, admit that basic or advanced protocols could be used to negotiate either the initial or subsequent agreement. For example, a relatively simple renegotiation could adapt the existing factory pattern for both initial and subsequent negotiations. If a future specification provides a multi-round negotiation to lower/simplify abstract agreement constraints to a more concrete solution, this could replace the basic factory pattern in both cases too. 2. I think the idea of superceding an agreement is fine, but I have trouble seeing a distinction between this and the general use of agreements in the context of other agreements. For example, the advance reservation scenario allows "claiming" of a resource reservation, and you can interpret this as adjusting an initial resource agreement to include binding to an application, with the same results as if someone simply negotiated an application with the same QoS terms in one shot... What I would point out is that this claiming/context model allows many:many derivation of agreements in the general case. E.g. I could reserve a large resource (in space-time) and consume it with multiple applications which either run serially or in parallel. I could also combine several resources (in separate agreements) into a complex application. Couldn't a renegotiation also be temporary, e.g. "boost this resource reservation for the next hour, but then fall back to the previous terms"? I am not sure how "supercededby" would be applicable here. Is it worth having one more general metalanguage for discovery/navigation of agreements which are linked to other agreements? We could use the extensibility of the wsag:Context to enumerate the actual claimed or superseded agreements, and it seems useful to have a dynamic resource property which could provide reverse-lookup of new agreements which list an agreement in the new wsag:Context too. 3. Also, a general concern I have is that the discussions are not crisp about the uses of the agreement. The talk of race conditions makes me nervous, as it seems to combine denotation of service terms with the implementation of resource managers. In my view, WS-Agreement is completely focused on the establishment of terms between the two parties, and says nothing about how one of the parties is implementing the protocol. I do not see a necessary race condition for "supercededby" because I don't think the initiator (for example) needs to be aware of this state change in order to meaningfully express a claim against an agreement. If an agreement is renegotiated, it could still be usable for claiming by name, while the actual resource manager has to take into account that there are now aliases to the newly revised delivery terms... 4. The question of having "responder initiated renegotiation" was foreseen in the optional symmetric protocol mode. In essence, if EPRs are exchanged so that both parties have an EPR representing the other party's view of the agreement, then they can switch roles and become initiator for further rounds of communication. In order to use this feature, one would need to define an extension to the protocol, e.g. have the symmetric agreement resources support an extended protocol which includes the renegotiation operations as well as the basic monitoring/cancellation operations. I think it would be appropriate to define a new negotiation protocol as a profile on this feature, so that a specific SDT would demand the presence of a renegotiation facility which would then be available as extended operations and resource properties on the Agreement resource. Again, if we consider the fuzzy case of many:many renegotiations, the best approach might be a simple RP in the agreement that holds an EPR to the renegotiation service, thereby separating discovery (via lookup of this RP an existing agreement) from claiming/context references which might involve more than one agreement at a time. karl -- Karl Czajkowski Software Architect Univa Corporation 1001 Warrenville Road, Suite 550 Lisle, IL 60532 karlcz@univa.com www.univa.com ________________________________________________________________ www.univa.com. The Leaders of Open Source Cluster and Grid Software

Karl: Thank you very much for your comments (and your patience in wating for my reply) The repli ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

Toshi, I have the following comments/observations after reviewing your wiki page... sorry I have not been able to keep a close watch on the recent activities of the group.

1. The idea of negotiation of alternatives is difficult and I think requires a better negotiation protocol.

OK <snip>

What I would suggest is that you try to keep this aspect of negotiation protocol orthogonal to the underlying notion of renegotiation. First, work on the semantics for renegotiation of an agreement as you have done, e.g. replacement/superceding of an agreement. Then, admit that basic or advanced protocols could be used to negotiate either the initial or subsequent agreement.

I think this is fine as *much* discussion would have to be made for negotiation of alternatives.

2. I think the idea of superceding an agreement is fine, but I have trouble seeing a distinction between this and the general use of agreements in the context of other agreements. For example, the advance reservation scenario allows "claiming" of a resource reservation, and you can interpret this as adjusting an initial resource agreement to include binding to an application, with the same results as if someone simply negotiated an application with the same QoS terms in one shot...

What I would point out is that this claiming/context model allows many:many derivation of agreements in the general case. E.g. I could reserve a large resource (in space-time) and consume it with multiple applications which either run serially or in parallel. I could also combine several resources (in separate agreements) into a complex application. Couldn't a renegotiation also be temporary, e.g. "boost this resource reservation for the next hour, but then fall back to the previous terms"?

Your points are exactly what we had in mind in the business grid project.. (The scenarios are included in HPCC2006 paper http://www.coregrid.net/mambo/images/stories/TechnicalReports/tr-0050.pdf I've also uploaded an excerpt from the presentation we made onto the Wiki. The last slide exactly shows the point I wanted to make.)

I am not sure how "supercededby" would be applicable here.

I think Supercededby could be useful for some purposes. eg. Logging purposes to show which Agreement had been effective until when then Superceded/replaced by which Agreement to check for SLA violation etc.

Is it worth having one more general metalanguage for discovery/navigation of agreements which are linked to other agreements? We could use the extensibility of the wsag:Context to enumerate the actual claimed or superseded agreements,

I think this could be one way of realizing this feature. (I had intended to put the 'Superceded-by " in the wsag:Context)

and it seems useful to have a dynamic resource property which could provide reverse-lookup of new agreements which list an agreement in the new wsag:Context too.

3. Also, a general concern I have is that the discussions are not crisp about the uses of the agreement. The talk of race conditions makes me nervous, as it seems to combine denotation of service terms with the implementation of resource managers. In my view, WS-Agreement is completely focused on the establishment of terms between the two parties, and says nothing about how one of the parties is implementing the protocol.

I agree that this is a bit of an implementation issue but I think the discussion we had in Terminating was that Termination could take a long time to be decided and we extended the Agreement State wiht such states as ObservedAndTerminating so I had wanted to be consistent in this sense. ##As an off track issue, It seems in creating the official pdf, # http://www.ogf.org/documents/GFD.107.pdf Figure in Section 7.1 got corrupted.. Any way to remedy this?

4. The question of having "responder initiated renegotiation" was foreseen in the optional symmetric protocol mode. In essence, if EPRs are exchanged so that both parties have an EPR representing the other party's view of the agreement, then they can switch roles and become initiator for further rounds of communication. In order to use this feature, one would need to define an extension to the protocol, e.g. have the symmetric agreement resources support an extended protocol which includes the renegotiation operations as well as the basic monitoring/cancellation operations.

I think it would be appropriate to define a new negotiation protocol as a profile on this feature, so that a specific SDT would demand the presence of a renegotiation facility which would then be available as extended operations and resource properties on the Agreement resource.

Again, if we consider the fuzzy case of many:many renegotiations, the best approach might be a simple RP in the agreement that holds an EPR to the renegotiation service, thereby separating discovery (via lookup of this RP an existing agreement) from claiming/context references which might involve more than one agreement at a time.

This is an interesting (if stagering) point. I had naively assumed that AR would be maintaining the Agreements A third party Agreement Factory could solve the problem with No.7 but this might have quite an impact on other parts of WS-Agreement Spec. Comments from other people also appreciated. Best Regards and Thanks Toshi

karl

-- Karl Czajkowski Software Architect

Univa Corporation 1001 Warrenville Road, Suite 550 Lisle, IL 60532

karlcz@univa.com www.univa.com ________________________________________________________________ www.univa.com.

The Leaders of Open Source Cluster and Grid Software

On Aug 27, Dominic Battre modulated:

I tried to digest that and this is what I came up with:

https://cit-server.cit.tu-berlin.de/trac/negmgr/wiki/TwoPhaseCommit

(I used my wiki because it supports tables)

It would be great, if you could have a brief look at it and tell me whether this is what you had in mind.

Well, your example looks like a solution with a new invitation message. The basic 2PC/advance reservation idiom, as already illustrated in the advance reservatione example in the spec, would be: Consumer Provider (as Initiator) (as Responder) a. discovery <--- template --- b. prepare --- createAgreement(SLA1) ---> <--- accept --- (or reject to abort preparation) c. commit --- createAgreement(SLA2) ---> <--- accept --- (reject would be a serious failure) The discovery phase (a) is not emphasized in WS-Agreement because it was assumed to be an area where OGSA would provide other solutions. The basic WSRF resource property model was considered sufficient to capture the template model and allow basic query, but one hopes there will be search services where a consumer could locate providers with relevant templates. It might also include other non-obligating queries regarding resource availability. The SLA1 in phase (b) is the advance reservation and captures the resource requirements that are needed for the co-allocation. Due to the limited negotiation model in WS-Agreement, the co-allocation solution must already be concretely proposed here, e.g. the time of resource availability is part of the SLA1 terms, since the consumer/initiator has to make consistent advance reservation proposals to all providers involved in the transaction. The only answer available in the protocol is "yes/no" as to whether they can prepare as requested in SLA1. (If you are looking for a proposal/counter-offer pattern, that is an entirely different issue than this 2PC synchronization. That, indeed, requires a new negotiation protocol, though it is possible to define was as an extension or complement to WS-Agreement.) If preparation fails, the initiator can cancel/destroy any existing reservations to abort the 2PC transaction. Therefore, as I mentioned previously, a cost model with cheap advance reservation+cancellation is required to allow this idiom. One would expect that the cost of reservation goes up the longer it is held, e.g. to discourage aggressive use of 2PC resulting in live-lock of resources. The SLA2 in phase (c) is the actual "job" or whatever was intended to be co-scheduled. It makes claims on the appropriate SLA1 which should mean that the provider is obligated to accept this claim, since he already promised the resources. Thus, rejection at this time is unexpected and indicates a violation, so the 2PC semantics would fall apart here. (Note, this is no different than any other way that a non-trusted/partially-trusted party could choose to violate 2PC protocols.) karl -- Karl Czajkowski Software Architect Univa Corporation 1001 Warrenville Road, Suite 550 Lisle, IL 60532 karlcz@univa.com www.univa.com ________________________________________________________________ www.univa.com. The Leaders of Open Source Cluster and Grid Software

Dominic, Sorry, I missed a step so I withdraw one of my questions below... On Aug 28 2007, parkinm@cs.man.ac.uk wrote:

On Aug 27 2007, Dominic Battre wrote:

...

Thank you very much, Karl, for giving a lot of insight what is behind WS-Agreement.

...

Furthermore, 2PC can be synthesized with two WS-Agreement round-trips and an appropriate domain-specific agreement semantics. So, either advance reservation, combined with the right cost/penalty model, or the underlying invitation system can both look like 2PC in practice:

I tried to digest that and this is what I came up with:

https://cit-server.cit.tu-berlin.de/trac/negmgr/wiki/TwoPhaseCommit

Between step 5 and 6 of this protocol, how long does the provier wait for a response? As there is no facility for the user reject an offer in this protocol and let the provider know it doesn't want the advance reservation - the provider must specify a time limit to the offer, no? As was said in an earlier email - you can't assume agreement is going to happen...

Sorry, please ignore this comment - I just saw the "User can cancel advance reservation offer for cheap fee" step.

Also, what happens if between step 5 and 6 another user wants to reserve the same resources? What does the provider do then?

As I mentioned in a previous email, the provider cannot offer those resources to the second user because if the first user accepts and the second user acccepts too, there is a problem of overcommitment of resources.

...

(I used my wiki because it supports tables)

It would be great, if you could have a brief look at it and tell me whether this is what you had in mind.

If some people want to contribute, I'd be interested in starting to write a "Best Practices in WS-Agreement" / "Design Patterns in WS-Agreement" / "WS-Agreement cookbook" / ... document.

Yes, I am interested.

...

This issue of 2PC for example would be a good candidate for such a document. I think it would really help if we find a place to collect examples, approaches of modeling something, approaches of implementing something, ...

I could easily contribute lots of questions but maybe some answers as well.

Thanks,

Michael.

Hi: Probably I should be explaining what I am trying to do. Thanks to the discussion on the mailing list in August, many points which need to be resolved are becoming clearer. Unfortunately, I don't have the answers to most of the points, and I currently lack the time / effort to delve into deep investigation.. OTOH I don't want to leave the micro-spec to be uncompleted and for more realistic discussion felt that blue-print ( or template if you like) of the spec would be needed. I am (very slowly) compiling the blue-print (based on the WS-Agreement Spec). In order to handle my limited English vocabulary, I am borrowing quite a bit of WS-Agreement Spec, so would expect the document to be authored by the original authors and any new contributors. Comments on how to proceed as well as improving the content is very much welcome. Also, for the glossary, I've included terms which had been defined in the original WS-Agreement Spec and is referred in the new spec. Is this necessary? or would citing WS-Agreement be enough? Best Regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

-----Original Message----- From: Toshiyuki Nakata [mailto:t-nakata@cw.jp.nec.com] Sent: Thursday, September 13, 2007 4:35 PM To: 'Toshiyuki Nakata' Cc: 'GRAAP-WG' Subject: New Pages/ Usage Scenarios　Glossaries.

Hi: I've updated the Wishlist page https://forge.gridforum.org/sf/wiki/do/viewPage/projects.graap -wg/wiki/ReNeg otiationWishlists to add pointers to Usage Scenarios https://forge.gridforum.org/sf/wiki/do/viewPage/projects.graap -wg/wiki/Usage Scenarios and Glossary https://forge.gridforum.org/sf/wiki/do/viewPage/projects.graap -wg/wiki/Gloss aryPage

#I'm afraid I hadn't noticed the naming convention of the wiki. #I probably need to put a prefix on the newer pages so that there won't be name conflicts. #Does anyone know of how to rename already established ones?

Comments very much welcome.

I'm afraid I won't be able to participate in OGF21 due to schedule c[lr]ashes but hope to respond on the wiki / mailing lists.

Best Regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

...

-----Original Message----- From: Toshiyuki Nakata [mailto:t-nakata@cw.jp.nec.com] Sent: Thursday, August 23, 2007 9:31 AM To: 'Dominic Battre' Cc: 'GRAAP-WG' Subject: RE: [GRAAP-WG] Modification to the wiki Page on Renegotiating an established Agreement

Hi: Dominic： Thank you very much for your thoughtful comments. I'll just address the first one. For the rest, please give me some time.

...

ad "New EPR or re-write the current WS-AG document?" during the renegotiation the agreement is in some kind of intermediate change (i.e. it might be in a proposed new status that is not yet accepted by the other party), don't we need a new EPR for that?

The reason that I wanted to re-write the current WS-AG rather than a new EPR was that one could never know who might be using the old EPR. In a complex scenario like the one I mentioned in Business Grid Computing case or some broker case, old EPR might be propagated to other parties who would be using it. So I thought that it would not be realistic to assure that the NEW EPR would be propagated to all the bodies who might be referring to the old EPR.

On the other hand, re-writing the current WS-AG document kept by the Agreement Responder does cause a serious race condition when the AR is the requestor for modifying the Agreement. (ie. it must be re-written only after the AI says he agrees, but when?)

...

What would the ResourceProperties (e.g. the SDTs or GTs) look like in the intermediate state? (DB, 2007/08/22) I am assuming that the service (under the old SLA) is still being provided even while the renegotiation is going on. (If the service is stopped, then we don't need renegotiation. We just terminate the old agreement and create a new agreement)

As for the rest of your comments, essentially I agree with you. The only problemis that some of them seem to be very difficult to address :-( In any case, please give me some time as I can only do this work sporadically.

Best regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

...

-----Original Message----- From: Dominic Battre [mailto:mailinglists@battre.de] Sent: Thursday, August 23, 2007 5:18 AM To: Toshiyuki Nakata Cc: 'GRAAP-WG' Subject: Re: [GRAAP-WG] Modification to the wiki Page on Renegotiating an established Agreement

Hi Toshi,

I did some brainstorming and added some random comments/wishes/ideas. Please have a look whether anything could be useful for the further proceeding. I don't know how much you have discussed and discarded before. Please feel free to ask me, in case my comments are confusing.

Best regards,

Dominic

Toshiyuki Nakata wrote:

...

Hi: I've put up some more things to ponder on the re-negotiation Wiki Page

https://forge.gridforum.org/sf/wiki/do/viewPage/projects.graap -wg/wiki/ReNeg

...

otiationWishlists?_message=1187773027531 esp. No.7 is rather a tough one.

Comments welcome.

Best Regards Toshi ----- Toshiyuki Nakata 中田　登志之 Executive Chief Engineer, Central Research Lab. NEC 1753, Shimonumabe, Nakahara-Ku, Kawasaki,Kanagawa 211-8666,Japan Tel +81-44-431-7653 (NEC Internal 22-60035) Fax +81-44-431-7609 (NEC Internal 22-60509)

-------------------------------------------------------------- ----------

...

-- graap-wg mailing list graap-wg@ogf.org http://www.ogf.org/mailman/listinfo/graap-wg