OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

xri message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]

Subject: RE: [xri] Decision on Ref "backtracking" issue


Backtracking is needed in any case, because it's needed for the XML
bracketing as well as for the following of sibling Refs. 

I've attached my previous email that talks about this in more detail.

~ Steve

> -----Original Message-----
> From: Wachob, Gabe [mailto:gwachob@visa.com]
> Sent: Monday, January 23, 2006 10:07 AM
> To: drummond.reed@cordance.net; xri@lists.oasis-open.org
> Subject: RE: [xri] Decision on Ref "backtracking" issue
> I'm not sure that the way #2 is specified, its any different than #3.
> If I "try" a REF, and in resolving the resulting XRI, I end up with a
> set of REFS, am I required to try that set of REFs that result from
> resolving the XRI I got from choosing the first REF?
> Specifically:
> Lets say =GabeW*coworker resolves to refs that point to =Mike and =Dave,
> and I choose =Mike and =Mike ends up with a ref to =SecretAgent and
> =PublicAgent.
> Lets say resolution of =SecretAgent fails.
> What do I do? Is that a failure that requires me to go back to =Dave? Or
> should I try =PublicAgent? What happens if =PublicAgent fails?
> Note that I think the wording of #2 and #3 both require me to go back to
> =Dave is =SecretAgent and =PublicAgent fail. This is still
> backtracking... Right?
> 	-Gabe
> > -----Original Message-----
> > From: drummond.reed@cordance.net [mailto:drummond.reed@cordance.net]
> > Sent: Sunday, January 22, 2006 12:41 AM
> > To: xri@lists.oasis-open.org
> > Cc: drummond.reed@cordance.net
> > Subject: [xri] Decision on Ref "backtracking" issue
> >
> > First, for anyone unfamiliar with the Ref "backtracking" issue in XRI
> > resolution, the question is where we draw the line in terms
> > of required
> > behavior for a resolver when it comes to following the XRIs
> > contained in
> > Ref elements (which I'll just call "Refs" in this message).
> >
> > Based on the discussion among the editors so far, it appears
> > we have three
> > choices:
> >
> > 1) Stop at the very first Ref in the current XRD and error if
> > it fails.
> >
> > 2) Try all Refs in the current XRD and error only if all of them fail.
> >
> > 3) Try all Refs in the current XRD, and if they all fail,
> > then "backtrack"
> > to any previous XRDs and try all of them, and only if they
> > ALL fail should
> > the resolver fail.
> >
> > Gabe has proposed that we not require #3, since it is both the most
> > complex and can take the most time. I agree.
> >
> > At the other end of the spectrum, Les' message below proposes
> > that we not
> > stop at #1, since there may be a good reason if the first Ref
> > in an XRD
> > doesn't work that the resolver should try the others.
> >
> > So the proposal on the table now is to take a middle course
> > and require
> > only that if resolution of the first Ref in an XRD fails, the resolver
> > must (subject to its own timeout constraints) try the others
> > in priority
> > order, but it is NOT required for a resolver to "backtrack"
> > to previous
> > XRDs and try earlier "untried" Refs.
> >
> > Anyone who disagrees with this proposal, please send email to the list
> > with an alternate (preferably by end of day Monday USA --
> > silence will be
> > deemed consensus ;-)
> >
> > For reference, here's what the actual wording might look
> > something like:
> >
> > "If a client resolver is not able to find the requested
> > service endpoint
> > in the current XRD, or if the URI(s) for that service endpoint do not
> > produce a successful response, the client resolver MUST
> > (subject to its
> > own timeout constraints) attempt resolution of the highest
> > priority Ref of
> > the current XRD. If that resolution is successful, the final
> > XRD of the
> > resulting XRDS document becomes the current XRD and
> > resolution continues.
> > If that resolution is not successful, the client resolver MUST attempt
> > resolution of the next highest priority Ref of the current
> > XRD, and so on.
> > If resolution of all Refs in the current XRD fails, the
> > client resolver
> > MAY return an error 27, VALID_REF_NOT_FOUND, or the client
> > resolver MAY
> > "backtrack" to previous XRDs in the resolution chain and
> > attempt to follow
> > any untried Refs. Note that the latter behavior is not
> > required and should
> > not be expected."
> >
> > =Drummond
> >
> >
> >
> > Do we really want to stop resolution if one REF is
> > unresponsive?  It seems
> > to me to be a good idea to have multiple authority services
> > (either via
> > SEPs, URIs or REFs) in case one is having a problem.  It
> > seems to me the
> > resolver should do what ever it can, within reason, to locate
> > the answer
> > for a request.  In DNS a domain can have upto 13 nameservers.
> >  If one is
> > not responding for what ever reason the resolver tries another.
> >
> > I-Name:  =les.chasen
> >
> > --------------------------------------------------------------
> > -------------
> >
> > From: Drummond Reed
> > Sent: Friday, January 20, 2006 11:33 AM
> > To: gwachob@visa.com; steven.churchill@ootao.com; Chasen,
> > Les; Tan, William
> > Cc: drummond.reed@cordance.net
> > Subject: Gabe's feedback and reference "backtracking"
> >
> > Gabe and Res Editor's:
> >
> > Note that since I can only send from Gmail, I can't send this
> > to the list.
> > One of you is welcome to forward this to the list.
> >
> > I just went over Gabe's comments. Fantastic stuff. There's
> > many that we
> > need to go over (I *really* wish I could be on the call
> > Friday morning but
> > I gotta go to bed now...). Anyway, the single biggest issue
> > is the one of
> > whether a resolver needs to do "backtracking" of references
> > (as currently
> > indicated in ED 04) or whether, as Gabe recommends, the
> > resolver should
> > just stop and report an error if it gets an error.
> >
> > I tend to agree with Gabe on this with one exception: I think
> > that *within
> > a single service endpoint* if the resolver gets a network
> > error on one URI
> > and more then one URI is supplied, the resolver should try the next
> > highest priority URI, and so on. Same for the next highest priority
> > service if there is >1 Service of that type in the XRD.
> >
> > But I agree with Gabe that if a resolver follows a reference
> > and hits an
> > error, it should not need to "backtrack" but just stop and report the
> > error.
> >
> > If everyone agrees to that on today's call, please publish it in the
> > minutes and I'll update the flowcharts to match (and start
> > working on ED
> > 05 to make those changes.)
> >
> > All of Gabe's other comments made sense to me. Please do record in the
> > minutes any others that the editors have consensus on and I'll start
> > getting those into ED 05. I'd then like to send it to Gabe (or ???) to
> > take the pen and make whatever other changes we feel are
> > necessary before
> > publishing it as WD 10.
> >
> > =Drummond
> >
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe from this mail list, you must leave the OASIS TC that
> > generates this mail.  You may a link to this group and all
> > your TCs in OASIS
> > at:
> > https://www.oasis-open.org/apps/org/workgroup/portal/my_workgr
> > oups.php
> >
> >
> ---------------------------------------------------------------------
> To unsubscribe from this mail list, you must leave the OASIS TC that
> generates this mail.  You may a link to this group and all your TCs in
> at:
> https://www.oasis-open.org/apps/org/workgroup/portal/my_workgroups.php
From: Steve Churchill [steven.churchill@ootao.com]
Sent: Saturday, January 21, 2006 10:54 PM
To: 'Drummond Reed'
Cc: 'drummond.reed@cordance.net'
Subject: RE: Updated flowcharts per Steve's recursion point




