Distributed algorithms for ultrasparse spanners and linear size skeletons

ABSTRACT

We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the trade-off between time, sparseness, and distortion. All of our algorithms assume a synchronized distributed network, where relatively short messages may be communicated in each time step. Our first result is an O(log n)^1+o(1)-time algorithm for finding a (2^{O(log* n)}log n)-spanner with size O(n). Besides being nearly optimal in time and distortion, this algorithm appears to be the first that constructs a O(n)-size skeleton without requiring unbounded length messages or time proportional to the diameter of the network. Our second result is a new class of efficiently constructible (α,β)-spanners called Fibonacci spanners whose distortion improves with the distance being approximated. At their sparsest Fibonacci spanners can have nearly linear size O(n(log log n)^φ) where φ = 1+☂5/2 is the golden ratio. As the distance increases the Fibonacci spanner's multiplicative distortion passes through four discrete stages, moving from logarithmic to doubly logarithmic, then into a period where it is constant, tending to 3, followed by another period tending to 1. On the lower bound side we prove that many recent sequential spanner constructions have no efficient counterparts in distributed networks, even if the desired distortion only needs to be achieved on the average or for a tiny fraction of the vertices. In particular, any distance preservers, purely additive spanners, or spanners with sublinear additive distortion must either be very dense, slow to construct, or have very weak guarantees on distortion.

REFERENCES

• 1: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: upper bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148144]
• 2: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007916]
• 3: D. Aingworth , C. Chekuri , P. Indyk , R. Motwani, Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication), SIAM Journal on Computing, v.28 n.4, p.1167-1181, Aug. 1999 [doi>10.1137/S0097539796303421]
• 4: Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
• 5: Surender Baswana, Dynamic algorithms for graph spanners, Proceedings of the 14th conference on Annual European Symposium, p.76-87, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_10]
• 6: S. Baswana. Personal communication, 2008.
• 7: Surender Baswana , Telikepalli Kavitha , Kurt Mehlhorn , Seth Pettie, New constructions of (α, β)-spanners and purely additive spanners, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Surender Baswana , Soumojit Sarkar, Fully dynamic algorithm for graph spanners with poly-logarithmic update time, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1125-1134, January 20-22, 2008, San Francisco, California
• 9: Surender Baswana , Sandeep Sen, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Random Structures & Algorithms, v.30 n.4, p.532-563, July 2007 [doi>10.1002/rsa.v30:4]
• 10: B. Derbel. Personal communication, 2008.
• 11: B. Derbel and C. Gavoille. Fast deterministic distributed algorithms for sparse spanners. In Proc. 13th Int'l Colloq on Structural Infor. and Comm. Complexity (SIROCCO), pages 100--114, 2006.
• 12: B. Derbel, C. Gavoille, and D. Peleg. Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In Proc. 21st Int'l Symp. on Distr. Comput. (DISC), pages 179--192, 2007.
• 13: Bilel Derbel , Cyril Gavoille , David Peleg , Laurent Viennot, On the locality of distributed sparse spanner construction, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400788]
• 14: Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908]
• 15: Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Aravind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Journal of Computer and System Sciences, v.71 n.4, p.467-479, November 2005 [doi>10.1016/j.jcss.2005.04.002]
• 16: Michael Elkin, Computing almost shortest paths, ACM Transactions on Algorithms (TALG), v.1 n.2, p.283-323, October 2005 [doi>10.1145/1103963.1103968]
• 17: Michael Elkin, A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281128]
• 18: M. Elkin. Streaming and fully dynamic centralized algorithms for maintaining sparse spanners. In Proc. 34th Int'l Colloq. on Automata, Languages, and Programming (ICALP), pages 716--727, 2007.
• 19: Michael Elkin , David Peleg, (1 + &egr;&Bgr;)-spanner constructions for general graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.173-182, July 2001, Hersonissos, Greece [doi>10.1145/380752.380797]
• 20: Michael Elkin , David Peleg, $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs, SIAM Journal on Computing, v.33 n.3, p.608-631, 2004 [doi>10.1137/S0097539701393384]
• 21: M. Elkin and J. Zhang. Efficient algorithms for constructing (1 ε,β)-spanners in the distributed and streaming models. Distributed Computing, 18(5):375--385, 2006.
• 22: P. Erdos. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29--36. Publ. House Czechoslovak Acad. Sci., Prague, 1963.
• 23: Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, Graph distances in the streaming model: the value of space, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 24: Giri Narasimhan , Michiel Smid, Geometric Spanner Networks, Cambridge University Press, New York, NY, 2007
• 25: A. Panconesi. Personal communication, 2008.
• 26: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 27: S. Pettie. Low distortion spanners. In Proc. 34th Int'l Colloq. on Automata, Languages, and Programming (ICALP), pages 78--89, 2007.
• 28: L. Roditty, M. Thorup, and U. Zwick. Deterministic constructions of approximate distance oracles and spanners. In Proc. 32nd Int'l Colloq. on Automata, Lang., and Prog. (ICALP), pages 261--272, 2005.
• 29: L. Roditty and U. Zwick. On dynamic shortest paths problems. In Proc. 12th Annual European Symposium on Algorithms (ESA), pages 580--591, 2004.
• 30: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 31: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005 [doi>10.1145/1044731.1044732]
• 32: Mikkel Thorup , Uri Zwick, Spanners and emulators with sublinear distance errors, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.802-809, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109645]
• 33: R. Wenger, Extremal graphs with no C4,s, or C10,s, Journal of Combinatorial Theory Series B, v.52 n.1, p.113-116, May 1991 [doi>10.1016/0095-8956(91)90097-4]
• 34: David P. Woodruff, Lower Bounds for Additive Spanners, Emulators, and More, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.389-398, October 21-24, 2006 [doi>10.1109/FOCS.2006.45]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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

General Terms:
Algorithms, Theory

Keywords:
spanner