Gossip Algorithm

A gossip algorithm is a decentralized scheme in which a graph vertex exchanges information or performs a computation with no more than one adjacent vertex at a time (Boyd et al. 2006). This differs from gossiping, which asks for the minimum number of communications needed to disseminate every participant's information to all participants.

One common use is solving the average consensus problem. For the standard randomized averaging version, let be a connected graph that is also an undirected graph, and let each graph vertex hold a scalar value . At iteration , a graph edge is selected at random, and its endpoints replace their values by their pairwise average. In vector form, this is

			(1)
			(2)

where and are vectors in the standard basis and is the identity matrix. The matrix is a symmetric projection matrix and a doubly stochastic matrix, so the update preserves the sum of all entries. If the graph is connected and successive selections are independent, with every graph edge having a fixed positive probability of selection, the iterates converge with probability one to the arithmetic mean of the initial values.

For randomized pairwise averaging, the expectation value is also a doubly stochastic matrix. The averaging time is controlled by its second-largest eigenvalue, with a smaller value giving faster convergence. This connects the averaging behavior to an associated random walk, and choosing the edge-selection probabilities to minimize the eigenvalue is a semidefinite programming problem (Boyd et al. 2006).

Gossip communication is also used in decentralized federated learning. Schumann et al. (2026) compared cycle graph, wheel graph, and complete graph client topologies for transformer-based language-model training.