PROBLEM: Count the number of ways in which atomic operation(s) of n different processes can be interleaved. A process may crash mid way before completion.
Suppose there are a total of n different processes - P1, P2, P3 .... , Pn.
Each process can have a variable number of atomic operation(s) that constitutes that process, but it should have at least one operation.
EXAMPLE
Consider two processes, P1 and P2
- P1: 1o1; 1o2; 1o3; 1o4; 1o5; 1o6;
- P2: 2o1; 2o2; 2o3;
where 1o1 denotes first operation of process P1.
Attempt:
Fix position of all operations of process P1, then count the number of ways in which the operations of process P2 can be placed in empty positions( __ ) created between operations of process P1, as shown below:
__ 1o1 __ 1o2 __ 1o3 __ 1o4 __ 1o5 __ 1o6 __There are seven empty positions numbered 1 to 7.
Counting: (Note that the numbers below (like 1 2 3) denote the empty position number.)
> Case1: When all three operations of P2 are placed in consecutive empty positions.
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
We have a total of 5 ordering possible for empty positions.
> Case2: When operations of P2 are placed in two consecutive empty positions taken together.
1 2 3 2 3 4 3 4 5 4 5 6 5 6 7
1 2 4 2 3 5 3 4 6 4 5 7
1 2 5 2 3 6 3 4 7
1 2 6 2 3 7
1 2 7
First cell in every column has already been counted in previous case. We have a total
of (5 - 1) + (4 - 1) + (3 - 1) + (2 - 1) + (1 - 1) = 10 ordering possible for empty
positions.
A similar argument can be made for last two consecutive empty positions taken together,
that gives us a total of another 10 ordering possible for empty positions.
> Case3: These are those cases that do not have empty positions numbered 8 and 9 for them.
6 7 8
7 8 9
> Case4: When operations may crash mid way before completion.
An 'x' denotes position where a crash is possible and process (here P2) terminates.
1x 2x 3
2x 3x 4
3x 4x 5
4x 5x 6
5x 6x 7
6x 7x 8
7x 8x 9
There is a total of 14 'x's possible.
Note: I have not put a cross after last empty position number because I am assuming that
a process will complete at this stage. You may correct my assumption if this is
wrong and should not be assumed in the first place.
Adding all 4 cases: 5 + 2*10 + 2 + 14 = 41. There are 41 possible ways to interleave operations processes P1 and P2.
As you can see, counting like this is cumbersome and error prone. I have missed cases.
How can this counting problem be generalised? Please see the problem statement at the top of the question.
