The basic version of the consensus problem is the network averaging problem.

We apply the Min-Sum message-passing protocol to solve the consensus problem in distributed optimization. We show that while the ordinary Min-Sum algorithm does not converge, a modified version of it known as Splitting yields convergence to the problem solution. We prove that a proper choice of the tuning parameters allows Min-Sum Splitting to yield subdiffusive accelerated convergence rates, matching the rates obtained by shift-register methods. The acceleration scheme embodied by Min-Sum Splitting for the consensus problem bears similarities with lifted Markov chains techniques and with multi-step first order methods in convex optimization.

Consensus planning is a method for coordinating decision making across complex systems and organizations, including complex supply chain optimization pipelines. It arises when large interdependent distributed agents (systems) share common resources and must act in order to achieve a joint goal. In this paper, we introduce a generic Consensus Planning Protocol (CPP) to solve such problems. Our protocol allows for different agents to interact with the coordinating algorithm in different ways (e.g., as a primal or dual or proximal agent). In prior consensus planning work, all agents have been assumed to have the same interaction pattern (e.g., all dual agents or all primal agents or all proximal agents), most commonly using the Alternating Direction Method of Multipliers (ADMM) as proximal agents. However, this is often not a valid assumption in practice, where agents consist of large complex systems, and where we might not have the luxury of modifying these large complex systems at will. Our generic CPP allows for any mix of agents by combining ADMM-like updates for the proximal agents, dual ascent updates for the dual agents, and linearized ADMM updates for the primal agents. We prove convergence results for the generic CPP, namely a sublinear O(1/k) convergence rate under mild assumptions, and two-step linear convergence under stronger assumptions. We also discuss enhancements to the basic method and provide illustrative empirical results.

This article considers consensus problem of multiagent systems with double integrator dynamics under nonuniform sampling. It is considered the maximum sampling time can be selected arbitrarily. Moreover, the communication graph can change to any possible topology as long as its associated graph Laplacian has eigenvalues in a given region, which can be selected arbitrarily. Existence of a controller that ensures consensus in this setting is shown when the changing topology graphs are balanced and has a spanning tree. Also, explicit bounds for controller parameters are given. A novel sufficient condition is given to solve the consensus problem based on making the closed loop system matrix a contraction using a particular coordinate system for general linear dynamics. It is shown that the given condition immediately generalizes to changing topology in the case of balanced topology graphs. This condition is applied to double integrator dynamics to obtain explicit bounds on the controller.

Although the consensus problem has been extensively investigated, the ties among agents are assumed to be characterized by scalar-weighted networks, which fail in characterizing interdependencies among higher-dimensional states of neighboring agents. Recently, a broader category of networks termed matrix-weighted networks has been introduced which is an immediate generalization of scalar-weighted networks Sun and Yu [27], Pan et al. [23, 20], Trinh et al. [28], Pan et al. [21, 22], Wang et al. [30], Pan et al. [19]. In fact, matrix-weighted networks naturally become relevant in scenarios such as graph effective resistance based distributed control and estimation Barooah and Hespanha [2], logical inter-dependency of multiple topics in opinion evolution Friedkin et al. [8], bearing-based formation control Zhao and Zelazo [37], array of coupled LC oscillators Tuna [29] as well as consensus and synchronization on matrix-weighted networks Trinh et al. [28], Pan et al. [20]. As opposed to scalar-weighted networks, connectivity alone does not translate to achieving consensus for matrixweighted networks. To this end, properties of weight matrices play an important role in characterizing consensus. For instance, positive definiteness and positive semi-definiteness of weight matrices have been employed to provide consensus conditions in Trinh et al. [28]; negative definiteness and negative semi-definiteness of weight matrices

The consensus problem is a fundamental problem in multi-agent systems which requires a group of processes (or agents) to reliably and timely agree on a single data value. Although extensively discussed in the context of distributed computing it's not exclusive to this field, also being present in our society in a variety of situations such as in democratic elections, the legislative process, jury trial proceedings, and so forth. It's solved through the employment of a consensus protocol governing how processes (agents) interact with one another. It may seem redundant but, to solve the consensus problem, first all processes agree to follow the same consensus protocol. Some of these processes may fail or be unreliable in other ways (such as in a conflict of interest situation) so consensus protocols must be fault tolerant or resilient.

We study alternating minimization for matrix completion in the simplest possible setting: completing a rank-one matrix from a revealed subset of the entries. We bound the asymptotic convergence rate by the variational characterization of eigenvalues of a reversible consensus problem. This leads to a polynomial upper bound on the asymptotic rate in terms of number of nodes as well as the largest degree of the graph of revealed entries.

We apply the Min-Sum message-passing protocol to solve the consensus problem in distributed optimization. We show that while the ordinary Min-Sum algorithm does not converge, a modified version of it known as Splitting yields convergence to the problem solution. We prove that a proper choice of the tuning parameters allows Min-Sum Splitting to yield subdiffusive accelerated convergence rates, matching the rates obtained by shift-register methods. The acceleration scheme embodied by Min-Sum Splitting for the consensus problem bears similarities with lifted Markov chains techniques and with multi-step first order methods in convex optimization.

Graphs are naturally sparse objects that are used to study many problems involving networks, for example, distributed learning and graph signal processing. In some cases, the graph is not given, but must be learned from the problem and available data. Often it is desirable to learn sparse graphs. However, making a graph highly sparse can split the graph into several disconnected components, leading to several separate networks. The main difficulty is that connectedness is often treated as a combinatorial property, making it hard to enforce in e.g. convex optimization problems. In this article, we show how connectedness of undirected graphs can be formulated as an analytical property and can be enforced as a convex constraint. We especially show how the constraint relates to the distributed consensus problem and graph Laplacian learning. Using simulated and real data, we perform experiments to learn sparse and connected graphs from data.

We consider the problem of distributed multi-task learning, where each machine learns a separate, but related, task. Specifically, each machine learns a linear predictor in high-dimensional space,where all tasks share the same small support. We present a communication-efficient estimator based on the debiased lasso and show that it is comparable with the optimal centralized method.