Ultra-Fast Load Balancing on Scale-Free Networks
Ultra-Fast Load Balancing on Scale-Free Networks
复制标题
DOI：
10.1007/978-3-662-47666-6_41
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
K. Bringmann;T. Friedrich;M. Hoefer;Ralf Rothenberger;Thomas Sauerwald
中科院分区：
文献类型：
--
作者：
K. Bringmann;T. Friedrich;M. Hoefer;Ralf Rothenberger;Thomas Sauerwald
大型分布式系统的性能关键取决于有效地平衡其负载。这激发了大量的理论研究如何不平衡的负载向量可以平滑与本地算法。由于技术上的原因，绝大多数以前的工作集中在定期（或几乎定期）图，包括对称拓扑结构，如网格和超立方体，而忽略了一个事实，即大型网络往往是高度异构的。我们建模的大型无标度网络的Chung-Lu随机图和分析一个简单的本地算法迭代负载平衡。在节点图上，我们的分布式算法在步内平衡负载。它不需要知道幂律度分布的指数或图模型的权重。据我们所知，这是第一个结果，表明负载平衡可以在双对数时间内完成现实的图形类。
The performance of large distributed systems crucially depends on efficiently balancing their load. This has motivated a large amount of theoretical research how an imbalanced load vector can be smoothed with local algorithms. For technical reasons, the vast majority of previous work focuses on regular (or almost regular) graphs including symmetric topologies such as grids and hypercubes, and ignores the fact that large networks are often highly heterogenous.We model large scale-free networks by Chung-Lu random graphs and analyze a simple local algorithm for iterative load balancing. Onn-node graphs our distributed algorithm balances the load withinsteps. It does not need to know the exponentof the power-law degree distribution or the weightsof the graph model. To the best of our knowledge, this is the first result which shows that load-balancing can be done in double-logarithmic time on realistic graph classes.