|
Published Articles >> Table of Contents >> Abstract
1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96)
p. 168
An Algorithm for Detecting Termination of Distributed Computation in Arbitrary Network Topologies within Linear Time
Hengming Zou, AT&T Bell Laboratories
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1996.508977
Send link to a friend
| Abstract |
|
To determine if a distributed process has terminated is very important. Several algorithms have been proposed for this purpose since early 1980s. Unfortunately, most of these algorithms assume a logical ring structure on network topology. Thinking that in order to form a logical ring, one may need either include some channels in a logical ring for more than once or physically add some extra channels to a network if the network itself does not physically form a ring, it is obvious to see that these algorithms may increase network expenses.This paper proposed a two-phase algorithm which does not require a logical ring topology, thus eliminating both multiple use of some channels in a logical ring and introduction of extra channels to a network. The algorithm can be finished in O(D+M) time in the worst case, here D denotes the distance of the network, M denotes the number of computation messages occurring during the execution of the algorithm. The message complexity of this algorithm for each successful detection is O(E+M), here E denotes the number of edges in the network.
|
 Additional Information
|
Index Terms- active, algorithm, distributed process, message, passive, predicate, termination Parallelization of Scheduling Algorithms
Citation:
Hengming Zou,
"An Algorithm for Detecting Termination of Distributed Computation in Arbitrary Network Topologies within Linear Time,"
ispan,
p. 168,
1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96),
1996
|
|
