Information Propagation Algorithms for Consensus Formation in Decentralized Multi-Agent Systems

Consensus occurs within a multi-agent system when every agent is in agreement about the value of some particular state. For example, the color of an LED, the position or magnitude of a vector, a rendezvous location, the most recent state of data within a database, or the identity of a leader are all states that agents might need to agree on in order to execute their tasking. The task of the decentralized consensus problem for multi-agent systems is to design an algorithm that enables agents to communicate and exchange information such that, in finite time, agents are able to form a consensus without the use of a centralized control mechanism. The primary goal of this research is to introduce and provide supporting evidence for Stochastic Local Observation/Gossip (SLOG) algorithms as a new class of solutions to the decentralized consensus problem for multi-agent systems that lack a centralized controller, with the additional constraints that agents act asynchronously, information is discrete, and all consensus options are equally preferable to all agents. Examples of where these constraints might apply include the spread of social norms and conventions in artificial populations, rendezvous among a set of specific locations, and task assignment. This goal is achieved through a combination of theory and experimentation. Information propagation process and an information propagation algorithm are derived by unifying the general structure of multiple existing solutions to the decentralized consensus problem. They are then used to define two classes of algorithms that spread information across a network and solve the decentralized consensus problem: buffered gossip algorithms and local observation algorithms. Buffered gossip algorithms generalize the behavior of many push-based solutions to the decentralized consensus problem. Local observation algorithms generalize the behavior of many pull-based solutions to the decentralized consensus problem. In the language of object oriented design, buffered gossip algorithms and local observation algorithms are abstract classes; information propagation processes are interfaces. SLOG algorithms combine the transmission mechanisms of buffered gossip algorithms and local observation algorithms into a single hybrid algorithm that is able to push and pull information within the local neighborhood. A common mathematical framework is constructed and used to determine the conditions under which each of these algorithms are guaranteed to produce a consensus, and thus solve the decentralized consensus problem. Finally, a series of simulation experiments are conducted to study the performance of SLOG algorithms. These experiments compare the average speed of consensus formation between buffered gossip algorithms, local observation algorithms, and SLOG algorithms over four distinct network topologies. Beyond the introduction of the SLOG algorithm, this research also contributes to the existing literature on the decentralized consensus problem by: specifying a theoretical framework that can be used to explore the consensus behavior of push-based and pull-based information propagation algorithms; using this framework to define buffered gossip algorithms and local observation algorithms as generalizations for existing solutions to the decentralized consensus problem; highlighting the similarities between consensus algorithms within control theory and opinion dynamics within computational sociology, and showing how these research areas can be successfully combined to create new and powerful algorithms; and providing an empirical comparison between multiple information propagation algorithms