Name
Abstract | ||
|---|---|---|
Termination detection is a fundamental problem in distributed computing. Many algorithms have been proposed, but only the S. Chandrasekaran and S. Venkatesan (CV) algorithm (1990) is known to be optimal in worst-case message complexity. This optimal algorithm, however, has several undesirable properties. First, it always requires M'+2* mod E mod +n-1 control messages, whether it is worst case or best case, where M' is the number of basic messages issued by the underlying computation after the algorithm starts, mod E mod is the number of channels in the system, and n is the number of processes. Second, its worst-case detection delay is O(M'). In a message-intensive computation, that might not be tolerable. Third, the maximum amount of space needed by each process is O(M'), a quantity not known at compile time, making it necessary to use the more expensive dynamic memory allocation. Last, it works only for FIFO channels. This paper remedies these drawbacks, while keeping its strength. The authors propose an algorithm that requires M'+2(n-1) control messages in the worst case, but much fewer on the average, and in the best case, it uses only 2(n-1) control messages, no matter how large M' is. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1109/IPPS.1992.222991 | IPPS |
Keywords | Field | DocType |
distributed algorithms,control systems,communication complexity,information science,switches,distributed computing,dynamic memory allocation | C dynamic memory allocation,FIFO (computing and electronics),Computer science,Compile time,Communication channel,Algorithm,Communication complexity,Distributed algorithm,Best, worst and average case,Computation | Conference |
ISBN | Citations | PageRank |
0-8186-2672-0 | 16 | 0.73 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ten-Hwang Lai | 1 | 1466 | 170.85 |
| Yu-Chee Tseng | 2 | 6603 | 639.67 |
| Xuefeng Dong | 3 | 76 | 7.24 |