Distributed Asynchronous Algorithms

We consider iterative algorithms of the form x:= f(x), executed by a distributed network of processors. We first discuss a few possibilities for synchronous execution. We then consider asynchronous implementations whereby each processor iterates on a different component of x, at its own pace, using the most recently received (but possibly outdated) information on the remaining components of x. While certain algorithms may fail to converge when implemented asynchronously, a large number of positive convergence results is available. We classify asynchronous algorithms into three main categories, depending on the amount of asynchroniam they can tolerate and survey the corresponding convergence results.