Computing Low Latency Batches with Unreliable Workers in Volunteer Computing Environments
Computing Low Latency Batches with Unreliable Workers in Volunteer Computing Environments
复制标题
DOI：
10.1007/s10723-009-9131-6
复制
发表时间：
2008-04
影响因子：
5.5
通讯作者：
E. Heien;David P. Anderson;K. Hagihara
中科院分区：
文献类型：
--
作者：
E. Heien;David P. Anderson;K. Hagihara
基于互联网的志愿者计算项目，如SETI@home，目前仅限于执行粗粒度的，并行的主从式任务。这部分是由于志愿者计算环境中任务分配的“拉”性质，其中工作者从主节点请求任务，而不是主节点将任务分配给任意工作者。在本文中，我们提出了算法计算批量的中粒度任务的最后期限在拉式志愿者计算环境。我们开发的模型不可靠的工人的基础上分析跟踪数据从一个实际的志愿者计算项目。这些模型被用来开发算法，在志愿者计算系统中的任务分配具有很高的概率，满足批量的最后期限。我们为完全可靠的工人、计算可靠的工人和不可靠的工人开发算法。最后，我们证明了算法的有效性，通过模拟使用的痕迹，从实际的志愿者计算环境。
Internet based volunteer computing projects such as SETI@home are currently restricted to performing coarse grained, embarrassingly parallel master-worker style tasks. This is partly due to the “pull” nature of task distribution in volunteer computing environments, where workers request tasks from the master rather than the master assigning tasks to arbitrary workers. In this paper we propose algorithms for computing batches of medium grained tasks with deadlines in pull-style volunteer computing environments. We develop models of unreliable workers based on analysis of trace data from an actual volunteer computing project. These models are used to develop algorithms for task distribution in volunteer computing systems with a high probability of meeting batch deadlines. We develop algorithms for perfectly reliable workers, computation-reliable workers and unreliable workers. Finally, we demonstrate the effectiveness of the algorithms through simulations using traces from actual volunteer computing environments.