This project is concerned with the analysis, implementation and simulation of asynchronous algorithms. Asynchronous algorithms do not require synchronization and thus are particularly suitable for large-scale multiprocessors or massively parallel systems. Moreover, asynchronous algorithms are tolerant to processor and link failures and easily adapt to changes in parameters or sensor data in real-time embedded systems. The theoretical analysis of convergence considers models with stochastic delays. Asynchronous algorithms running on a multiprocessor are processes with random communication delays. With this approach complex problems such as the effects of random message delays due to variable load conditions in the interconnection network and the reliability issues related to probabilistic link or processor failures are easily analyzed. The approach is also applied to the analysis of problems in which the solution changes with time and of algorithms with good time-adaptation. Finally, the convergence of algorithms which are trapped in periodic orbits can be improved through randomization techniques. Six asynchronous algorithms with the above features are implemented on the Intel Touchstone DELTA machine accessible at Caltech. Extensive evaluation of each algorithm is performed in order to assess the effectiveness of asynchronous algorithms in the context of large-scale multiprocessor systems.
