编码 MapReduce
在分布式计算系统中,通过编码存储的数据可以减少迟滞服务器造成的延迟,并减少在洗牌阶段的服务器之间的通信负载。本文通过内部的重复编码来提高外部最大距离可分离(MDS)码的速率,进而提高洗牌阶段的多播机会,从而改善了最佳延迟和通信开销之间的平衡。
Aug, 2018
本论文研究的问题是如何在分布式计算中,通过优化计算负载来降低通信负载,通过研究分布式计算中计算和通信之间的权衡关系,提出一种编码方案,命名为 “编码分布式计算”(CDC),该方案通过增加 Map 函数的计算负载来减少通信负载,实现了计算和通信的最优权衡。同时,将 CDC 的编码技术应用于 Hadoop TeraSort 基准测试中,开发出一种新的编码 TeraSort 算法,对实验中最常用的设置进行了验证,整个作业执行速度提高了 1.97 至 3.39 倍。
Apr, 2016
本文提出了一种基于编码计算的分布式图处理框架,通过结构性冗余注入来在消息交换时实现编码的多播机会,从而大规模减少了通信负载,理论分析证明该方案在两种流行的随机图模型(Erdos-Renyi 模型和幂律模型)中实现了计算负载和平均通信负载之间的(近似)反比例线性折衷,实验结果表明该方案在 PageRank 计算中具有显着提高。
Jan, 2018
本文介绍了一种针对分布式计算的编码框架,通过在某些线性计算任务中引入 “计算延迟” 和 “通信负载” 之间的权衡来解决延迟和通信负载问题,从而实现在延迟和负载之间取得权衡来执行分布式计算任务。
Sep, 2016
探究编码算法在分布式机器学习中的应用,研究矩阵乘法和数据洗牌两种算法中应用编码技术减少 straggler 和 communication bottlenecks 时的优化效果,理论分析和实验结果均证明编码算法具有显著的优势。
Dec, 2015
本文提出了一种编码框架(HCMM)以提高异构分布式计算的速度,并展示了在 Amazon EC2 上进行分布式矩阵乘法实验的结果。该方法比三种基准负载分配方案的速度分别快 61%,46%和 36%。同时,我们还提供了在异构设置中的最优负载分配问题的一般化解决方案,并开发了一个启发式算法(HCMM)负载分配问题。
Jan, 2017
本文提出了基于 Shamir 秘密共享方案的数据外包算法,用 MapReduce 作为底层编程模型来执行保护隐私的 SQL 查询,防止输出大小和访问模式攻击,并在参数上评估其效率。
Jan, 2018
本文探讨了 MapReduce 框架的算法方面,并通过设计和分析处理基本的排序、搜索和仿真问题的 MapReduce 算法展示了我们的方法的有效性。
Jan, 2011
本文介绍了一种新的梯度编码(GC)方案,结合多消息通信(MMC)和聚类,以减少因服务器慢导致的迭代时间延长问题,其能有效提高平均完成时间并降低通信负荷。
Mar, 2019
本文探讨了在 map-reduce 计算中并行性和通信成本之间的权衡问题,并引入了单轮 map-reduce 计算问题的模型,以发现以分配给一个缩小器的最大输入数为函数的通信成本下界。作者对三个问题进行了分析:找到两个距离为 $d$ 的字符串、在较大的图形中查找三角形和其他模式以及矩阵乘法。
Jun, 2012