Finite termination of asynchronous iterative algorithms
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
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.
