This paper considers the setting where a cloud server services a static set or a dynamic sequence of tasks submitted by multiple clients. Every client wishes to assure honest execution of tasks by additionally employing a trusted third party (TTP) to re-compute the tasks with a certain probability. The cloud server makes a deposit for each task it takes, each client allocates a budget (including the wage for the server and the cost for possibly hiring TTP) for each task submitted, and every party has its limited fund for either deposits or task budgets. We study how to allocate the funds optimally to achieve the three-fold goals: a rational cloud server honestly computes each task; the server's wage is maximized; the overall delay for task verification is minimized. We apply game theory to formulate the optimization problems, and develop the optimal or heuristic solutions for three application scenarios. For each of the solutions, we analyze it through either rigorous proofs or extensive simulations. To the best of our knowledge, this is the first work on optimizing fund allocation for verifiable outsourcing of computation in the setting of one server and multiple clients, based on game theory.
翻译:本文考虑了云端服务器为多个客户提交的静态数据集或动态任务序列提供服务的背景。 每个客户都希望通过额外雇用信任的第三方(TTP)来保证诚实地执行任务, 以某种概率重新计算任务。 云端服务器为每件任务留出一笔存款, 每个客户为每件任务分配预算( 包括服务器的工资和可能聘用TTP的费用), 每个当事方都有有限的存款或任务预算资金。 我们研究如何最佳地分配资金, 以实现三重目标: 一个理性的云端服务器诚实地计算每项任务; 服务器的工资最大化; 任务核查的总体延迟最小化。 我们应用游戏理论来制定优化问题, 为三种应用情景制定最佳或超常化解决方案。 对于每一种解决方案, 我们通过严格的证明或广泛的模拟来分析。 根据我们的知识, 这是在设定一个服务器和多个客户时根据游戏理论, 优化资金分配以可核查方式进行计算。