A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
复制标题
一种用于维护稀疏扳手的近乎最优的分布式全动态算法
DOI：
10.1145/1281100.1281128
复制
发表时间：
2006
影响因子：
1.3
通讯作者：
Michael Elkin
中科院分区：
文献类型：
--
作者：
Michael Elkin
当前，对于动态分布式消息通话模型中的绝大部分图形问题尚无已知的显式算法。取而代之的是，大多数最新动态分布式算法都是通过使用将静态算法转换为动态算法的仿真技术来构成当前问题的静态算法的。我们认为，这种强大的方法不能为许多重要的动态分布式问题提供令人满意的解决方案，这需要从头开始为这些问题开发算法。
在本文中，我们开发了一种完全动态的分布式算法，用于保持稀疏的跨度。我们的算法大大改善了该问题最新算法的静止时间。此外，我们表明我们算法的静止时间是最佳的，最多是一个小恒定因子。此外，在所有效率参数中，我们的算法在最新算法上大大提高，具体来说，它具有较小的静态消息和空间复杂性，以及较小的本地处理时间。最后，我们的算法是独立且相当简单的，因此，可以适合于对未老练的网络设备的实现。
Currently, there are no known explicit algorithms for the great majority of graph problems in the dynamic distributed message-passing model. Instead, most state-of-the-art dynamic distributed algorithms are constructed by composing a static algorithm for the problem at hand with a simulation technique that converts static algorithms to dynamic ones. We argue that this powerful methodology does not provide satisfactory solutions for many important dynamic distributed problems, and this necessitates developing algorithms for these problems from scratch.
In this paper we develop a fully dynamic distributed algorithm for maintaining sparse spanners. Our algorithm improves drastically the quiescence time of the state-of-the-art algorithm for the problem. Moreover, we show that the quiescence time of our algorithm is optimal up to a small constant factor. In addition, our algorithm improves significantly upon the state-of-the-art algorithm in all efficiency parameters, specifically, it has smaller quiescence message and space complexities, and smaller local processing time. Finally, our algorithm is self-contained and fairly simple, and is, consequently, amenable to implementation on unsophisticated network devices.