Online and dynamic embeddings of approximate ultrametrics

ABSTRACT

In many network applications it would be useful for individual nodes to have knowledge of distances (e.g. latency or bandwidth) in the network. If every node stored all distances then it would take Ω(n²) space at every node, and furthermore when a new node joins it would have to send an Ω(n)-bit message to Ω(n) other nodes, for a total communication complexity of Ω(n²) per update. In this paper we consider a specific class of metrics, those obeying an ε-three point condition, and show that by embedding these metrics into ultrametrics we can use only O(n) space at every node, have amortized communication complexity of O(n^4/3) (allowing nodes to join and leave the network), and still estimate distances up to a (1+ε)^{log n + 5}-stretch factor.

REFERENCES

• 1: Ittai Abraham , Mahesh Balakrishnan , Fabian Kuhn , Dahlia Malkhi , Venugopalan Ramasubramanian , Kunal Talwar, Reconstructing approximate tree metrics, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281110]
• 2: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, ACM SIGCOMM Computer Communication Review, v.34 n.4, October 2004

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
dynamic, embeddings, metric spaces, online, ultrametrics