Sufficient conditions for the convergence of asynchronous iterations (Q1118982)

Many systems may be modelled by a set of nonlinear equations. Such equations may be solved by writing them in the form \(x=F(x)\). Then, given an initial guess \(x^ 0\in {\mathbb{R}}^ n\), a fixed point iteration is \(x^{k+1}=F(x^ k).\) On a multiprocessor the form is written as \(x_ i=F_ i(x),\) \(i=1..n\), and a processor is assigned to each (or to several) \(F_ i(x)\). Since iteration \(k+1\) cannot start before iteration k is completed it seems that successive iterations require synchronization. However such synchronization leads to a serious impairment of algorithm performance [cf. \textit{T. S. Axelrod}, ibid. 3, 129-140 (1986)] so leading to the use of asynchronous algorithms. The convergence of such algorithms in the case \(x\in {\mathbb{R}}^ n\) has been given by \textit{G. M. Baudet} [J. Assoc. Comput. Machin. 25, 129-140 (1978; Zbl 0372.68015)]. In this paper the authors discuss the convergence of asynchronous algorithms in the more general case where the data may be discrete or symbolic. The final section gives an example of the discrete scene-labeling algorithm on a multiprocessor computer with distributed global memory.