Parallel rotor walks on finite graphs and applications in discrete load balancing
Parallel rotor walks on finite graphs and applications in discrete load balancing
复制标题
并联转子在有限图上行走及其在离散负载平衡中的应用
DOI：
10.1145/2486159.2486178
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
P. Berenbrink
中科院分区：
文献类型：
--
作者：
Hoda Akbari;P. Berenbrink
我们研究了并行转子行走过程，其工作原理如下：考虑一个图沿着与任意分布的令牌在其节点。每个节点都配备了一个转子，以固定的圆形顺序指向其邻居。在每一轮中，每个节点使用转子分发其所有令牌。一个令牌被分配给转子指向的邻居，然后转子移动到下一个邻居，依此类推，直到没有令牌剩余。这个过程可以被认为是一个确定性的模拟过程，其中令牌在每一轮中执行一个独立的随机游走步骤。我们比较了令牌在转子行走过程中的分布与随机行走模型中的预期分布。两个过程之间的相似性通过它们的差异来衡量，这是所有轮和节点上相应分布条目之间的最大差异。我们分析了一个懒惰的转子行走的变化，它模拟了每个节点上循环概率为1/2的随机行走，并且每个节点在每一轮中发送的不是所有的令牌，而是每隔一个令牌。将转子游动看作一个负载平衡过程，证明了转子游动福尔斯属于文献[11]中引入的一类有界误差扩散过程。这给出了超立方体和r维环面（r=O（1））的O（log 3/2 n）和O（1）的差异界，改进了现有的O（log 2 n）和O（n1/r）的最佳界。此外，作为切换到负载平衡视图的结果，我们观察到现有的负载平衡结果可以被转换为以前在转子行走文献中没有注意到的转子行走差异界限。我们还使用转子行走的思想来提出和分析随机舍入离散负载平衡过程，该过程实现与类似协议相同的平衡质量[11，3]，但与[3]相比使用更少的随机比特数，并避免[11]的负负载问题。
We study the parallel rotor walk process, which works as follows: Consider a graph along with an arbitrary distribution of tokens over its nodes. Every node is equipped with a rotor that points to its neighbours in a fixed circular order. In each round, every node distributes all of its tokens using the rotor. One token is allocated to the neighbour pointed at by the rotor, then the rotor moves to the subsequent neighbour, and so on, until no token remains. The process can be considered as a deterministic analogue of a process in which tokens perform one independent random walk step in each round. We compare the distribution of tokens in the rotor walk process with expected distribution in the random walk model. The similarity between the two processes is measured by their discrepancy, which is the maximum difference between the corresponding distribution entries over all rounds and nodes. We analyze a lazy variation of rotor walks that simulates a random walk with loop probability of 1/2 on each node, and each node sends not all its tokens, but every other token in each round. Viewing the rotor walk as a load balancing process, we prove that the rotor walk falls in the class of bounded-error diffusion processes introduced in [11]. This gives us discrepancy bounds of O(log3/2 n) and O(1) for hypercube and r-dimensional torus with r=O(1), respectively, which improve over the best existing bounds of O(log2 n) and O(n1/r). Also, as a result of switching to the load balancing view, we observe that the existing load balancing results can be translated to rotor walk discrepancy bounds not previously noticed in the rotor walk literature. We also use the idea of rotor walks to propose and analyze a randomized rounding discrete load balancing process that achieves the same balancing quality as similar protocols [11, 3], but uses fewer number of random bits compared to [3], and avoids the negative load problem of [11].