# Count number of ways in which atomic operation(s) of n different processes can be interleaved 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. Posted on Categories proxies