Stochastic semistability with application to stochastic consensus

Originally developed in computer science, the consensus (or agreement) problem has become an important research topic in coordination control among mobile agents in recent years. Distributed consensus protocols that utilize each agent's neighboring information as local feedback rules are of particular interest to researchers. In practice, the communication network may be subject to random link failure, which results in a stochastic consensus problem.;In this dissertation, we extend the semistability theory for deterministic systems to stochastic systems with a continuum of equilibrium points. We establish the stochastic semistability theory, which serves as a useful mathematical tool for studying stability properties of stochastic systems with a continuum of equilibrium points. We propose the notion of almost sure semistability, which requires almost sure Lyapunov stability of every equilibrium point as well as almost sure convergence to the equilibrium set. We then develop necessary and sufficient conditions for almost sure Lyapunov stability of an equilibrium point in terms of the notions of restricted prolongation and nontangency. Based on that, we further derive Lyapunov-like sufficient conditions for almost sure Lyapunov stability and almost sure semistability for stochastic systems with a continuum of equilibrium points.;Based on the newly established stochastic semistability theory, we then study the stochastic consensus problem in a unified framework. We formulate the consensus problem in a stochastic setting by modeling the communication link failure process as a continuous-time discrete-value Markov process. We consider communication networks with either bidirectional or unidirectional information flow, with possibly time-varying edge weights, and with possibly time-varying probability distribution of the link failure process. We apply the notion of almost sure semistability to consensus over a random network and define the notion of almost sure consensus. We then derive sufficient conditions for reaching almost sure consensus over a random network by using linear consensus algorithms. We consider the convergence speed of the stochastic linear consensus al- gorithm. We propose convergence factor/time as a measurement for convergence speed and derived lower/upper bounds for convergence factor/time. We also derived sufficient conditions for reaching almost sure consensus over a random network by using nonlinear consensus algorithms. We consider the family of nonlinear consensus algorithms using continuously differentiable functions and derive sufficient conditions for almost sure consensus. We also consider a particular family of nonlinear consensus algorithms using non-continuously differentiable functions. Numerical examples are provided for illustration.