2013/07/05 by Antonio Fernández Anta, Antonio Fernandez Anta, Chryssis Georgiou +4
Computer Science · Decision Sciences · #68Q85 #Computer Science and Game Theory (cs.GT) #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Game Theory and Applications #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC) #cs.DC #cs.GT #msc:68Q85
paper · pdf · doi:10.48550/arxiv.1307.1650
23 pages. A preliminary version of this work appears in the Proceedings of NCA 2008
arxiv created 2013/07/05 · openalex publication_date 2013/07/05 · arxiv updated 2013/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, using a game-theoretic approach, cost-sensitive mechanisms that lead to reliable Internet-based computing are designed. In particular, we consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of potentially untrusted worker processors and collects their responses. Workers may collude in order to increase their benefit. Several game-theoretic models that capture the nature of the problem are analyzed, and algorithmic mechanisms that, for each given set of cost and system parameters, achieve high reliability are designed. Additionally, two specific realistic system scenarios are studied. These scenarios are a system of volunteer computing like SETI, and a company that buys computing cycles from Internet computers and sells them to its customers in the form of a task- computation service. Notably, under certain conditions, non redundant allocation yields the best trade-off between cost and reliability.