Triangulation and Embedding Using Small Sets of Beacons

Aleksandrs Slivkins

Node-to-node latencies can be seen as a notion of distance in networks such as the Internet. For a number of applications it is useful to represent this distance via coodinates in a low-dimensional Euclidean space and, moreover, compute these coordinates in a decentralized fashion, with low overhead on participating nodes. In particular, each node is allowed only a near-constant number of distance measurements. This is in sharp contrast with existing theoretical work on metric embeddings which assumes full (and centralized) access to the distance matrix.

Here we show how to extend theoretical guarantees for embedding to this decentralized setting. We also consider a more basic problem of ’triangulation’, in which one uses the triangle inequality to infer the distances that have not been measured. We also report on some successes of this style of analysis in the context of a deployed system.