Currently, there are no known explicit algorithms for the great majority of graph problems in the dynamicdistributed message-passing model. Instead, most state-of-the-art dynamicdistributedalgorithms are constructe...
详细信息
ISBN:
(纸本)9781595936165
Currently, there are no known explicit algorithms for the great majority of graph problems in the dynamicdistributed message-passing model. Instead, most state-of-the-art dynamicdistributedalgorithms 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 dynamicdistributed problems;and this necessitates developing algorithms for these problems from scratch. In this paper we develop a fully dynamicdistributed 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 tip 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.
暂无评论