OrcWiki: ExtendedParallelOr
https://orc.csres.utexas.edu/wiki/
The Orc programming language project wiki (wiki changes feed)en-usJSPWiki 2.10.2
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=9
ExtendedParallelOr, version 9AdrianQuark changed this page on Sat May 16 10:49:46 CDT 2009:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 47 changed 2 lines</td></tr>
<tr><td class="diffrem">val (v,b) = x >> Rtimer(1) >> (S(x), false)</td></tr>
<tr><td class="diffrem"> | y >> Rtimer(1) >> (S(y), false)</td></tr>
<tr><td class="diffadd">val (v,b) = x >> Rtimer(d) >> (S(x), false)</td></tr>
<tr><td class="diffadd"> | y >> Rtimer(d) >> (S(y), false)</td></tr>
<tr><td class="diff">At line 66 changed one line</td></tr>
<tr><td class="diffrem">This proof relies on the subtle fact that {{Rtimer}} site returns have lower priority than other events like publication and tuple construction. If this were not the case and both {{x}} and {{y}} became available, it would be possible for both calls to {{S}} to be made before {{((x,y), true)}} publishes, violating the specification.</td></tr>
<tr><td class="diffadd">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.</td></tr>
<tr><td class="diff">At line 68 changed one line</td></tr>
<tr><td class="diffrem">!! Alternate Solution</td></tr>
<tr><td class="diffadd">!! Problem 5</td></tr>
<tr><td class="diff">At line 70 changed one line</td></tr>
<tr><td class="diffrem">A slightly more complex solution which does not use {{Rtimer}} is also possible:</td></tr>
<tr><td class="diffadd">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.</td></tr>
</table>Sat, 16 May 2009 15:49:46 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=8
ExtendedParallelOr, version 8AdrianQuark changed this page on Wed May 06 20:00:49 CDT 2009:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 72 changed one line</td></tr>
<tr><td class="diffrem">[{orc</td></tr>
<tr><td class="diffadd">[{orc runnable='false'</td></tr>
</table>Thu, 07 May 2009 01:00:49 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=7
ExtendedParallelOr, version 7AdrianQuark changed this page on Wed May 06 20:00:27 CDT 2009:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 70 changed one line</td></tr>
<tr><td class="diffrem">An alternative (but slightly more complex) solution which does not use {{Rtimer}} is also possible:</td></tr>
<tr><td class="diffadd">A slightly more complex solution which does not use {{Rtimer}} is also possible:</td></tr>
</table>Thu, 07 May 2009 01:00:27 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=6
ExtendedParallelOr, version 6AdrianQuark changed this page on Wed May 06 19:59:51 CDT 2009:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 1 added 2 lines</td></tr>
<tr><td class="diffadd">!! Introduction</td></tr>
<tr><td class="diffadd"></td></tr>
</table>Thu, 07 May 2009 00:59:51 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=5
ExtendedParallelOr, version 5AdrianQuark changed this page on Wed May 06 19:59:04 CDT 2009:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 76 changed one line</td></tr>
<tr><td class="diffrem">if b then R(x,y) else v</td></tr>
<tr><td class="diffadd">if b then N(x,y) else v</td></tr>
<tr><td class="diff">At line 78 added 2 lines</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">In this case, {{c}} decides which of {{S(x)}} or {{S(y)}} should be called based on whether {{x}} or {{y}} was available first.</td></tr>
</table>Thu, 07 May 2009 00:59:04 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=4
ExtendedParallelOr, version 4AdrianQuark changed this page on Wed May 06 19:57:18 CDT 2009:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 64 changed one line</td></tr>
<tr><td class="diffrem">This solution relies on the subtle fact that {{Rtimer}} site returns have lower priority than other events like publication and tuple construction. Otherwise, if both {{x}} and {{y}} become available, it would be possible for both calls to {{S}} to be made before {{((x,y), true)}} publishes, violating the problem specification.</td></tr>
<tr><td class="diffadd">This proof relies on the subtle fact that {{Rtimer}} site returns have lower priority than other events like publication and tuple construction. If this were not the case and both {{x}} and {{y}} became available, it would be possible for both calls to {{S}} to be made before {{((x,y), true)}} publishes, violating the specification.</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">!! Alternate Solution</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">An alternative (but slightly more complex) solution which does not use {{Rtimer}} is also possible:</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">[{orc</td></tr>
<tr><td class="diffadd"></td></tr>
<tr><td class="diffadd">val c = x >> true | y >> false</td></tr>
<tr><td class="diffadd">val (v,b) = if( c) >> (S(x), false)</td></tr>
<tr><td class="diffadd"> | if(~c) >> (S(y), false)</td></tr>
<tr><td class="diffadd"> | ((x,y), true)</td></tr>
<tr><td class="diffadd">if b then R(x,y) else v</td></tr>
<tr><td class="diffadd">}]</td></tr>
</table>Thu, 07 May 2009 00:57:18 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=3
ExtendedParallelOr, version 3AdrianQuark changed this page on Wed May 06 17:42:43 CDT 2009:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 64 changed one line</td></tr>
<tr><td class="diffrem">This solution relies on the subtle fact that {{Rtimer}} site returns have lower priority than other events like publication and tuple construction. Otherwise, if both {{x}} and {{y}} become available, it would be possible for both calls to {{S}} to be made before {{((x,y), true)}} publish, violating the problem specification.</td></tr>
<tr><td class="diffadd">This solution relies on the subtle fact that {{Rtimer}} site returns have lower priority than other events like publication and tuple construction. Otherwise, if both {{x}} and {{y}} become available, it would be possible for both calls to {{S}} to be made before {{((x,y), true)}} publishes, violating the problem specification.</td></tr>
</table>Wed, 06 May 2009 22:42:43 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=2
ExtendedParallelOr, version 2AdrianQuark changed this page on Wed May 06 17:42:13 CDT 2009:<br /><hr /><br /><table class="diff" border="0" cellspacing="0" cellpadding="0">
<tr><td class="diff">At line 9 changed one line</td></tr>
<tr><td class="diffrem">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. Publish {{Q(y)}} if {{Q(y)}} has been called, and {{P(x)}} only if {{Q(y)}} has not been called.</td></tr>
<tr><td class="diffadd">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)}}.</td></tr>
<tr><td class="diff">At line 30 changed one line</td></tr>
<tr><td class="diffrem">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.</td></tr>
<tr><td class="diffadd">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.</td></tr>
</table>Wed, 06 May 2009 22:42:13 GMT
https://orc.csres.utexas.edu/wiki/Wiki.jsp?page=ExtendedParallelOr&version=1
ExtendedParallelOr, version 1AdrianQuark created this page on Wed May 06 17:32:40 CDT 2009:<br /><hr /><br /><h3 id="section-ExtendedParallelOr-Introduction"> Introduction<a class="hashlink" href="#section-ExtendedParallelOr-Introduction">#</a></h3>
<p>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.
</p>
<p>To set the context for the problem, consider asking two airlines, sites <tt>A()</tt> and <tt>B()</tt>, for quotes. Normally, we expect the quotes <tt>x</tt> from <tt>A()</tt> and <tt>y</tt> from <tt>B()</tt>, to arrive relatively quickly, and then we call <tt>Normal(x,y)</tt> 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 <tt>Special(x)</tt> if <tt>x</tt> is available (or <tt>Special(y)</tt> if <tt>y</tt> becomes available). To avoid race conditions, we wait for a short amount of time, <tt>d</tt>, after the first quote, say <tt>x</tt>, becomes available. If <tt>y</tt> becomes available within this time window, we call <tt>Normal(x,y)</tt>. If <tt>y</tt> does not become available, we call <tt>Special(x)</tt>, but we still wait to receive <tt>y</tt>. If <tt>y</tt> becomes available before <tt>Special(x)</tt> responds, we call <tt>Normal(x,y)</tt> and use its response (ignoring any response from <tt>Special(x)</tt>). If <tt>y</tt> is received after <tt>Special(x)</tt> responds, the response from <tt>Special(x)</tt> is published and <tt>y</tt> is ignored.
</p>
<p>Observe from the specification that both <tt>Special(x)</tt> and <tt>Special(y)</tt> would not be called, because <tt>Normal(x,y)</tt> could have been called after both <tt>x</tt> and <tt>y</tt> become available. We first consider some variations.
</p>
<h3 id="section-ExtendedParallelOr-Problem1"> Problem 1<a class="hashlink" href="#section-ExtendedParallelOr-Problem1">#</a></h3>
<p>Priority of <tt>y</tt> over <tt>x</tt>. Given <tt>x</tt> and <tt>y</tt> as before, call <tt>P(x)</tt> and <tt>Q(y)</tt> as soon as <tt>x</tt> and <tt>y</tt> become available. If <tt>P(x)</tt> returns a value before <tt>Q(y)</tt> has been called, publish that value and halt. Otherwise, publish only the value of <tt>Q(y)</tt>.
</p>
<p><div><script src="/orchard/orc.js" type="text/javascript"></script>
<link rel="stylesheet" type="text/css" href="/orchard/orc.css" media="screen"/><script type="text/javascript">function orcSpoiler(a) {var $a = jQuery(a);var $orc = $a.next();$orc.css('display', 'none');$orc.css('visibility', 'visible');$orc.css('position', 'static');$orc.slideDown();$a.hide();}</script><pre class="orc-snippet">val (v,b) = (P(x),false) | (y,true)
if b then Q(y) else v</pre></div>
</p>
<h3 id="section-ExtendedParallelOr-Problem2"> Problem 2<a class="hashlink" href="#section-ExtendedParallelOr-Problem2">#</a></h3>
<p>Same as problem 1, but additionally, <tt>P</tt> should not be called if <tt>y</tt> is available before <tt>x</tt>.
</p>
<p><div><pre class="orc-snippet">val c = x >> false | y >> true
if c then Q(y)
else {- Solution to Problem 1 -}</pre></div>
</p>
<h3 id="section-ExtendedParallelOr-Problem3"> Problem 3<a class="hashlink" href="#section-ExtendedParallelOr-Problem3">#</a></h3>
<p>Call <tt>P</tt>, <tt>Q</tt> and <tt>R</tt> when <tt>x</tt>, <tt>y</tt> or <tt>(x,y)</tt> become available. If <tt>R</tt> has been called, take its response. Else, publish whichever of <tt>P</tt> or <tt>Q</tt> responds first and halt.
</p>
<p><div><pre class="orc-snippet">val (v,b) = (P(x),false) | (Q(y),false) | ((x,y),true)
if b then R(x,y) else v</pre></div>
</p>
<p />
<h3 id="section-ExtendedParallelOr-Problem4"> Problem 4<a class="hashlink" href="#section-ExtendedParallelOr-Problem4">#</a></h3>
<p>The original problem. Abbreviate <tt>Special</tt> and <tt>Normal</tt> by <tt>S</tt> and <tt>N</tt>.
</p>
<p><div><pre class="orc-snippet">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</pre></div>
</p>
<h3 id="section-ExtendedParallelOr-Correctness"> Correctness<a class="hashlink" href="#section-ExtendedParallelOr-Correctness">#</a></h3>
<p>To see the correctness of the solution in problem 4, we do a case analysis.
</p>
<ul><li><tt>x</tt> is available before <tt>y</tt>: we consider three cases.
<ul><li><tt>y</tt> never becomes available: then <tt>(v,b)</tt> are set to <tt>(S(x), false)</tt>, and <tt>S(x)</tt> is published.
</li><li><tt>y</tt> becomes available within time <tt>d</tt> (of the availability of <tt>x</tt>): then <tt>(v,b)</tt> are set to <tt>((x,y), true)</tt>, neither <tt>S(x)</tt> nor <tt>S(y)</tt> is called, and the published value is <tt>N(x,y)</tt>.
</li><li><tt>y</tt> becomes available after time <tt>d</tt>: Then <tt>S(x)</tt> is called. We consider two cases.
<ul><li><tt>S(x)</tt> becomes available before <tt>y</tt> becomes available: then <tt>N(x,y)</tt> is not called, and <tt>S(x)</tt> is published.
</li><li><tt>S(x)</tt> is not available when <tt>y</tt> becomes available: then <tt>(v,b)</tt> are set to <tt>((x,y), true)</tt>, <tt>S(x)</tt> is ignored if and when it is received, and the published value is <tt>N(x,y)</tt>.
</li></ul></li></ul></li><li><tt>y</tt> is available before <tt>x</tt>: similar to the first case.
</li><li>neither <tt>x</tt> nor <tt>y</tt> ever become available: no site is called and there is no publication.
</li></ul><p>The proof relies on the semantics of Orc in which publication and tuple construction happen instantaneously. Thus, even for very small values of <tt>d</tt>, say 1, publication and tuple construction will occur before <tt>Rtimer(d)</tt> responds.
</p>
<h3 id="section-ExtendedParallelOr-Problem5"> Problem 5<a class="hashlink" href="#section-ExtendedParallelOr-Problem5">#</a></h3>
<p>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.
</p>
<p><div><pre class="orc-snippet">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</pre></div>
</p>
<p>In this case, <tt>c</tt> decides which of <tt>S(x)</tt> or <tt>S(y)</tt> should be called based on whether <tt>x</tt> or <tt>y</tt> was available first.
</p>Wed, 06 May 2009 22:32:40 GMT