[ogsa-rss-wg] Candidate Ordering Language

[Donal K. Fellows]

Hi everyone!

I've previously proposed that we should be returning ordered sets of
candidates from the CSG. But it's been (rightly) pointed out that this
means the caller needs some control over the ordering. In general, this
is a difficult thing to do - valuation policies might need to be very
flexible indeed, forcing the use of a general programming language with
all the attendant security trickinesses - but we can probably do a
cut-down version that captures most of what is needed with much less
effort. Furthermore, if we define this through appropriate extensibility
tricks, we can still allow the more general solutions to be there in the
complex cases.

Therefore, this is a simple function language that operates (given some
context offer) and provides a single floating-point value that indicates
the ranking. (Open question: should small or large values be "good"?)

   Language consists of a term (possibly with subterms) yielding a value.
   There are different kinds of terms:

   Combination Terms:

      <sum> term+ </sum>
      <product> term+ </product>

      Sum adds its terms together, product multiplies them together.
      Subtraction and division can be constructed using these and the
      right monadic terms.

   Monadic Terms:

      <power exponent="xsd:double"> term </power>
      <negate> term </negate>
      <log> term </log>
      <exp> term </exp>
      <abs> term </abs>

      Log and exp use natural logarithms. Power isn't strictly necessary
      with log and exp, but it'll simplify things for most common cases.
      Abs returns the absolute value of the term (chopping any sign).

   Atomic Terms:

      <constant> xsd:double </constant>
      <value base="xsd:dateTime|now"? > XPath </value>
      <exists> XPath </exists>

      Constant allows the embedding of literals, value allows the use of
      a value picked out of the context offer (strictly, it uses the
      value of the first node in the nodeSet returned by evaluating the
      XPath expression) and exists allows the checking of whether a
      particular XPath expression refers to anything within the context
      offer (it's value is 1 if the nodeSet is non-empty, and 0
      otherwise).

      In order to deal with values that are expressed as xsd:dateTime
      instead of numerics, value has an optional base attribute and the
      result is the difference between the base time and the "value" time
      in *seconds*.

Example:

The value is the sum of the price times a constant factor, and the
inverse square root of the number of CPUs allocated (using some schema
for offers that I've picked out of the air)...

    <sum>
      <product>
        <value> //price/@value </value>
        <constant> 42 </constant>
      </product>
      <power exponent="-0.5">
        <!-- Assume that somewhere there's some JSDL -->
        <value> //JobDescription/Resources/IndividualCPUCount </value>
      </power>
    </sum>

Or something like that. And this very simple structure has the advantage
of being both pretty easy to implement (once you have XPath) and free of
programming language nasties.

Is this sufficient? Or too complicated? Have I missed anything obvious?

(The other major alternative is to define a language that can compare
two terms, but that's likely to be more difficult to do, and it can
easily lead to ill-defined orderings, i.e. where there is no partial
order on the offers at all. A scoring function doesn't have those problems.)

Donal.