Show simple item record

dc.contributor.authorFernández Anta, Antonioen
dc.contributor.authorGeorgiou, Chryssisen
dc.contributor.authorMosteiro, Miguel A.en
dc.contributor.authorPareja, D.en
dc.creatorFernández Anta, Antonioen
dc.creatorGeorgiou, Chryssisen
dc.creatorMosteiro, Miguel A.en
dc.creatorPareja, D.en
dc.description.abstractWe consider a computing system where a master processor assigns tasks for execution to worker processors through the Internet. We model the workers' decision of whether to comply (compute the task) or not (return a bogus result to save the computation cost) as a mixed extension of a strategic game among workers. That is, we assume that workers are rational in a game-theoretic sense, and that they randomize their strategic choice. Workers are assigned multiple tasks in subsequent rounds. We model the system as an infinitely repeated game of the mixed extension of the strategic game. In each round, the master decides stochastically whether to accept the answer of the majority or verify the answers received, at some cost. Incentives and/or penalties are applied to workers accordingly. Under the above framework, we study the conditions in which the master can reliably obtain tasks results, exploiting that the repeated game model captures the effect of long-term interaction. That is, workers take into account that their behavior in one computation will have an effect on the behavior of other workers in the future. Indeed, should a worker be found to deviate from some agreed strategic choice, the remaining workers would change their own strategy to penalize the deviator. Hence, being rational, workers do not deviate. We identify analytically the parameter conditions to induce a desired worker behavior, and we evaluate experimentally the mechanisms derived from such conditions. We also compare the performance of our mechanisms with a previously known multi-round mechanism based on reinforcement learning. © 2016 IEEE.en
dc.publisherIEEE Computer Societyen
dc.sourceProceedings of the IEEE Symposium on Reliable Distributed Systemsen
dc.source35th IEEE International Symposium on Reliable Distributed Systems, SRDS 2016en
dc.subjectComputation theoryen
dc.subjectMachine designen
dc.subjectReinforcement learningen
dc.subjectComputer gamesen
dc.subjectGame Theoryen
dc.subjectTask computingen
dc.subjectAlgorithmic Mechanism Designen
dc.subjectComputation costsen
dc.subjectInternet Computingen
dc.subjectLong-term interactionen
dc.subjectMaster-Worker Task Computingen
dc.subjectParameter conditionsen
dc.subjectRepeated Gamesen
dc.subjectStrategic choiceen
dc.titleMulti-round Master-Worker Computing: A Repeated Game Approachen
dc.description.endingpage40 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeConference Objecten
dc.description.notes<p>Sponsors: IEEEen
dc.description.notesIEEE Computer Societyen
dc.description.notesTechnical Committee on Distributed Processing (TCDP)en
dc.description.notesConference code: 125554</p>en
dc.contributor.orcidGeorgiou, Chryssis [0000-0003-4360-0260]
dc.contributor.orcidFernández Anta, Antonio [0000-0001-6501-2377]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record