Computer Science – Data Structures and Algorithms
Scientific paper
2011-12-06
Computer Science
Data Structures and Algorithms
18 pages
Scientific paper
Distance computation is one of the most fundamental primitives used in communication networks. The cost of effectively and accurately computing pairwise network distances can become prohibitive in large-scale networks such as the Internet and Peer-to-Peer (P2P) networks. To negotiate the rising need for very efficient distance computation, approximation techniques for numerous variants of this question have recently received significant attention in the literature. The goal is to preprocess the graph and store a small amount of information such that whenever a query for any pairwise distance is issued, the distance can be well approximated (i.e., with small stretch) very quickly in an online fashion. Specifically, the pre-processing (usually) involves storing a small sketch with each node, such that at query time only the sketches of the concerned nodes need to be looked up to compute the approximate distance. In this paper, we present the first theoretical study of distance sketches derived from distance oracles in a distributed network. We first present a fast distributed algorithm for computing approximate distance sketches, based on a distributed implementation of the distance oracle scheme of [Thorup-Zwick, JACM 2005]. We also show how to modify this basic construction to achieve different tradeoffs between the number of pairs for which the distance estimate is accurate and other parameters. These tradeoffs can then be combined to give an efficient construction of small sketches with provable average-case as well as worst-case performance. Our algorithms use only small-sized messages and hence are suitable for bandwidth-constrained networks, and can be used in various networking applications such as topology discovery and construction, token management, load balancing, monitoring overlays, and several other problems in distributed algorithms.
Dinitz Michael
Pandurangan Gopal
Sarma Atish Das
No associations
LandOfFree
Efficient Computation of Distance Sketches in Distributed Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Computation of Distance Sketches in Distributed Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Computation of Distance Sketches in Distributed Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-380800