Algorithmic mechanisms for internet-based master-worker computing with untrusted and selfish workers
SourceProceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2010
24th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2010
Google Scholar check
MetadataShow full item record
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 responsesexamples 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.
Showing items related by title, author, creator and subject.
Christoforou, Evgenia; Fernández Anta, Antonio; Georgiou, Chryssis; Mosteiro, Miguel A.; Sánchez, A. (2013)We consider Internet-based master-worker task computations, such as SETI@home, where a master process sends tasks, across the Internet, to worker processes
Samaras, George S.; Panayiotou, Christoforos (2002)The explosive growth of the Internet has fuelled the creation of new and exciting information services. Most of the current technology has been designed for desktop and larger computers with medium to high bandwidth and ...
Pallis, George C. (2012)As more aspects of our work and life move online and the Internet expands beyond a communication medium to become a platform for business and society, Content Delivery Networks (CDNs) have recently gained momentum in the ...