Introduction#

Parallel-or introduces a paradigm in which an output can be computed given only some of the inputs. However, the output is monotonic in the inputs; once an output value has been computed, it is not affected by subsequent inputs. We explore extensions to this paradigm, where the output may not be monotonic.

To set the context for the problem, consider asking two airlines, sites A() and B(), for quotes. Normally, we expect the quotes x from A() and y from B(), to arrive relatively quickly, and then we call Normal(x,y) for normal processing (by the accounting department). However, we would like to do processing even when only one quote is available. In that case, we would call Special(x) if x is available (or Special(y) if y becomes available). To avoid race conditions, we wait for a short amount of time, d, after the first quote, say x, becomes available. If y becomes available within this time window, we call Normal(x,y). If y does not become available, we call Special(x), but we still wait to receive y. If y becomes available before Special(x) responds, we call Normal(x,y) and use its response (ignoring any response from Special(x)). If y is received after Special(x) responds, the response from Special(x) is published and y is ignored.

Observe from the specification that both Special(x) and Special(y) would not be called, because Normal(x,y) could have been called after both x and y become available. We first consider some variations.

Problem 1#

Priority of y over x. Given x and y as before, call P(x) and Q(y) as soon as x and y become available. If P(x) returns a value before Q(y) has been called, publish that value and halt. Otherwise, publish only the value of Q(y).

val (v,b) = (P(x),false) | (y,true)
if b then Q(y) else v

Problem 2#

Same as problem 1, but additionally, P should not be called if y is available before x.

val c = x >> false | y >> true
if c then Q(y)
else {- Solution to Problem 1 -}

Problem 3#

Call P, Q and R when x, y or (x,y) become available. If R has been called, take its response. Else, publish whichever of P or Q responds first and halt.

val (v,b) = (P(x),false) | (Q(y),false) | ((x,y),true)
if b then R(x,y) else v

Problem 4#

The original problem. Abbreviate Special and Normal by S and N.

val (v,b) =   x >> Rtimer(d) >> (S(x), false)
            | y >> Rtimer(d) >> (S(y), false)
            | ((x,y), true)
if b then N(x,y) else v

Correctness#

To see the correctness of the solution in problem 4, we do a case analysis.

  • x is available before y: we consider three cases.
    • y never becomes available: then (v,b) are set to (S(x), false), and S(x) is published.
    • y becomes available within time d (of the availability of x): then (v,b) are set to ((x,y), true), neither S(x) nor S(y) is called, and the published value is N(x,y).
    • y becomes available after time d: Then S(x) is called. We consider two cases.
      • S(x) becomes available before y becomes available: then N(x,y) is not called, and S(x) is published.
      • S(x) is not available when y becomes available: then (v,b) are set to ((x,y), true), S(x) is ignored if and when it is received, and the published value is N(x,y).
  • y is available before x: similar to the first case.
  • neither x nor y ever become available: no site is called and there is no publication.

The proof relies on the semantics of Orc in which publication and tuple construction happen instantaneously. Thus, even for very small values of d, say 1, publication and tuple construction will occur before Rtimer(d) responds.

Problem 5#

We consider a variation of the problem in which time values are not used explicitly. S(x) is called if input x is received first, and S(y) is called if y is received first. Assume for discussion that x is received first and S(x) is called. If y is received before the response from S(x) is received, then N(x,y) is called and its response is published; otherwise, the response from S(x) is published.

val c = x >> true | y >> false
val (v,b) =   if( c) >> (S(x), false)
            | if(~c) >> (S(y), false)
            | ((x,y), true)
if b then N(x,y) else v

In this case, c decides which of S(x) or S(y) should be called based on whether x or y was available first.

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-9) was last changed on 16-May-2009 10:49 by AdrianQuark