Broadcast and Gossip Stochastic Average Consensus Algorithms in Directed Topologies

We address the problem of a set of agents reaching consensus by computing the average of their initial states. We propose two randomized algorithms over a directed communication graph where either a random node broadcast its value or a randomly selected pair of nodes communicate in a distributed fashion. The proposed algorithms guarantee convergence in three important definitions, namely: almost surely, in expectation, and in the mean-square sense. We show how the parameters of the algorithm can be optimized to improve the rate of convergence and compare its rates of convergence for directed and undirected graphs.