Decentralized Network Supercomputing in the Presence of Malicious and Crash-Prone Workers

摘要

Internet supercomputing is an approach to solving parti-tionable, computation-intensive problems by harnessing the power of a vast number of interconnected computers. For the problem of using network supercomputing to perform a large collection of independent tasks, our prior work introduced the decentralized approach, and provided a synchronous algorithm that is able to perform all tasks with high probability (whp), while dealing with malicious behaviors under a rather strong assumption that the average probability of live (non-crashed) processors returning bogus results remains inferior to 1/2 during the computation. There the adversary is severely limited in its ability to crash processors that normally ret urn correct results. This work develops an efficient synchronous decentralized algorithm that is able to deal with a much stronger adversary. We consider a failure model with crashes, where given the initial set of processors P, an adversary is able to crash any subset F of processors, where ∣F∣ ≤ f·n, for a constant f (0 ＜ f ＜ 1), under the constraint that there exists a subset H ≤ P - F, with ∣H∣ = Ω(n), called the hardened set, such that the average probability of a processor in H returning a bogus result is inferior to 1/2. Here any processor may return bogus results, and H may be much smaller than P - F, while the average probability of processors in P - F returning a bogus result may be greater than 1/2. We develop an efficient randomized algorithm for n processors and t tasks (n ≤ t), where each live processor is able to determine locally when all tasks are performed, and obtain the results of all tasks. We prove that in Θ(t/n log n) rounds all live workers know the results of all tasks whp, and that these results are correct whp. The work complexity of the algorithm is Θ(t log n), the message complexity is Θ(t log n), and the bit complexity is Ο(tn log~3 n)).