TY - GEN
T1 - Brief announcement: decentralized network supercomputing in the presence of malicious and crash-prone workers.
T2 - 2012 ACM Symposium on Principles of Distributed Computing, PODC'12
AU - Davtyan, Seda
AU - Konwar, Kishori M.
AU - Shvartsman, Alexander A.
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2012
Y1 - 2012
N2 - Internet supercomputing is an approach to solving partitionable, 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 return 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 (0fH ⊆ 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 logn) 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 Θ(tlogn), the message complexity is Θ(nlogn ), and the bit complexity is O(tn log 3n).
AB - Internet supercomputing is an approach to solving partitionable, 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 return 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 (0fH ⊆ 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 logn) 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 Θ(tlogn), the message complexity is Θ(nlogn ), and the bit complexity is O(tn log 3n).
KW - communication
KW - distributed algorithms
KW - fault-tolerance
KW - internet supercomputing
KW - randomized algorithms
UR - http://www.scopus.com/inward/record.url?scp=84865012629&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865012629&partnerID=8YFLogxK
U2 - 10.1145/2332432.2332475
DO - 10.1145/2332432.2332475
M3 - Conference contribution
AN - SCOPUS:84865012629
SN - 9781450314503
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 231
EP - 232
BT - PODC'12 - Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing
Y2 - 16 July 2012 through 18 July 2012
ER -