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 : ℝn → ℝn. 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.