Algorithmic mechanisms for internet-based master-worker computing with untrusted and selfish workers
| Autor: | Fernández Anta, Antonio, Georgiou, Chryssis, Mosteiro, Miguel A. |
|---|---|
| Přispěvatelé: | Georgiou, Chryssis [0000-0003-4360-0260], Fernández Anta, Antonio [0000-0001-6501-2377] |
| Rok vydání: | 2010 |
| Předmět: |
Super computing
Theoretical computer science Computer science Distributed parameter networks Master processor computer.software_genre Task (project management) Master-worker applications Set (psychology) Game theory Task executions Stochastic distribution Internet Algorithmic mechanism business.industry Internet-based computing Rational Supercomputer Task execution Altruistic and malicious processors Incentive Grid computing Internet based computing Internet based Machine design Computational task The Internet Volunteering computing Distributed Computing business computer Algorithms |
| Zdroj: | IPDPS Proceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2010 24th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2010 |
| DOI: | 10.1109/ipdps.2010.5470409 |
| Popis: | We consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of untrusted worker processors, and collects their responses examples of such computations are the "@home" projects such as SETI. Prior work dealing with Internet-based task computations has either considered only rational, or only malicious and altruistic workers. Altruistic workers always return the correct result of the task, malicious workers always return an incorrect result, and rational workers act based on their self-interest. However, in a massive computation platform, such as the Internet, it is expected that all three type of workers coexist. Therefore, in this work we study Internet-based master-worker computations in the presence of Malicious, Altruistic, and Rational workers. A stochastic distribution of the workers over the three types is assumed. Considering all the three types of workers renders a combination of game-theoretic and classical distributed computing approaches to the design of mechanisms for reliable Internet-based computing. Indeed, in this work, such an algorithmic mechanism that makes use of realistic incentives to obtain the correct task result with a parametrized probability is designed. Only when necessary, the incentives are used to force the rational players to a certain equilibrium (which forces the workers to be truthful) that overcomes the attempts of the malicious workers to deceive the master. Finally, the mechanism is analyzed in two realistic Internet-based master-worker applications. This work is an example of how game theory can be used as a tool to formalize and solve a practical Distributed Computing problem such as Internet super computing. ©2010 IEEE. Conference code: 80843 Cited By :12 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|