关键词:
移位加
锯齿解码
编码分布式计算
激励机制
本地再编码
摘要:
在数据大爆炸的时代,集中式处理数据已不能满足需求,分布式处理被广泛应用起来。但是在分布式处理数据的过程中,总有一些计算速度相对较慢的设备,拖慢了整体的计算时间,为了消除这些计算速度相对较慢的设备的影响,编码技术应运而生。通过编码增加计算冗余,只需接受部分处理速度快的设备结果,就能恢复原始数据,能有效地抵抗计算速度慢的影响。传统的编码技术使用的都是线性编码,线性编码有计算量大,计算复杂度高和消耗资源多等缺点,因此改善线性编码带来的这些缺点,降低数据存储时的开销具有重要意义。近年来,CP-ZD码被提出,CP指的是组合特性(Combiantion Property,CP),ZD指的是能锯齿解码(Zigzag Decoding,ZD),CP含义是将k个源包编码成n个编码包,其中n≥k,其中任意k个编码包就可恢复原始数据。(n,k)CP-ZD码采用的编解码方式分别是移位加(Shift-and-Add,SA)编码和ZD解码,这种码相对于线性编码,避免了昂贵的乘除法,极大地减小了计算复杂度。然而现有的码在n/k增大的情况下,开销比较大,因此本文针对这种场景设计了开销更小的DCS码,然后证明了其可锯齿解码,并通过实验仿真显示该码比现有的码开销要小。
编码分布式计算系统(Coded Distributed Computing,CDC)中,主节点分配工作任务给工作节点。为了完成CDC子任务,工作节点会消耗自己的资源产生成本,而工作节点是自私的,自愿参与完成CDC子任务是不现实的,因此需要设计激励机制,激励工作节点参与完成任务。本文设计了一种双边拍卖机制来激励工作节点来完成主节点的CDC任务,该机制不仅完成了主节点和工作节点的配对,并且以最大化社会福利为目标,即最大化主节点和工作节点的效益,设计了支付机制,达到激励主节点和工作节点参与完成CDC任务的目的。为了消除恶意节点的影响,还设计了信誉分数机制,能够有效消除在中标后没有完成CDC子任务的恶意工作节点。从仿真结果来看,以最大化社会福利为目标设计的支付机制相较于以第二价格支付社会福利更大,因此更能起到激励作用。
现有的编码分布式计算完成矩阵乘向量的任务时只考虑编码,解码和计算的时间,忽略了现实边缘计算的场景中,分布式基础设施中会有其他作业共享,传输带宽会发生改变,这些性能是可以动态变化的。这些情况都会对任务完成的时间造成影响,所以输入的编码矩阵的最佳方式也应该能随时适应不断变化的场景。在本文中设计一种基于SAZD的矩阵乘向量的编码方式,该编码方式不仅比线性编码的计算负载小,而且提出了一种本地再编码的方式,相对于全局编码减少了加法运算,从实验结果来看,在分布式系统性能不断变换时,本地再编码相较于全局编码节省了时间,更能适应动态变化的场景。