We consider a multi agent optimization problem where a set of agents collectively solves a global optimization problem with the objective function given by the sum of locally known convex functions. We focus on the case when information exchange among agents takes place over a directed network and propose a distributed subgradient algorithm in which each agent performs local processing based on information obtained from his incoming neighbors. Our algorithm uses weight balancing to overcome the asymmetries caused by the directed communication network, i.e., agents scale their outgoing information with dynamically updated weights that converge to balancing weights of the graph. We show that both the objective function values and the consensus violation, at the ergodic average of the estimates generated by the algorithm, converge with rate @math , where @math is the number of iterations. A special case of our algorithm provides a new distributed method to compute average consensus over directed graphs.
A weighted digraph is balanced if, for each node, the sum of the weights of the edges outgoing from that node is equal to the sum of the weights of the edges incoming to that node. Weight-balanced digraphs play a key role in a number of applications, including cooperative control, distributed optimization, and distributed averaging problems. We address the weight-balance problem for a distributed system whose components (nodes) can exchange information via interconnection links (edges) that form an arbitrary, possibly directed, communication topology (digraph). We develop two iterative algorithms, a centralized one and a distributed one, both of which can be used to reach weight-balance, as long as the underlying communication topology forms a strongly connected digraph (or is a collection of strongly connected digraphs). The centralized algorithm is shown to reach weight-balance after a finite number of iterations (bounded by the number of nodes in the graph). The distributed algorithm operates by having each node adapt the weights on its outgoing edges and is shown to asymptotically lead to weight-balance. We also analyze the rate of convergence of the proposed distributed algorithm and obtain a (graph-dependent) worst-case bound for it. Finally, we provide examples to illustrate the operation, performance, and potential advantages of the proposed algorithms. Over the last decade, we have seen a revolution in connectivity between computers, and a resulting paradigm shift from centralized to highly distributed systems. With massive scale also comes massive instability, as node and link failures become the norm rather than the exception. For such highly volatile systems, decentralized gossip-based protocols are emerging as an approach to maintaining simplicity and scalability while achieving fault-tolerant information dissemination. In this paper, we study the problem of computing aggregates with gossip-style protocols. Our first contribution is an analysis of simple gossip-based protocols for the computation of sums, averages, random samples, quantiles, and other aggregate functions, and we show that our protocols converge exponentially fast to the true answer when using uniform gossip. Our second contribution is the definition of a precise notion of the speed with which a node's data diffuses through the network. We show that this diffusion speed is at the heart of the approximation guarantees for all of the above problems. We analyze the diffusion speed of uniform gossip in the presence of node and link failures, as well as for flooding-based mechanisms. The latter expose interesting connections to random walks on graphs.   We propose a class of distributed iterative algorithms that enable the asymptotic scaling of a primitive column stochastic matrix, with a given sparsity structure, to a doubly stochastic form. We also demonstrate the application of these algorithms to the average consensus problem in networked multi-component systems. More specifically, we consider a setting where each node is in charge of assigning weights on its outgoing edges based on the weights on its incoming edges. We establish that, as long as the (generally directed) graph that describes the communication links between components is strongly connected, each of the proposed matrix scaling algorithms allows the system components to asymptotically assign, in a distributed fashion, weights that comprise a primitive doubly stochastic matrix. We also show that the nodes can asymptotically reach average consensus by executing a linear iteration that uses the time-varying weights (as they result at the end of each iteration of the chosen matrix scaling algorithm). In this work we propose a distributed algorithm to solve the discrete-time average consensus problem on strongly connected weighted digraphs (SCWDs). The key idea is to couple the computation of the average with the estimation of the left eigenvector associated with the zero eigenvalue of the Laplacian matrix according to the protocol described in (2012). The major contribution is the removal of the requirement of the knowledge of the out-neighborhood of an agent, thus paving the way for a simple implementation based on a pure broadcast-based communication scheme.  In this work we propose a decentralized algorithm for balancing a strongly connected weighted digraph. This algorithm relies on the decentralized estimation of the left eigenvector associated to the zero structural eigenvalue of the Laplacian matrix. The estimation is performed through the distributed computation of the powers of the Laplacian matrix itself. This information can be locally used by each agent to modify the weights of its incoming edges so that their sum is equal to the sum of the weights outgoing this agent, i.e., the weighted digraph is balanced. Simulation results are proposed to corroborate the theoretical results. In a recent Physical Review Letters article, propose a simple but compelling discrete-time model of n autonomous agents (i.e., points or particles) all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of its own heading plus the headings of its "neighbors." In their paper, provide simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent's set of nearest neighbors change with time as the system evolves. This paper provides a theoretical explanation for this observed behavior. In addition, convergence results are derived for several other similarly inspired models. The Vicsek model proves to be a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function.  