Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures

ABSTRACT

Tree structures such as breadth-first search (BFS) trees and minimum spanning trees (MST) are among the most fundamental graph structures in distributed network algorithms. However, by definition, these structures are not robust against failures and even a single edge's removal can disrupt their functionality. A well-studied concept which attempts to circumvent this issue is Fault-Tolerant Tree Structures, where the tree gets augmented with additional edges from the network so that the functionality of the structure is maintained even when an edge fails. These structures, or other equivalent formulations, have been studied extensively from a centralized viewpoint. However, despite the fact that the main motivations come from distributed networks, their distributed construction has not been addressed before.

In this paper, we present distributed algorithms for constructing fault tolerant BFS and MST structures. The time complexity of our algorithms are nearly optimal in the following strong sense: they almost match even the lower bounds of constructing (basic) BFS and MST trees.

References

1. Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2004.
2. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Fault-tolerant approximate shortest-path trees. In Algorithms-ESA 2014, pages 137--148. Springer, 2014.
3. Surender Baswana and Neelesh Khanna. Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs. Algorithmica, 66(1):18--50, 2013.
4. FRK Chung and MR Garey. Diameter bounds for altered graphs. Journal of Graph Theory, 8(4):511--534, 1984.
5. Lecture notes on k-wise uniform (randomness) generators. http://pages.cs.wisc.edu/ dieter/Courses/2013s-CS880/Scribes/PDF/lecture04.pdf. Accessed: 2015-02.
6. Shiri Chechik and David Peleg. Rigid and competitive fault tolerance for logical information structures in networks. In Electrical and Electronics Engineers in Israel (IEEEI), 2010 IEEE 26th Convention of, pages 000024--000025. IEEE, 2010.
7. Ajoy K Datta, Lawrence L Larmore, Linda Pagli, and Giuseppe Prencipe. Linear time distributed swap edge algorithms. In Algorithms and Complexity, pages 122--133. Springer, 2013.
8. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In Proc. of the Symp. on Theory of Comp. (STOC), pages 363--372, 2011.
9. Michael Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In Proc. of the Symp. on Theory of Comp. (STOC), pages 331--340, 2004.
10. Paola Flocchini, T Enriquez, Linda Pagli, Giuseppe Prencipe, and Nicola Santoro. Distributed minimum spanning tree maintenance for transient node failures. Computers, IEEE Transactions on, 61(3):408--414, 2012.
11. Mohsen Ghaffari. Near-optimal scheduling of distributed algorithms. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 3--12, 2015.
12. Zvi Gotthilf and Moshe Lewenstein. Improved algorithms for the k simple shortest paths and the replacement paths problems. Information Processing Letters, 109(7):352--355, 2009.
13. Beat Gfeller, Nicola Santoro, and Peter Widmayer. A distributed algorithm for finding all best swap edges of a minimum-diameter spanning tree. Dependable and Secure Computing, IEEE Transactions on, 8(1):1--12, 2011.
14. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 748--757. IEEE, 2012.
15. John Hershberger and Subhash Suri. Vickrey prices and shortest paths: What is an edge worth? In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 252--259. IEEE, 2001.
16. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 355--364, 2012.
17. Shay Kutten and David Peleg. Fast distributed construction of k-dominating sets and applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC), pages 238--251, 1995.
18. Frank Thomson Leighton, Bruce M Maggs, and Satish B Rao. Packet routing and job-shop scheduling in O(congestion+dilation) steps. Combinatorica, 14(2):167--186, 1994.
19. Kavindra Malik, AK Mittal, and Santosh K Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters, 8(4):223--227, 1989.
20. Noam Nisan and Amir Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 129--140. ACM, 1999.
21. Enrico Nardelli, Ulrike Stege, and Peter Widmayer. Low-cost Fault-tolerant Spanning Graphs for Point Aets in the Euclidean Plane. 1997.
22. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.
23. Seth Pettie. Sensitivity analysis of minimum spanning trees in sub-inverse-ackermann time. Algorithms and Computation, pages 964--973, 2005.
24. Merav Parter and David Peleg. Sparse fault-tolerant BFS trees. In the Proceedings of the Annual European Symposium on Algorithms, pages 779--790, 2013.
25. Merav Parter and David Peleg. Fault tolerant approximate bfs structures. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1073--1092. SIAM, 2014.
26. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed MST construction. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 253--, 1999.
27. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Transactions on Algorithms (TALG), 8(4):33, 2012.
28. Jeanette P Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223--250, 1995.
29. Robert Endre Tarjan. Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees. Inf. Process. Lett., 14(1):30--33, 1982.
30. Virginia Vassilevska Williams. Faster replacement paths. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1337--1346. SIAM, 2011.
31. Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Transactions on Algorithms (TALG), 9(2):14, 2013.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Networks

  • Network algorithms

• Theory of computation

  • Design and analysis of algorithms

    • Distributed algorithms