Resumen de Achieving reliability and fairness in online task computing environments
Evgenia Christoforou
We consider online task computing environments such as volunteer computing platforms running on BOINC (e.g. SETI@home) and crowdsourcing platforms such as Amazon’s Mechanical Turk. We model the computations as an Internet-based task computing system under the master-worker paradigm. A master entity sends tasks across the Internet, to worker entities willing to perform a computational task. Workers execute the tasks, and report back the results, completing the computational round. Unfortunately, workers are untrustworthy and might report an incorrect result. We capture the workers' behavior with two realistic models: (1) the “error probability model” on the workers behavior, which assumes the presence of altruistic workers willing to provide correct results and the presence of troll workers aiming at providing random incorrect results.
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 reporting a correct result, the presence of malicious workers always reporting an incorrect result, and the presence of rational workers following a strategy that will maximize their utility (benefit). The rational 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' behavior are 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 set of tasks with high probability. Applying the rationality model, we take an evolutionary game theoretic approach and we design mechanisms that eventually achieve a reliable computational platform where the master receives the correct task result with probability one and with minimal auditing cost. The designed mechanisms provide incentives to the rational workers, reinforcing their strategy to a correct behavior, while they are complemented by four reputation schemes that cope with malice.
Finally, we also design mechanisms that deal with unresponsive workers by keeping a reputation related to the workers' response rate. Based on the responsiveness reputation the most reliable and active workers are selected in each computational round. Simulations show the trade-off among the master’s cost and the time the system needs to reach a state where the master always receives the correct task result. The second problem we consider in this work is related to the master entities. A set of masters with similar tasks is competing for the same set of workers at each computational round. A master might have a strategic behavior, declaring a valuation that will allow her to always receive the desired worker, while the rest of the master entities will suffer from starvation of the preferred workers. We address this problem, by designing a mechanism for fair and efficient distribution of the workers in the presence of strategic masters, without the use of monetary incentives. We show analytically that our designed mechanism guarantees fairness, is socially efficient, and is truthful. Simulations favorably compare our designed mechanism with two benchmark auction mechanisms.
