Access Restriction

Author Awerbuch, Baruch ♦ Cidon, Israel ♦ Kutten, Shay
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Distributed algorithms ♦ Amortized complexity ♦ Dynamic networks ♦ Leader election ♦ Optimal message complexity ♦ Spanning tree ♦ Topological changes
Abstract In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The amortized (on the number of topological changes) message complexity is $\textit{O}(\textit{V}),$ where $\textit{V}$ is the number of nodes in the network. The message size used by the algorithm is $\textit{O}(log$ |ID|) where |ID| is the size of the name space of the nodes. Typically, log |ID| = $\textit{O}(log$ $\textit{V}).$ Previous algorithms that adapt to dynamic networks involved Ω $(\textit{E})$ messages per topological change—inherently paying for re-computation of the tree from scratch. Spanning trees are essential components in many distributed algorithms. Some examples include $\textit{broadcast}$ (dissemination of messages to all network nodes), multicast, reset (general adaptation of static algorithms to dynamic networks), routing, termination detection, and more. Thus, our efficient maintenance of a spanning tree implies the improvement of algorithms for these tasks. Our results are obtained using a novel technique to save communication. A node uses information received in the past in order to deduce present information from the fact that certain messages were NOT sent by the node's neighbor. This technique is one of our main contributions.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 55
Issue Number 4
Page Count 45
Starting Page 1
Ending Page 45

Open content in new tab

   Open content in new tab
Source: ACM Digital Library