!! 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)}}.

[{orc runnable='false'

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}}.

[{orc runnable='false'

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.

[{orc runnable='false'

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}}.

[{orc runnable='false'

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.

[{orc runnable='false'

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.