Scalable and fault tolerant orthogonalization based on randomized distributed data aggregation

Area of Science:

• Distributed computing
• Numerical analysis
• Fault-tolerant systems

Background:

• Distributed algorithms are crucial for large-scale matrix computations.
• Existing aggregation methods lack robust resilience to node failures.
• Randomized communication schedules present challenges in distributed settings.

Purpose of the Study:

• To investigate distributed algorithms for matrix computations using data aggregation.
• To develop a novel, resilient aggregation algorithm for distributed environments.
• To introduce a fault-tolerant distributed orthogonalization method.

Main Methods:

• Development of the push-flow algorithm for distributed data aggregation (summing/averaging).
• Analysis of the algorithm's performance and resilience on hypercube topologies.
• Application of the aggregation algorithm to distributed orthogonalization, creating the rdmGS method.

Main Results:

• The push-flow algorithm demonstrates superior resilience to failures compared to existing methods.
• On hypercube networks, push-flow asymptotically matches optimal all-to-all reduction iterations.
• The algorithm exhibits good scalability with an increasing number of nodes.
• The rdmGS method provides accurate results for distributed orthogonalization despite node failures.

Conclusions:

• The push-flow algorithm is an effective and resilient method for distributed data aggregation.
• Distributed matrix computations, like orthogonalization, can be made fault-tolerant using robust aggregation.
• The developed methods offer significant improvements for large-scale, potentially unreliable distributed systems.