Necessary Conditions and Sufficient Conditions for Finding a Common Fixed Point of a Family of Maps Using a Distributed Algorithm

This paper is concerned with necessary conditions and sufficient conditions which ensure convergence of a distributed algorithm for computing a common fixed point of a family of m > 1 nonlinear maps M_i : ⁿ → ⁿ. Each agent i knows the map M_i and receives entries of the state vectors of its current neighbors at each time t. Using only this information, each agent recursively updates its own estimate of a common fixed point. Under the assumption of non-redundancy, and for arbitrary nonlinear maps M_i, it is shown that a nonuniformly strongly connected sequence of neighbor graphs is necessary to ensure the distributed algorithm causes all agent estimates to converge to the same common fixed point. Furthermore, sufficient conditions requiring that the maps M_i be paracontractions are provided which ensure all agent estimates to converge to the same common fixed point. In the case considering doubly stochastic weight matrices and maps M_i which are paracontractions with respect to the 2-norm, both necessary and sufficient conditions are provided. Finally, necessary and sufficient conditions are given which relax the condition of non-redundancy and allow for more complicated interactions between the sequence of neighbor graphs and the sets of fixed points.