  We present reputation-based mechanisms for building reliable task computing
systems over the Internet. The most characteristic examples of such systems are
the volunteer computing and the crowdsourcing platforms. In both examples end
users are offering over the Internet their computing power or their human
intelligence to solve tasks either voluntarily or under payment. While the main
advantage of these systems is the inexpensive computational power provided, the
main drawback is the untrustworthy nature of the end users. Generally, this
type of systems are modeled under the "master-worker" setting. A "master" has a
set of tasks to compute and instead of computing them locally she sends these
tasks to available "workers" that compute and report back the task results. We
categorize these workers in three generic types: altruistic, malicious and
rational. Altruistic workers that always return the correct result, malicious
workers that always return an incorrect result, and rational workers that
decide to reply or not truthfully depending on what increases their benefit. We
design a reinforcement learning mechanism to induce a correct behavior to
rational workers, while the mechanism is complemented by four reputation
schemes that cope with malice. The goal of the mechanism is to reach a state of
eventual correctness, that is, a stable state of the system in which the master
always obtains the correct task results. Analysis of the system gives provable
guarantees under which truthful behavior can be ensured. Finally, we observe
the behavior of the mechanism through simulations that use realistic system
parameters values. Simulations not only agree with the analysis but also reveal
interesting trade-offs between various metrics and parameters. Finally, the
four reputation schemes are assessed against the tolerance to cheaters.
