Markov chains competing for transitions: application to large-scale distributed systems (Q352904)

This paper considers the parallel composition of many identical, but not necessarily independent, absorbing discrete-time Markov chains. A randomised scheduling policy is used to determine the Markov chain that performs the next transition. The central focus of the paper is to determine the first time at which one of the Markov chains reaches its absorbing state. The authors obtain the probability distribution as well as the expectation of this measure, and provide polynomial-time algorithms to obtain these quantities. Asymptotic results are obtained when the number of Markov chains goes to infinity. The results are applied to cluster merging and splitting in large distributed networks.