Restricted Or-Parallelism:

extends the notion of independent or-parallelism, by allowing parallel execution of alternatives accessing unbound conditional variables. The restriction imposed is that no conflicts should occur on such variables. This translates to the fact that either: (i) the conditional variables are read and not written; or (ii) conditional variables instantiated along one alternative are not actually used by the other alternatives (i.e. the dependency is only apparent).

The concept of restricted or-parallelism could be pushed to the limit, allowing parallel execution of alternatives capable of binding the same conditional variables, as long as (i) the bindings are consistent, that is the same value is assigned to the conditional variable across the different alternatives; (ii) the execution of the alternatives is time-insensitive with respect to the bindings to the conditional variables.

Figure 5 illustrates an example of restricted or-parallelism. It is important to observe that

• the binding to X does not affect the computation of the first alternative;
• the binding to Y is deterministic (i.e., both the alternative assign the same value) and it is not time-sensitive (i.e., the computation will not change depending on which of the two alternatives binds Y first).

  
Figure 5: Restricted Or-Parallelism

At the implementation level, little more than independent or-parallelism is required to support restricted or-parallelism. The only relevant addition is related to the possibility of concurrent accesses to the same objects: accesses to conditional variables should be treated as critical sections, guaranteeing mutual exclusion.

The notion of restricted or-parallelism, to our knowledge, has not be practically explored in any system.