CS 789 THEORY SEMINAR [home]

Speaker:    Aleksandrs Slivkins
Affiliation:  Cornell University
Date:          August 30, 2004
Title:          Triangulation and Embedding using Small Sets of Beacons

Abstract: 

A growing body of research in the networking community has studied the distance matrix defined by the node-to-node latencies in the Internet, resulting in a number of approaches that approximately embed this distance into a low-dimensional Euclidean space. In this setting it is feasible to measure distances among only a linear or near-linear number of node pairs, which is in sharp contrast with the theoretical work on metric embeddings where the full (and centralized) access to the distance matrix is assumed and heavily used. Moreover, the more basic problem of 'triangulation' was considered, in which one uses the triangle inequality to infer the distances that have not been measured.

Here we give distributed algorithms with provable performance guarantees for triangulation and embedding. We focus on doubling metrics (which have been proposed as a reasonable abstraction of Internet latencies), but give results for other classes of metrics as well. We address both the 'beacon-based' approach, where each node measures distances to a small set of 'beacons', and the more recent approaches that do not place too much load on any one node. Our guarantees typically must include 'slack' -- a certain fraction of all distances that may be arbitrarily distorted; this notion of 'slack' is of independent interest.

Written with  Jon Kleinberg and Tom Wexler, to appear in FOCS'04 available on http://www.cs.cornell.edu/people/slivkins.