How can agnostic nodes impact consensus in multi-agent systems?
Voter Model Meets Rumour Spreading: A Study of Consensus Protocols on Graphs with Agnostic Nodes [Extended Version]
This paper studies a variant of the voter model, a classic consensus protocol in multi-agent systems, where some agents initially have no opinion (agnostic nodes). It analyzes how these agnostic nodes influence the probability of reaching consensus on a particular opinion and the time it takes to reach consensus.
For LLM-based multi-agent systems, the key takeaways are: (1) Agnostic agents, analogous to LLMs with no initial prompt/context, can be integrated into consensus protocols. (2) The presence of agnostic agents doesn't significantly impact the time bounds for consensus if their information acquisition (becoming gnostic) is faster than overall consensus. (3) A Markov Chain Monte Carlo (MCMC) algorithm can efficiently estimate consensus probabilities even with agnostic agents, offering a practical approach for LLM-based multi-agent simulations and development. This allows developers to predict the likelihood of LLMs converging on a specific output given their initial prompts and interaction dynamics within a multi-agent setup.