Distributed approaches to triangulation and embedding
Aleksandrs Slivkins · 2005
A number of recent papers in the networking community study the distance matrix defined by the node-to-node la-tencies in the Internet and, in particular, provide a number of quite successful distributed approaches that embed this distance into a low-dimensional Euclidean space. In such algorithms it is feasible to measure distances among only a linear or near-linear number of node pairs; the rest of the dis-tances are simply not available. Moreover, for applications it is desirable to spread the load evenly among the partici-pating nodes. Indeed, several recent studies use this 'fully distributed ' approach and achieve, empirically, a low distor-tion for all but a small fraction of node pairs. This is concurrent with the large body of theoretical work on metric embeddings, but there is a fundamental dis-tinction: in the theoretical pproaches tometric embeddings, full and centralized access to the distance matrix is assumed and heavily used. In this paper we present the first fully dis-tributed embedding algorithm with provable distortion guar-antees for doubling metrics (which have been proposed as a reasonable abstraction of Internet latencies), thus providing some insight into the empirical success of the recent VivaMi algorithm [5]. The main ingredient of our embedding algo-rithm is an improved 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; this problem received a considerable attention in the net-working community, and has also been studied theoretically in [19]. We use our techniques to extend e-relaxed embeddings and triangulations toinfinite metrics and arbitrary measures, and to improve on the approximate distance labeling scheme of Talwar [33]. I