RT Dissertation/Thesis
T1 Achieving reliability and fairness in online task computing environments
A1 Christoforou, Evgenia
A2 IMDEA Networks Institute, 
AB We consider online task computing environments such as volunteer computing platforms runningon BOINC (e.g., SETI@home) and crowdsourcing platforms such as Amazon MechanicalTurk. We model the computations as an Internet-based task computing system under the masterworkerparadigm. A master entity sends tasks across the Internet, to worker entities willing toperform a computational task. Workers execute the tasks, and report back the results, completingthe computational round. Unfortunately, workers are untrustworthy and might report an incorrectresult. Thus, the first research question we answer in this work is how to design a reliable masterworkertask computing system. We capture the workers’ behavior through two realistic models:(1) the “error probability model” which assumes the presence of altruistic workers willing toprovide correct results and the presence of troll workers aiming at providing random incorrectresults. Both types of workers suffer from an error probability altering their intended response.(2) The “rationality model” which assumes the presence of altruistic workers, always reportinga correct result, the presence of malicious workers always reporting an incorrect result, and thepresence of rational workers following a strategy that will maximize their utility (benefit). Therational workers can choose among two strategies: either be honest and report a correct result,or cheat and report an incorrect result. Our two modeling assumptions on the workers’ behaviorare supported by an experimental evaluation we have performed on Amazon Mechanical Turk.Given the error probability model, we evaluate two reliability techniques: (1) “voting” and (2)“auditing” in terms of task assignments required and time invested for computing correctly a setof tasks with high probability. Considering the rationality model, we take an evolutionary gametheoretic approach and we design mechanisms that eventually achieve a reliable computationalplatform where the master receives the correct task result with probability one and with minimalauditing cost. The designed mechanisms provide incentives to the rational workers, reinforcingtheir strategy to a correct behavior, while they are complemented by four reputation schemes thatcope with malice. Finally, we also design a mechanism that deals with unresponsive workers bykeeping a reputation related to the workers’ response rate. The designed mechanism selects themost reliable and active workers in each computational round. Simulations, among other, depictthe trade-off between the master’s cost and the time the system needs to reach a state wherethe master always receives the correct task result. The second research question we answer inthis work concerns the fair and efficient distribution of workers among the masters over multiple computational rounds. Masters with similar tasks are competing for the same set of workers ateach computational round. Workers must be assigned to the masters in a fair manner; when themaster values a worker’s contribution the most. We consider that a master might have a strategicbehavior, declaring a dishonest valuation on a worker in each round, in an attempt to increase itsbenefit. This strategic behavior from the side of the masters might lead to unfair and inefficient assignmentsof workers. Applying renown auction mechanisms to solve the problem at hand can beinfeasible since monetary payments are required on the side of the masters. Hence, we present analternative mechanism for fair and efficient distribution of the workers in the presence of strategicmasters, without the use of monetary incentives. We show analytically that our designed mechanismguarantees fairness, is socially efficient, and is truthful. Simulations favourably compareour designed mechanism with two benchmark auction mechanisms.
YR 2017
FD 2017-06
LK https://hdl.handle.net/10016/25132
UL https://hdl.handle.net/10016/25132
LA eng
NO Mención Internacional en el título de doctor
NO This work has been supported by IMDEA Networks Institute and the Spanish Ministry of Education grant FPU2013-03792.
DS e-Archivo
RD 16 may. 2024