Fault Tolerance Properties of Gossip-Based Distributed Orthogonal Iteration Methods

In this paper, we investigate and compare the fault tolerance properties and resilience of gossip-based distributed orthogonal iteration algorithms for the in-network computation of the extreme eigenpairs of matrix. Gossip-based algorithms have many attractive properties, especially for loosely coupled distributed and decentralized systems, like P2P networks or sensor networks. Due to their randomized communication schedule and the fact that communication happens only between nearest neighbors, they are highly flexible with respect to the topology of the underlying system. Moreover, such algorithms have a big potential for high resilience against various types of failures. Lately, several gossip-based distributed eigensolvers based on orthogonal iteration method have been introduced. However, the performance of these algorithms in the presence of failures has not been analyzed yet. We illustrate that convergence properties, the numerical accuracy achieved, as well as resilience properties of gossip-based distributed orthogonal iteration are basically determined by the choice of the distributed data aggregation algorithm (DDAA) which is required within the algorithm for performing distributed reduction operations (such as summation or averaging) across the system. In particular, we illustrate that when using the proper combination of DDAA and distributed orthogonal iteration method, high accuracy can be achieved and even silent message loss can be tolerated without any loss in numerical accuracy.