  In this work and the supporting Parts II [2] and III [3], we provide a rather
detailed analysis of the stability and performance of asynchronous strategies
for solving distributed optimization and adaptation problems over networks. We
examine asynchronous networks that are subject to fairly general sources of
uncertainties, such as changing topologies, random link failures, random data
arrival times, and agents turning on and off randomly. Under this model, agents
in the network may stop updating their solutions or may stop sending or
receiving information in a random manner and without coordination with other
agents. We establish in Part I conditions on the first and second-order moments
of the relevant parameter distributions to ensure mean-square stable behavior.
We derive in Part II expressions that reveal how the various parameters of the
asynchronous behavior influence network performance. We compare in Part III the
performance of asynchronous networks to the performance of both centralized
solutions and synchronous networks. One notable conclusion is that the
mean-square-error performance of asynchronous networks shows a degradation only
of the order of $O(\nu)$, where $\nu$ is a small step-size parameter, while the
convergence rate remains largely unaltered. The results provide a solid
justification for the remarkable resilience of cooperative networks in the face
of random failures at multiple levels: agents, links, data arrivals, and
topology.
