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.