Dynamic composition constructs

["Gerald Hilderink" <g.h.hilderink@xxxxxxxxxxxxx>]

A DYN PAR could be a PAR or a PRI PAR on which the parent process can add,
remove or insert a process at run-time before running the DYN PAR.

In CTJ the PAR (Parallel), PRI PAR (PriParallel), SEQ (Sequential), ALT
(Alternative-Guard) and PRI ALT (PriAlternative-Guard) constructs are all
dynamic constructs. Without discussing the Java implementation I will try to
illustrate the idea by the following examples.

One can add, remove or insert processes by special methods (or by special
operators):
- adding process P4:   (P1 || P2 || P3).add(P4)          = (P1 || P2 || P3
|| P4)
- removing process P2: (P1 || P2 || P3 || P4).remove(P2) = (P1 || P3 || P4)
  or using index:      (P1 || P2 || P3 || P4).remove(1)  = (P1 || P3 || P4)
- inserting process P2 before P4 at index 2 (index = [0..2]): (P1 || P3 ||
P4).insert(P2,2) = (P1 || P3 || P2 || P4)

Example:
~~~~~~~~
For example PROCESS is a process,

PROCESS =	(P1 |<| P2 |<| P3 |<| P4)
EXAMPLE =	(PROCESS.remove(P1) ; PROCESS.add(P1) ; PROCESS.remove(P3) ;
PROCESS.insert(P3,0) ; PROCESS)	(*)

the result will be shown in steps,

PROCESS = 	(P2 |<| P3 |<| P4)            (step 1)
PROCESS = 	(P2 |<| P3 |<| P4 |<| P1)     (step 2)
PROCESS = 	(P2 |<| P4 |<| P1)            (step 3)
PROCESS = 	(P3 |<| P2 |<| P4 |<| P1)     (step 4, final result)

Moving processes is changing priorities:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Processes could be moved from one location to the other (from a to b) by the
move(a,b) method.

PROCESS.move(a,b) =	(p = PROCESS.at(a) ; PROCESS.remove(p) ;
PROCESS.insert(p, b))
with a > b.

PROCESS.move(a,b) =	(p = PROCESS.at(b) ; PROCESS.remove(p) ;
PROCESS.insert(p, a))
with a < b.

PROCESS.move(a,b) =	SKIP
with a = b.

The method PROCESS.at(i) returns the process at index i in PROCESS. The
indexes a and b are positive integer value ([0..>).

Problem when executing these special methods in parallel:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Executing these special methods in parallel may result in illegal results,
for example:

PROCESS =	(P1 |<| P2 |<| P3 |<| P4)
EXAMPLE =	((PROCESS.insert(P5,1) || PROCESS.insert(P6,1)) ; PROCESS)	(**)
the result will be
PROCESS =	(P1 |<| P5 |<| P6 |<| P2 |<| P3 |<| P4)
or
PROCESS =	(P1 |<| P6 |<| P5 |<| P2 |<| P3 |<| P4)

Solution for Java
~~~~~~~~~~~~~~~~~
The imposed restriction is that only the parent process may invoke these
methods on PROCESS in sequence where construct (*) is valid and construct
(**) is invalid.

The passive process interface for a Java process is
void run()
void add(process)
void remove(process)
void insert(process, index)
void move(index_from, index_to)

The parent process can never add, remove, insert or move a process when
PROCESS is running. The action (PROCESS.add(Px) || PROCESS) is not allowed
because when PROCESS is running then the parent process is blocked. Other
processes are *not* allowed to have a reference to PROCESS. By following
this simple rule makes this technique in Java secure.

General
~~~~~~~
This technique also applies for the other constructs:
- PAR construct:     (P1 || P2 || P3).add(P4)   = (P1 || P2 || P3 || P4)
- SEQ construct:     (P1 ; P2 ; P3).add(P4)     = (P1 ; P2 ; P3 ; P4)
- ALT construct:     (P1 [] P2 [] P3).add(P4)   = (P1 [] P2 [] P3 [] P4)
- PRI ALT construct: (P1 [<] P2 [<] P3).add(P4) = (P1 [<] P2 [<] P3 [<] P4)

PROCESS.insert(p) on a PAR or ALT construct is equal to PROCESS.add(p).

A nice result of this technique is that processes itself have no priorities.
One simply manipulates priorities by changing the places of processes in the
array of processes (referred by their indexes). Indexes do not necessary
represent the priority number of processes on composition constructs in
general.

Gerald.