Event Scheduled for May 9, 2012
Event: CSE & Principles of Computing & Knowledge Seminar: Chryssis Georgiou, University of Cyprus, Algorithmic Mechanisms for Reliable Master-Worker Internet-based Task Computing
Location: ITE 336
Time: 11:00 am
Details of Event:
We consider Internet-based master-worker computations, where a master processor assigns, across the Internet, computational tasks 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 (aiming in increasing their benefit) . 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. In addition, we consider the possibility that the communication between the master and the workers is not reliable, and that workers could be unavailable.
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.
In this talk I will present two algorithmic mechanisms that provide appropriate incentives to rational workers to act correctly, despite the malicious' workers actions and the unreliability of the network.
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 attempt of the malicious workers to deceive the master. Furthermore, I will discuss how these mechanisms can be analyzed in two realistic Internet-based master-worker settings, a SETI-like one and a contractor-based one, such as Amazon's Mechanical Turk. The analysis is complemented with plots that illustrate the trade-offs between reliability and cost, under different system parameters.
This is a joint work with Evgenia Christoforou, Antonio Fernandez Anta and Miguel Mosteiro and it is part of a research project supported by the Cyprus Research Promotion Foundation grant ΤΠΕ/ΠΛΗΡΟ/0609(ΒΕ)/05
Sponsored By: Computer Science and Engineering
Pamphlet/Flyer: No Pamphlet/Flyer Available