1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

This is a classical combinatorics problem, where we view each operation in a process as indistinguishable. We can always label the $i$th operation as such after permuting all operations without distinguishing between the operations of a single process.

The number of different permutations of $n$ objects, where there are $n_1$ indistinguishable objects of the first kind, $n_2$ indistinguishable objects of the second, etc, is

$$\frac{n!}{n_1!n_2!\cdots n_k!}.$$

See e.g. this for a proof.


So in your example we find solution $\frac{9!}{6!3!} = 84$. Here are all 84 to confirm:

111111222
111112122
111112212
111112221
111121122
111121212
111121221
111122112
111122121
111122211
111211122
111211212
111211221
111212112
111212121
111212211
111221112
111221121
111221211
111222111
112111122
112111212
112111221
112112112
112112121
112112211
112121112
112121121
112121211
112122111
112211112
112211121
112211211
112212111
112221111
121111122
121111212
121111221
121112112
121112121
121112211
121121112
121121121
121121211
121122111
121211112
121211121
121211211
121212111
121221111
122111112
122111121
122111211
122112111
122121111
122211111
211111122
211111212
211111221
211112112
211112121
211112211
211121112
211121121
211121211
211122111
211211112
211211121
211211211
211212111
211221111
212111112
212111121
212111211
212112111
212121111
212211111
221111112
221111121
221111211
221112111
221121111
221211111
222111111
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.