Response to your previous message:


At this point, it is not a matter of “simplicity”, as you mention in your email. I am attempting to judge if your version is programmatically correct – that is, does the flowchart express the correct Ref traversal behavior. (As it stands, the correctness of your flowchart cannot really be determined. I attempt to explain why below.)


> The rule I folowed was that the "Go to Reference Selection" box was no longer a "handoff" but just a "subroutine" that always returned you to the same flowchart so you continued from there.


My question was actually about the "Go to Authority Resolution Flowchart". I wanted to know whether or not you intended that to be on the same stack frame.


It is very much a moot point, anyway, because flowcharts simply cannot express the return being on a separate stack frame. (Nor can they directly represent recursion, since that involves separate stack frames.)


Why does this guy keep harping about the freaking stack?


At this point I need to again regurgitate the reasons why a stack is required (if even just abstractly, as in my approach) to maintain the nested traversal contexts for our Ref graph traversal.


  1. We need to save the previous traversal contexts in order to obtain the “next” Ref from a given context (for the case that sibling refs are to be traversed when a previous one fails.)


  1. We need to save the previous traversal contexts in order to perform the XML bracketing (the output of the XRDS which surrounds inner nested Ref traversals.)


Note that our Ref traversal is really just plain old standard graph traversal. Wikipedia has it right: one cannot perform this type of traversal without using an explicit or implicit stack to push and pop previous traversal contexts. (http://en.wikipedia.org/wiki/Stack_(data_structure).)


Attempting to represent (using a flowchart) an algorithm that performs graph traversal (requiring a stack) can be done. But one must be careful. For example, here are two valid ways.


  1. Represent the stack explicitly. Here is an example that does this: http://www.freepatentsonline.com/6356902.pdf. (By the way, this flowchart IS programmatically correct.)


  1. Do what I did in my version and “abstract out” the entire graph traversal (and thus the stack/recursion) from the flowchart. This is precisely what is done by my box “Get XRD for Ref”. Yes, that box performs a recursive invocation of the entire Authority Resolution phase in order to perform the nested graph traversal. But no more needs to be said about it in the flowchart. That part has been abstracted out. (Note that I do not attempt to “Go to” the start of authority resolution, because that would be attempting to implement graph traversal within the flowchart, and this cannot be done without an explicit stack. More below.)


Your approach to the flowchart falls in neither of two categories above. It attempts to “Go to” the beginning of Authority Resolution in a non-recursive manner (because flowcharts don’t allow recursion) and it attempts to somehow represent the graph traversal logic required by (1) and (2) above without dealing with the concept of nested traversal contexts.


The correctness of your flowchart cannot be evaluated, because statements like: “From the current XRD, get next highest level Ref” have no meaning outside of a traversal context. (At which traversal context does the current XRD exist?) You asked in your previous email if this was an implementation decision. It is not, because what we are talking about here is “can someone follow our intended logic from the flowchart”. The answer is no, because, as I said, the graph traversal logic, by definition, cannot be expressed without the notion of pushing and popping traversal contexts in a stack. (Representing graph traversal without a stack is akin to trying to represent a flow chart without being able to use the conditional box. The algorithm simply cannot be expressed.)


Again, my approach in (b) simplifies the entire issue by entirely abstracting away the graph traversal from the flowchart. Any part of the flowchart always deals with a single traversal context. Here is the most crucial element of my approach: I never attempt to “Go to” the start of authority resolution. The moment that I attempt to do something like that is the moment the flowchart starts trying to implement the graph traversal, and the moment I must explicitly represent a stack in the flowchart.


These are difficult concepts, and we don’t have a whiteboard. It’s hard to get through it, but we will.


~ Steve




From: Drummond Reed [mailto:drummond.reed@gmail.com]
Sent: Saturday, January 21, 2006 6:15 PM
To: Steve Churchill
Cc: drummond.reed@cordance.net
Subject: Re: Updated flowcharts per Steve's recursion point




Yes, I am getting rest, and China is pretty awesome. Just wish I had the time to explore it vs. getting all this work done.


Anyway, good questions you ask. Here's my high-level answer: from a SPEC standpoint, I don't think it matters whether the stack frame is implicit or explicit. If I understand you right, that's an implementation decision. The spec merely needs to make the logical flow clear and unambiguous.


The key criteria that I would apply then is simplicity. What's the simplest way to depict the recursive nature of reference processing that produces the nested XRDS documents? What I sent you was the simplest way I could think of to show it. The rule I folowed was that the "Go to Reference Selection" box was no longer a "handoff" but just a "subroutine" that always returned you to the same flowchart so you continued from there. I then followed it with Authority Resolution, which either returns an XRDS document or an error. So that's the recursion.


Does this work now? Or do you think there's a simpler, clearer way to do it?




On 1/20/06, Steve Churchill <steven.churchill@ootao.com> wrote:




I hope that things are going well on your trip. I hope you are managing to get some sleep and rest.


I'm trying to understand where the stack fits in with the current flowcharts.


As correctly pointed out on the wikipedia reference I sent, a stack is *required * for the type of traversal taking place for ref processing. Either it needs to be explicit – by the code managing its own stack structure, or implicit – by the code using the runtime call stack via recursion.


Here's my question: when I see a box in the flowchart that says, for example, "Go to Authority Resolution Flowchart" (as in the Auth-Res flowchart) do you intend that (1) execute as a loop on the existing stack frame or (2) to execute as a procedure call causing a new call stack frame?


I'm asking this, because, in order to understand the Ref traversal of the current flowcharts, I need to understand how the stack is being pushed and popped. Note that (1) above implies that a single procedure (stack frame) has code that is branching back to itself (so an explicit stack structure would be needed to handle the traversal.) In the case of the Auth-Res flowchart saying "Go to Authority Resolution Flowchart" then (2) would imply recursion.


Upon your answer, I will respond with further comments.



~ Steve





From: Drummond Reed [mailto: drummond.reed@gmail.com]
Sent: Friday, January 20, 2006 7:55 AM
To: steven.churchill@ootao.com; les.chasen@neustar.biz; William.Tan@neustar.biz; gwachob@visa.com
Cc: drummond.reed@cordance.net
Subject: Updated flowcharts per Steve's recursion point


[I'm sending from my Gmail account because it's clear most of my regular SMTP outgoing email is not getting out from China. Please Reply All so I get the reply via my Cordance account because incoming email seems to work fine.]


Steve and Res editors:


Steve sent me a note pointing out I still didn't get the recursive nature of reference processing correctly in the ED 04 version of the flowcharts (despite him having sent me two corrections to that effect.) My fault. I finally got the time tonight to make the corrections.


Steve, please look over the attached Visio file. The key change was to the Auth-Res page, of course, but in fact all the flowcharts that had a Go To Reference Processing call on them had to be updated because now the recursion loop must be shown on each flowchart that calls for reference processing.


It was well worth doing for another reason -- I caught a flaw in the Default Type Selection flowchart where if you started looking for a Path match but didn't find one and switched over for looking for a default Type match ($res*local or $res*path), and you didn't find that either, so you started reference processing, if you subsequently resolve the Ref and get a new XRD, you need to "start again" checking for a Path match first before switching back to looking for a default type.


I had missed that in the ED 04 flowchart. Fixed now.


Anyway, Steve, let us all know if these updated flowcharts fix the recursion problem (and if not, please modify them until they do, then send them back to me.)


Meanwhile I'll start looking over the comments Gabe sent.




[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]