## Abstract

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 ^{3}n).

Original language | English (US) |
---|---|

Title of host publication | PODC'12 - Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing |

Pages | 231-232 |

Number of pages | 2 |

DOIs | |

State | Published - 2012 |

Externally published | Yes |

Event | 2012 ACM Symposium on Principles of Distributed Computing, PODC'12 - Madeira, Portugal Duration: Jul 16 2012 → Jul 18 2012 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing |
---|

### Conference

Conference | 2012 ACM Symposium on Principles of Distributed Computing, PODC'12 |
---|---|

Country/Territory | Portugal |

City | Madeira |

Period | 7/16/12 → 7/18/12 |

## Keywords

- communication
- distributed algorithms
- fault-tolerance
- internet supercomputing
- randomized algorithms

## ASJC Scopus subject areas

- Software
- Hardware and Architecture
- Computer Networks and Communications