As traditional one-processor machines have limited computational resources, and powerful parallel machines are very expensive to obtain and maintain, the Internet is emerging as the computational platform of choice for processing complex computational jobs. Several Internet-based systems and protocols have been designed to operate on top of this global computation infrastructure (e.g., Grid systems, "@home" projects such as SETI). Although the potential is great, the use of Internet-based computing is limited by the selfish or untrustworthy nature of the platform's components.
We consider Master-Worker Internet-based computations where a master processor assigns tasks, over the Internet, to a set of workers to compute and return the task result. The workers are not trustworhty and might decide to forge the result of the task either due to their self-interest (they may obtain more benefit from not collaborating) or due to malice (they simply want to harm the outcome of the computation - a virus, for example). The design objective is for the master to obtain the correct task result while minimizing its cost. During this research we first plan to design a theoretical framework that would enable us to investigate the foundations, principles, feasibility, and cost-reliability tradeoffs of Master-Worker Internet-based computing. In this research we will also design algorithmic mechanisms within the developed framework that will be able to guarantee (under certain conditions) that rational (selfish) nodes have incentives to collaborate with the master (that is, to truthfully compute and return the correct task result), and at the same time, alleviate the negative impact of malicious nodes' actions. This will involve the development of new techniques that will combine game-theoretic with traditional distributed computing approaches. Finally, we will analyse the feasibility of the techniques and algorithms developed on realistic Master-Worker Internet-based applications such as SETI@home.