close

The Department of Computer Science at the University of Cyprus cordially invites you to the Seminar entitled:

Algorithmic Mechanisms for Reliable Internet-based Master-Worker Computing

Speaker: Chryssis Georgiou and Evgenia Christoforou
Affiliation: University of Cyprus, Cyprus
Category: Seminar
Location: Room 146, Faculty of Pure and Applied Sciences (FST-01), 1 University Avenue, 2109 Nicosia, Cyprus (directions)
Date: Tuesday, October 30, 2012
Time: 18.00-20.00 EET
Host: Chryssis Georgiou (chryssis-AT-cs.ucy.ac.cy)
URL: https://www.cs.ucy.ac.cy/colloquium/presentations.php#cs.ucy.pres.2012.christoforou

Abstract:
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 and Amazon’s Mechanical Turk. Prior work has considered such Master-Worker computations either in the presence of rational workers or in the presence of 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, our study focuses in developing reliable Internet-based Master-Worker computations in the presence of malicious, altruistic, and rational workers. 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 the first part of the talk we will briefly introduce the concept of Internet-based Master-Worker Computing and contrast it with typical Supercomputing settings. Then, focusing on a single task execution, we 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 workers to a certain equilibrium (which forces the workers to be truthful) that overcomes the attempt of the malicious workers to deceive the master. The mechanisms are analyzed in two realistic Internet-based master-worker settings and derived plots illustrate the trade-offs between reliability and cost. In the second part of the talk we will consider long-running, many-task, Master-Worker computations and show how knowledge obtained in prior master-workers interactions can be used to develop a reliable Internet-based computational platform where the master always obtain the correct result of the tasks. For this purpose we model Master-Worker computations using evolutionary dynamics and we study the conditions under which the master can reliably obtain tasks results. We will present an algorithmic mechanism that employs reinforcement learning and show the conditions under which truthful behavior can be ensured and in how many communication rounds such behavior is expected to be reached. Rationality is faced with appropriate incentives, while malice is confronted with the use of reputation schemes. The presentation consists the final dissemination seminar for the Cyprus Research Promotion Foundation funded Project ΤΠΕ/ΠΛΗΡΟ/0609(ΒΕ)/05

Short Bio:
Dr. Chryssis Georgiou (PhD, University of Connecticut, 2003) is an Assistant Professor of Computer Science at the University of Cyprus. His research interests span the Theory and Practice of Fault-tolerant Distributed and Parallel Computing with a focus on Algorithms and Complexity. He is the Project Coordinator of the project RELIABLE which is funded by the Cyprus Research Promotion Foundation under protocol number ΤΠΕ/ΠΛΗΡΟ/0609(ΒΕ)/05. See https://www.cs.ucy.ac.cy/ric . Evgenia Christoforou (MSc, University of Cyprus, 2012) is a Research Assistant at the Department of Computer Science, at the University of Cyprus, under the RPF funded project RELIABLE (ΤΠΕ/ΠΛΗΡΟ/0609(ΒΕ)/05). Her current research interests lie in Algorithmic and Evolutionary Game Theory. In November 2012, Evgenia will be joining as a researcher the Institute IMDEA Networks, Madrid, Spain.

  Other Presentations Web: https://www.cs.ucy.ac.cy/colloquium/presentations.php
  Colloquia Web: https://www.cs.ucy.ac.cy/colloquium/
  Calendar: https://www.cs.ucy.ac.cy/colloquium/schedule/cs.ucy.pres.2012.Christoforou.ics