Name
Abstract | ||
|---|---|---|
Traditional approaches to network supercomputing employ a master process and a large number of potentially undependable worker processes that must perform a collection of tasks on behalf of the master. In such a centralized scheme, the master process is a performance bottleneck and a single point of failure. This work develops an original approach that eliminates the master and instead uses a decentralized algorithm, where each worker is able to determine locally that all tasks have been performed, and to collect locally the results of all tasks. The failure model assumes that the average probability of a worker returning a wrong result is inferior to 1/2. A randomized synchronous algorithm for n processes and n tasks is presented. The algorithm terminates in Θ(log n) rounds, and it is proved that upon termination the workers know the results of all tasks with high probability, and that these results are correct with high probability. The message complexity of the algorithm is Θ(n log n), and the bit complexity is O(n2 log3 n). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1993806.1993860 | international conference on principles of distributed systems |
Keywords | DocType | Volume |
high probability,bit complexity,n log n,n logn,robust network,n process,log n,randomized synchronous algorithm,algorithm terminates,message complexity,n task,centralized control,average probability,master processor,n2 log3 n,decentralized algorithm,high rank,master process,distributed algorithm,randomized algorithm,fault tolerance,randomized algorithms,distributed algorithms,fault tolerant | Conference | 7109 |
ISSN | Citations | PageRank |
0302-9743 | 8 | 0.59 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Seda Davtyan | 1 | 50 | 7.99 |
| Kishori M. Konwar | 2 | 107 | 17.49 |
| Alexander A. Shvartsman | 3 | 766 | 58.27 |