Algorithmic mechanisms for internet supercomputing under unreliable communication
SourceProceedings - 2011 IEEE International Symposium on Network Computing and Applications, NCA 2011
10th IEEE International Symposium on Network Computing and Applications, NCA 2011
Google Scholar check
MetadataShow full item record
This work, using a game-theoretic approach, considers Internet-based computations, where a master processor assigns, over the Internet, a computational task to a set of untrusted worker processors, and collects their responses. The master must obtain the correct task result, while maximizing its benefit. Building on prior work, we consider a framework where altruistic, malicious, and rational workers co-exist. In addition, we consider the possibility that the communication between the master and the workers is not reliable, and that workers could be unavailableassumptions that are very realistic for Internet-based master-worker computations. Within this framework, we design and analyze two algorithmic mechanisms that provide, when necessary, appropriate incentives to rational workers to act correctly, despite the malicious' workers actions and the unreliability of the network. These mechanisms are then applied to two realistic Internet-based master-worker settings, a SETI-like one and a contractor-based one, such as Amazon's mechanical turk. © 2011 IEEE.