ANALYSIS OF THE SPURIOUS BEHAVIOR OF ASYNCHRONOUS RELAXATION ALGORITHMS

An analysis is presented of the dynamic responses of nonlinear asynchr onous iterations in multiprocessors in terms of the delays and the rel axation parameters. The actual distributed implementation is simulated , for analytical purposes, by means of systems of nonlinear difference equations. Local and global stability analyses of these systems are u sed to reveal the rich dynamical behavior of chaotic relaxations in th e presence of nonlinearities and nonconvexities. We show the effect of the delays and relaxation parameters in the topology of the basins of attraction of different equilibrium points by constructing appropriat e Lyapunov functions. The occurrence of bifurcation phenomena leading to chaotic behavior is shown. Finally, we study the phenomenon of the appearance of metastable equilibrium points, as functions of the commu nicational delays among the different processors.