Consensus algorithms in decentralized networks

We consider a decentralized network with the following goal: the state at each node of the network iteratively converges to the same value. Ensuring that this goal is achieved requires certain properties of the topology of the network and the function describing the evolution of the network. We will present these properties for deterministic systems, extending current results in the literature. As an additional contribution, we will show how the convergence results for stochastic systems are direct consequences of the corresponding deterministic systems, drastically simplifying many other current results. In general, these consensus systems can be both time invariant and time varying, and we will extend all our deterministic and stochastic results to include time varying systems as well. We will then consider a more complex consensus problem, the resource allocation problem. In this situation each node of the network has both a state and a capacity. The capacity is a monotone increasing function of the state, and the goal is for the nodes to exchange capacity in a decentralized manner in order to drive all of the states to the same value. Conditions ensuring consensus in the deterministic setting will be presented, and we will show how convergence in this system also comes from the fundamental deterministic result for consensus algorithms. The main results will again be extended to stochastic and time varying systems. The linear consensus system requires the construction of a matrix of weighting parameters with specific properties. We present an iterative algorithm for determining the weighting parameters in a decentralized fashion; the weighting parameters are specified by the nodes and each node only specifies the weighting parameters as sociated with that node. The results assume that the communication graph of the network is directed, and we consider both synchronous communication, and stochastic asynchronous networks