Robust Distributed Orthogonalization Based on Randomized Aggregation

The construction of distributed algorithms for matrix com-putations built on top of distributed data aggregation al-gorithms with randomized communication schedules is in-vestigated. For this purpose, a new aggregation algorithm for summing or averaging distributed values, the push-flow algorithm, is developed, which achieves superior resilience properties with respect to node failures compared to existing aggregation methods. On a hypercube topology it asymptot-ically requires the same number of iterations as the optimal all-to-all reduction operation and it scales well with the num-ber of nodes. Orthogonalization is studied as a prototypical matrix computation task. A new fault tolerant distributed orthogonalization method (rdmGS), which can produce ac-curate results even in the presence of node failures, is built on top of distributed data aggregation algorithms