Convergence analysis of asynchronous linear iterations with stochastic delays (Q1208523)

A general linear model of asynchronous iterations, the communication delays of which are stochastic with Markovian character, is presented. The model permits static allocation of components to different processors in which each component gets assigned at the start of the algorithm to be updated by the same processor. For better load balancing among processors, dynamic allocation is employed in which the assignment of components may be changed with time. In an effort to elevate the level of tolerance to processor failure, the presented model also allows concurrent updating of the same component by several processors. It is allowed that the processors use their individual updates with a possible bounded delay. Sufficient conditions under which the model of asynchronous iterations converges in the second moment to the sought solution are provided. For the Markov case when the communication delays are independent, identically distributed, the authors provide sufficient conditions for convergence in the second moment and necessary and sufficient conditions for convergence in the mean.