Toward Maximizing the Quality of Results of Dependent Tasks Computed Unreliably
| Autor: | Li Gao, Grzegorz Malewicz |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Mathematical optimization
Optimization problem Computer science Computation Reliability (computer networking) media_common.quotation_subject Expected value Theoretical Computer Science Task (project management) Constraint (information theory) Computational Theory and Mathematics Theory of computation Quality (business) media_common |
| Zdroj: | Theory of Computing Systems. 41:731-752 |
| ISSN: | 1433-0490 1432-4350 |
| Popis: | This paper studies the problem of maximizing the number of correct results of dependent tasks computed unreliably. We consider a distributed system composed of a reliable server that coordinates the computation of a massive number of unreliable workers. Any worker computes correctly with probability p < 1. Any incorrectly computed task corrupts all dependent tasks. The goal is to determine which tasks should be computed by the (reliable) server and which by the (unreliable) workers, and when, so as to maximize the expected number of correct results, under a constraint d on the computation time. This problem is motivated by distributed computing applications that persist partial results of computations for future use in other computations and that want to ensure that the persisted results are of high quality. We show that this optimization problem is NP-hard. Then we study optimal scheduling solutions for the mesh with the tightest deadline. We present combinatorial arguments that describe all optimal solutions for two ranges of values of worker reliability p, when p is close to zero and when p is close to one. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|