Finite termination of asynchronous iterative algorithms Academic Article uri icon

abstract

  • We consider n-processor distributed systems where the ith processor executes asynchronously the iteration xi = fi(x). It is natural to terminate the iteration of the ith processor when some local condition, such as xi = fi(x): 'small', holds. However, local termination conditions of this type may not lead to global termination because of the asynchronous character of the algorithm. In this paper, we propose several approaches to modify the original algorithm and/or supplement it with an interprocessor communication protocol so that this difficulty does not arise. Some of the resulting procedures can be recast as termination detection schemes for arbitrary finite, distributed computations.

published proceedings

  • PARALLEL COMPUTING

author list (cited authors)

  • Savari, S. A., & Bertsekas, D. P.

citation count

  • 23

complete list of authors

  • Savari, SA||Bertsekas, DP

publication date

  • January 1996