Summary of Gaia

场景和Problem

    Gaia所对应的使用场景为geo-distributed machine learning，指有多个data centers同时参加一次model training。这是因为由于成本或隐私等原因，将全世界的数据集中到一个DC中是不现实的，故数据依旧仅存放于各个local datacenter中。各数据中心通过WAN进行通信，交换updates。于是，和在LAN中训练最为不同的一点是，WAN的带宽是珍贵的，跨WAN进行通信的成本非常高，于是成为训练瓶颈。

    为证明其motivation，Gaia提供了跨DC模型训练中，communication的时延测试，如下图：

    可以看到WAN的带宽要比LAN的带宽小15X（平均），在最坏的情况下甚至小于60X。故传统的distributed framework如MapReduce、Tensorflow等并不能适用于此场景。

Solutions and Contributions

    Gaia的目标是，尽可能的缩小跨WAN的数据传输，即reduct communication size。Gaia发现，并不是所有的updates都会对parameters的变化有巨大的影响，如下图：

    可以看到，甚至有60%以上的updates对parameters的影响在0.05%以下，这给了我们解决通信量大的启发，即只传那些会大幅影响parameters的updates，称为significant updates。

    Gaia的主要贡献可以总结为：解耦合了于DC内部的updates同步，和DC间的updates同步，这里的同步是指相较于BSP、SSP等并行方法中的同步，在Gaia中使用的并行方法为ASP (Approximate Synchronous Parallel)。基于这种新的并行方法，Gaia不需要在每次迭代中都使用全部的updates，论文中给出了该并行方法同样可以使模型达到收敛的证明。

    此外，Gaia具有泛用性，其适用于大多数machine learning算法，并可以与Parameter Sever架构的系统一同使用。

    关于Parameter Server架构的分布式机器学习框架，可以参考Summary of Parameter Server

    Parameter Server系统框图如下：


    Gaia运行在Parameter Servers中间，在本节笔者将对其组件进行分别介绍。

The significance filter

    该组件用来评估每个update的重要性，故需要一个significance function和initial significance threshold，只有大于阈值的updates才会在DC间share。

ASP selective barrier

    该组件用于保证significant updates可以被及时处理。当PS发现收到significant updates（来自本地workers的）的速率大于WAN带宽时（发送方），它将通过ASP selective barrier把这些updates的indexes发送给其他的data centers。接受端会阻塞其local workers直至收到significant updates。这一组件保证了所有的workers可以在受限的network latency后感知到significant updates。

Mirror clock

    WAN的带宽和延时是动态变化的，对于worker而言，其需要及时的感知到significant updates。ASP selective barrier假设了WAN带宽和延时是固定的，所以可以计算出受限的WAN时延；且假设了该时延足够短，故其他DC可以及时的感知到。Mirror clock用于记录各个DC的本地clock，每次交互updates时，DC都会附上自己的clock时间。当一个server发现本地clock比最慢的server要快时，它将阻塞本地workers，直到最慢的mirror server catches up。

    Gaia没有给出advanced significance function和tuning of significance thresholds的方法，但其给出了ASP的正确性证明。在Gaia evaluation中使用的significance function是update对模型的影响，例如一个update会对model parameters造成1%的改变，当小于1%则认为此update是不重要的。