Path: utzoo!attcan!uunet!husc6!purdue!gatech!hubcap!max
From: max@polya.stanford.edu (Max Hailperin)
Newsgroups: comp.parallel
Subject: Re: optimistic computation: what and wh
Summary: optimistic vs. speculative concurrency
Message-ID: <3530@hubcap.UUCP>
Date: 14 Nov 88 13:31:09 GMT
Sender: fpst@hubcap.UUCP
Lines: 31
Approved: parallel@hubcap.clemson.edu

Just to try to illucidate the question of optimistic/speculative
concurrency a bit, let me say that they are frequently distinguished
from one another (though they are indeed intimately related):

OPTIMISTIC means you ignore synchonization constraints, while keeping
an eye out for cases where this gets you in trouble.  For example, you
might read a variable without waiting to see if anyone at an earlier
logical time might write it.  When the write is done, the writer
checks whether an invalid read did indeed slip in, and if so rolls
back the reader.  All the work should be useful, except that it may be
computing using the wrong values.  This is used in some distributed
database systems.  It also is the essense of "Time Warp" discrete
event simulation.  It has been proposed for lisp evaluation by Morris
Katz ("ParaTran: A Transparent, Transaction Based Runtime Mechanism
for Parallel Execution of Scheme," MIT EECS Masters Thesis, June 1986)
and also by Tom Knight ("An Architecture for Mostly Functional
Languages," Proceedings of the 1986 ACM Symposium on Lisp and
Functional Programming, pp. 105-112).

SPECULATIVE concurrency means going down multiple branches of a
conditional while you figure out which one you really want.  This is
also allied to what the parallel logic programming community calls
"OR-parallelism," and with the notions of "competative concurrency"
and "sponsorship" in the actors field.  Both of these generalize on
it.  For example, suppose you want to evaluate the OR (or AND) of two
expressions: you can start evaluating them concurrently, and if either
returns TRUE (respectively FALSE), you can kill the other off.  (This
is sort of like the case with a conditional, only more symmetric.)

I hope this pedanticness benefited someone; I'm sure many of you know
this all as well as I do (or better) -- I was aiming this at those who don't.