Node-to-node latencies is a notion of distance in the Internet. A recent trend in the networking literature has been to embed this distance into a low-dimensional Euclidean space. For applications it is desirable to compute such embedding via a distributed algorithm with low load on every participating node. Indeed, several studies use this 'fully distributed' approach and achieve, empirically, a low distortion for all but a small fraction of node pairs.

Such phenomenon calls for theoretical explanation: here we present the first fully distributed embedding algorithm that has provable guarantees. We focus on doubling metrics (which have been proposed as a reasonable abstraction of Internet latencies). Our construction extends to a fully distributed algorithm for a more basic problem of "triangulation", where the triangle inequality is used to infer the distances that have not been measured directly.

In the centralized (non-distributed) setting we apply our techniques to distance labeling schemes on doubling metrics.

This talk is based on "Distributed Approaches to Triangulation and Embedding" (A. Slivkins, SODA'05)