In a vehicular edge computing (VEC) system, vehicles can share their surplus
computation resources to provide cloud computing services. The highly dynamic
environment of the vehicular network makes it challenging to guarantee the task
offloading delay. To this end, we introduce task replication to the VEC system,
where the replicas of a task are offloaded to multiple vehicles at the same
time, and the task is completed upon the first response among replicas. First,
the impact of the number of task replicas on the offloading delay is
characterized, and the optimal number of task replicas is approximated in
closed-form. Based on the analytical result, we design a learning-based task
replication algorithm (LTRA) with combinatorial multi-armed bandit theory,
which works in a distributed manner and can automatically adapt itself to the
dynamics of the VEC system. A realistic traffic scenario is used to evaluate
the delay performance of the proposed algorithm. Results show that, under our
simulation settings, LTRA with an optimized number of task replicas can reduce
the average offloading delay by over 30% compared to the benchmark without task
replication, and at the same time can improve the task completion ratio from
97% to 99.6%.

本文提出了一种在车辆边缘计算系统中使用多个任务副本进行任务卸载，以减少任务卸载延迟的学习算法，并通过实验展示了该算法的良好性能。

车联网边缘计算的分布式任务复制：性能分析与基于学习的算法

Distributed Task Replication for Vehicular Edge Computing: Performance  Analysis and Learning-based Algorithm

In a cloud computing job with many parallel tasks, the tasks on the slowest
machines (straggling tasks) become the bottleneck in the job completion.
Computing frameworks such as MapReduce and Spark tackle this by replicating the
straggling tasks and waiting for any one copy to finish. Despite being adopted
in practice, there is little analysis of how replication affects the latency
and the cost of additional computing resources. In this paper we provide a
framework to analyze this latency-cost trade-off and find the best replication
strategy by answering design questions such as: 1) when to replicate straggling
tasks, 2) how many replicas to launch, and 3) whether to kill the original copy
or not. Our analysis reveals that for certain execution time distributions, a
small amount of task replication can drastically reduce both latency as well as
the cost of computing resources. We also propose an algorithm to estimate the
latency and cost based on the empirical distribution of task execution time.
Evaluations using samples in the Google Cluster Trace suggest further latency
and cost reduction compared to the existing replication strategy used in
MapReduce.

本文提供了一个分析云计算任务并行执行框架中任务复制对延迟和计算资源成本的权衡的框架，通过回答设计问题，如何在什么时候复制滞后的任务，启动多少副本等。我们的分析表明，对于某些执行时间分布，少量任务复制可以显著降低延迟和计算资源的成本，并提出一种基于任务执行时间的经验分布估计延迟和成本的算法。与 MapReduce 中使用的现有复制策略相比，使用 Google Cluster Trace 中的样本进行评估揭示了进一步的延迟和成本降低。

大规模并行计算中高效 straggler 复制

Efficient Straggler Replication in Large-scale Parallel Computing

One typical use case of large-scale distributed computing in data centers is
to decompose a computation job into many independent tasks and run them in
parallel on different machines, sometimes known as the "embarrassingly
parallel" computation. For this type of computation, one challenge is that the
time to execute a task for each machine is inherently variable, and the overall
response time is constrained by the execution time of the slowest machine. To
address this issue, system designers introduce task replication, which sends
the same task to multiple machines, and obtains result from the machine that
finishes first. While task replication reduces response time, it usually
increases resource usage. In this work, we propose a theoretical framework to
analyze the trade-off between response time and resource usage. We show that,
while in general, there is a tension between response time and resource usage,
there exist scenarios where replicating tasks judiciously reduces completion
time and resource usage simultaneously. Given the execution time distribution
for machines, we investigate the conditions for a scheduling policy to achieve
optimal performance trade-off, and propose efficient algorithms to search for
optimal or near-optimal scheduling policies. Our analysis gives insights on
when and why replication helps, which can be used to guide scheduler design in
large-scale distributed computing systems.

本文研究大规模分布式计算中任务复制对响应时间和资源使用的影响，并提出了一些高效的算法来寻找最优的调度策略。