TY - GEN
T1 - Convergence rate and termination of asynchronous iterative algorithms
AU - Bertsekas, Dimitri P.
AU - Tsitsiklis, John N.
N1 - Funding Information:
This paper deals with iterative algorithms of the form z := f(z), where z = (z~,...,z,) is a vector in ZIP and f : 3” I+ 8” is an iteration mapping defining the algorithm. In many interesting appli- Research supported by the NSF under Grants ECS-8519058 and ECS-8552419, with matching funds from Bellcore and DuPont, and by the AR0 under Grant DAAL03-86-K-0171.
Publisher Copyright:
© 1989 ACM.
PY - 1989/6/1
Y1 - 1989/6/1
N2 - We consider iterative algorithms of the form x:= f(x), executed by a parallel or distributed computing system. We focus on 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. We provide results on the convergence rate of such algorithms and make a comparison with the convergence rate of the corresponding synchronous methods in which the computation proceeds in phases. We also present results on how to terminate asynchronous iterations in finite time with an approximate solution of the computational problem under consideration.
AB - We consider iterative algorithms of the form x:= f(x), executed by a parallel or distributed computing system. We focus on 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. We provide results on the convergence rate of such algorithms and make a comparison with the convergence rate of the corresponding synchronous methods in which the computation proceeds in phases. We also present results on how to terminate asynchronous iterations in finite time with an approximate solution of the computational problem under consideration.
KW - Asynchronous algorithms
KW - Distributed algorithms
KW - Iterative methods
KW - Parallel algorithms
KW - Termination detection
UR - http://www.scopus.com/inward/record.url?scp=84883093816&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883093816&partnerID=8YFLogxK
U2 - 10.1145/318789.318894
DO - 10.1145/318789.318894
M3 - Conference contribution
AN - SCOPUS:84883093816
T3 - Proceedings of the International Conference on Supercomputing
SP - 461
EP - 470
BT - Proceedings of the 3rd International Conference on Supercomputing, ICS 1989
PB - Association for Computing Machinery
T2 - 3rd International Conference on Supercomputing, ICS 1989
Y2 - 5 June 1989 through 9 June 1989
ER -