Modeling a set of probabilistic concurrent processes

Question

I'm looking into discrete-time Markov chains (DTMCs) for use in analyzing a probabilistic consensus protocol. One basic thing I haven't been able to figure out is how to model a set of independent processes: consider $N$ processes. These processes will concurrently execute a series of identical instructions labeled $0, 1, 2, 3,$ etc. and all are starting in instruction $0$. When probability is not involved, modeling this is simple: it's a state machine which branches nondeterministically off the start state to $N$ different states, where in each of those $N$ states a different process was the first to execute instruction $0$. What do we do when probability is involved? Do we do the same thing with $N$ states branching from the start state, where the probability of transitioning to each state is $\frac{1}{N}$? As in, it's uniformly random which process was the first one to execute instruction $0$?

Is this like taking the product of the state machines of each process?

I'm using a DTMC here, would I gain anything by moving to a CTMC if I don't care about anything beyond the global order of execution?

Bonus question: assigning probabilities to whichever action is taken first seems like a generalization of the non-probabilistic notion of fairness; if it is, what is the formal definition of this generalized notion of probabilistic fairness?

Answer 1

I will again refer to a lecture by Prof. Katoen.

What you need here is a way of combining the DTMCs. The problem is, that a combination of DTMCs does not give you a new DTMC. This is because you want to model the choice which of the $N$ processes proceeds nondeterministically. That is, you don't know anything about which process executes the next instruction.

For this, you have a new kind of probabilistic system - Markov Decision Processes (MDPs). In an MDP, you first choose which action in a state you will take. This action enables a probabilistic distribution (similar to DTMCs) which determines the probability of the next state. Notice that an MDP reduces essentially to a DTMC when only one action is always possible.

So to model your $N$ processes, you would combine their DTMCs, let's say $D_i$ into an MDP where states are of the form $\langle p_1, p_2, \ldots, p_n \rangle $ and in each state there are $N$ actions, denoted $\alpha_i$. If you take action $\alpha_i$, then you go to a state where only $p_i$ changes to $p_i^\prime$ according to the distribution of the process $i$. This way you compose your $N$ processes into one single system very similarly to making a product of state machines.

To analyze the resulting MDP, you can resolve the nondeterminism by all sorts of schedulers. But that this I think out of scope. Nevertheless, you could use a uniformly randomized scheduler as you hinted in you question - then every action is selected with a uniform probability.

Answer 2

One approach is to model it as a composition of $N+1$ processes: a scheduler process, plus your $N$ basic processes. At each time step, the scheduler process selects which basic process will execute next. Your scheduler could be randomized: for instance, at each time step, it could choose which basic process to execute next uniformly at random, if you wanted.

Now the transitions of the entire system, and their probabilities, should be easy to derive. A state of the system is of the form $\langle s_0,s_1,\dots,s_N \rangle$ where $s_0$ is the state of the scheduler and $s_i$ is the state of the $i$th basic process. Each transition might have the form $\langle s_0,\dots,s_N \rangle \to \langle s'_0,s_1,\dots,s_{i-1},s'_i,s_{i+1},\dots,s_N \rangle$ (where $i$ is a deterministic function of $s_0$, and with probability given by the probability of $s_0 \to s'_0$ in the scheduler multiplied by the probability of $s_i \to s'_i$ in the $i$th basic process).

There are probably other ways to model it as well, maybe better ones for all I know. This is just one possibility that occurs to me.