Triangulation and Embedding Using Small Sets of Beacons

Concurrent with recent theoretical interest in the problem of metric embedding, a growing body of
research in the networking community has studied the distance matrix defined by node-to-node latencies
in the Internet, resulting in a number of recent approaches that approximately embed this distance
matrix into low-dimensional Euclidean space. There is a fundamental distinction, however, between
the theoretical approaches to the embedding problem and this recent Internet-related work: in addition
to computational limitations, Internet measurement algorithms operate under the constraint that it is
only feasible to measure distances for a linear (or near-linear) number of node pairs, and typically in a
highly structured way. Indeed, the most common framework for Internet measurements of this type is a
beacon-based approach: one chooses uniformly at random a constant number of nodes (‘beacons’) in the
network, each node measures its distance to all beacons, and one then has access to only these measurements
for the remainder of the algorithm. Moreover, beacon-based algorithms are often designed not for
embedding but for the more basic problem of triangulation, in which one uses the triangle inequality to
infer the distances that have not been measured.
Here we give algorithms with provable performance guarantees for beacon-based triangulation and
embedding. We show that in addition to multiplicative error in the distances, performance guarantees
for beacon-based algorithms typically must include a notion of slack — a certain fraction of all distances
may be arbitrarily distorted. For metric spaces of bounded doubling dimension (which have been
proposed as a reasonable abstraction of Internet latencies), we show that triangulation-based distance
reconstruction with a constant number of beacons can achieve multiplicative error 1 + ± on a 1 ¡ ² fraction
of distances, for arbitrarily small constants ± and ². For this same class of metric spaces, we give
a beacon-based embedding algorithm that achieves constant distortion on a 1 ¡ ² fraction of distances;
this provides some theoretical justification for the success of the recent Global Network Positioning algorithm
of Ng and Zhang, and it forms an interesting contrast with lower bounds showing that it is not
possible to embed all distances in a doubling metric space with constant distortion. We also give results
for other classes of metric spaces, as well as distributed algorithms that require only a sparse set of
distances but do not place too much measurement load on any one node.