.png){kind=icon}
.png){kind=icon}
Return
Robust network supercornputing with unreliable workers
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2014.10.002.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Internet supercomputing is becoming a powerful tool for harnessing massive amounts of computational resources. However in typical master-worker settings the correctness of the results of the computation crucially relies on the ability of the master to depend on the computation performed by the workers. We consider a distributed system consisting of a master process and a collection of synchronous worker processes that can execute tasks on behalf of the master and that may act nefariously by deliberately returning fallacious results. The master decides on the correctness of the results by assigning the same task to several workers. For such a setting with n processes and t tasks we study the problem of collectively performing the tasks under two different failure models: model-F-a, where some fraction f of workers that are prone to returning arbitrary (e.g., incorrect) results and the probability p of such faulty behavior are not known a priori to the master, and model F-b when these quantities are known to the master. Previous works assume that the number of faulty processes or the probability of a process acting maliciously is known to the master, e.g., as in model F-b. In this paper this assumption is removed in model F-a. First, for model F-a we provide an efficient algorithm-based on the Stopping Rule Algorithm by Dagum et al. (1995)- that can estimate f and p with (is an element of, delta)-approximation, for any 0 < delta < 1 and is an element of > 0. We also provide a randomized algorithm for detecting the faulty processes for model F-a. Finally, we provide algorithms to perform t tasks, with n workers, in models F-a and F-b. (C) 2014 Elsevier Inc. All rights reserved.
Keywords:
Distributed algorithms
Fault-tolerance
Randomized algorithms
Reliability
Internet supercomputing
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K