论文标题
在边缘 - 摩托维亚发展图上的负载平衡算法的分析
An analysis of load-balancing algorithms on edge-Markovian evolving graphs
论文作者
论文摘要
对时变网络（通常称为不断发展的图）对算法的分析是理论计算机科学中的现代挑战。 Edge-Markovian是一个相对简单且全面的图表模型：每个不是当前边缘的顶点独立地成为每个时间步长的概率$ p $的边缘，并且每个边缘都会随概率$ q $而消失。显然，Edge-Markovian图根据当前形状改变了其形状，依赖关系拒绝了一些独立的随机图序列的有用技术，这些技术通常与静态随机图相似。它激发了本文开发一种新技术，用于分析边缘 - 摩洛维亚不断发展的图形上的算法。 具体而言，本文涉及负载平衡，这是分布式计算中流行的主题，我们分析了所谓的随机匹配算法，这是负载平衡的标准方案。我们证明，主要的随机匹配算法在$ O（r \ log（Δn））$ sptep的$ o（r \ log（Δn））上达到了几乎最佳的负载余额，其中$ r = \ max \ {p/（1-q），（1-q）/p \} $，$ n $，$ n $是dentices（ium.e.，处理器）和$Δ$ gap g的数量和$Δ$ note $ note和$Δ我们指出，随机图的独立序列对应于$ r = 1 $。为了避免由于与执行历史的复杂相关性而引起的分析的难度，我们基于与历史无关的界限开发了一种简单的证明技术。据我们所知，这是对随机发展图上负载平衡平衡的第一个理论分析，这不仅是边缘 - 马克维亚人，而且对于随机图的独立序列而言。
Analysis of algorithms on time-varying networks (often called evolving graphs) is a modern challenge in theoretical computer science. The edge-Markovian is a relatively simple and comprehensive model of evolving graphs: every pair of vertices which is not a current edge independently becomes an edge with probability $p$ at each time-step, as well as every edge disappears with probability $q$. Clearly, the edge-Markovian graph changes its shape depending on the current shape, and the dependency refuses some useful techniques for an independent sequence of random graphs which often behaves similarly to a static random graph. It motivates this paper to develop a new technique for analysis of algorithms on edge-Markovian evolving graphs. Specifically speaking, this paper is concerned with load-balancing, which is a popular subject in distributed computing, and we analyze the so-called random matching algorithms, which is a standard scheme for load-balancing. We prove that major random matching algorithms achieve nearly optimal load balance in $O(r \log (Δn))$ steps on edge-Markovian evolving graphs, where $r = \max\{p/(1-q), (1-q)/p\}$, $n$ is the number of vertices (i.e., processors) and $Δ$ denotes the initial gap of loads unbalance. We remark that the independent sequences of random graphs correspond to $r=1$. To avoid the difficulty of an analysis caused by a complex correlation with the history of an execution, we develop a simple proof technique based on history-independent bounds. As far as we know, this is the first theoretical analysis of load-balancing on randomly evolving graphs, not only for the edge-Markovian but also for the independent sequences of random graphs.
