Publication: Achieving reliability and fairness in online task computing environments
Loading...
Identifiers
Publication date
2017-06
Defense date
2017-05-25
Authors
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
We consider online task computing environments such as volunteer computing platforms running
on BOINC (e.g., SETI@home) and crowdsourcing platforms such as Amazon Mechanical
Turk. We model the computations as an Internet-based task computing system under the masterworker
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. Thus, the first research question we answer in this work is how to design a reliable masterworker
task computing system. We capture the workers’ behavior through two realistic models:
(1) the “error probability model” 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. Considering 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 a mechanism that deals with unresponsive workers by
keeping a reputation related to the workers’ response rate. The designed mechanism selects the
most reliable and active workers in each computational round. Simulations, among other, depict
the trade-off between 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 research question we answer in
this 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 at
each computational round. Workers must be assigned to the masters in a fair manner; when the
master values a worker’s contribution the most. We consider that a master might have a strategic
behavior, declaring a dishonest valuation on a worker in each round, in an attempt to increase its
benefit. This strategic behavior from the side of the masters might lead to unfair and inefficient assignments
of workers. Applying renown auction mechanisms to solve the problem at hand can be
infeasible since monetary payments are required on the side of the masters. Hence, we present an
alternative 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 favourably compare
our designed mechanism with two benchmark auction mechanisms.
Description
Mención Internacional en el título de doctor
Keywords
Internet-based task computing system, Masterworker task computing system, Online task computing environment, Reliability