Consensus Algorithms in Dynamical Network Systems

Sammanfattning: Dynamical network systems are complex interconnected systems describing many real world problems. The current trend is to connect more and more systems together, and at the same time requiring continuous availability. To this end, it is crucial to understand the dynamic behaviors of networked systems.This thesis makes three contributions in this area.First, we study the important problem of gathering data that are distributed among the nodes in a network. Two specific tasks are considered: to estimate the size of the network, and to aggregate the distribution of local measurements generated by the nodes. We consider a framework where the nodes require anonymity, and restricted computational resources. We propose probabilistic algorithms with low resource requirements, that quickly generate arbitrarily accurate estimates. For dynamical networks, we improve the accuracy through a regularization term which captures the trade-off between the gathered data and a-priori assumptions on the dynamics.In the second part of this thesis, we consider a dynamical network system where one node is misbehaving due to a failure. We specifically seek robustness conditions that guarantee that the entire network system is still functional. The nodes' dynamics is governed by consensus updates, and we present thresholds on the interaction strengths that determines if the system will reach consensus, or if the system will diverge.Finally, a P2P network is utilized to improve a live-streaming media application. In particular, we study how an overlay network, constructed from simple preference functions, can be used to build efficient topologies that reduce both network latency and interruptions. We present necessary and sufficient convergence conditions, as well as convergence speed estimates, and demonstrate the improvements for a real P2P video streaming application.