Computing Reviews

Efficient distributed computation of distance sketches in networks
Das Sarma A., Dinitz M., Pandurangan G. Distributed Computing28(5):309-320,2015.Type:Article
Date Reviewed: 05/11/16

Shortest path computation is fundamental not only to efficient node-to-node communications, but also to search, discovery of relatedness between uniform resource locators (URLs) or between members of social networks, discovery of network topology, and more. However, discovery of shortest paths is also computationally challenging.

Distance sketches allow each node in a network to store its own view of the overall network topology. These views are combined to provide rapid approximate responses to distance queries.

The paper is primarily a theoretical study of distance sketching algorithms, leading to a new distributed algorithm that provides an almost optimal tradeoff between size and accuracy of distance sketches. This algorithm was combined with existing centralized techniques, resulting in a highly practical approach to computing distance sketches in large networks.

The paper makes for a challenging but rewarding read. The interplay between theory and practice in the mathematical analysis and synthesis of distance sketching algorithms is especially fascinating.

Overall, this paper is well worth reading and likely to be of interest to network practitioners as well as network theorists.

Reviewer:  Edel Sherratt Review #: CR144398 (1607-0503)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy