Déjà Vu: A Minimalistic Mechanism for Distributed Plurality Consensus
For distributed systems with simple agents, this work provides a parameter-free consensus protocol that matches or outperforms existing methods in communication efficiency.
The paper introduces Déjà Vu, a simple mechanism for distributed plurality consensus where agents update their opinion upon encountering a duplicate opinion from neighbors. The analysis shows it is competitive with h-majority and can be more communication-efficient in some regimes.
We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of k opinions, aims to agree on the initially most frequent one. In this setting, h-majority is arguably the simplest and most studied protocol, in which each agent samples the opinion of h neighbors uniformly at random and updates its opinion to the most frequent value in the sample. We propose a new, extremely simple mechanism called Déjà Vu: an agent queries neighbors until it encounters an opinion for the second time, at which point it updates its own opinion to the duplicate value. This rule does not require agents to maintain counters or estimate frequencies, nor to choose any parameter (such as a sample size h); it relies solely on the primitive ability to detect repetition. We provide a rigorous analysis of Déjà Vu that relies on several technical ideas of independent interest and demonstrates that it is competitive with h-majority and, in some regimes, substantially more communication-efficient, thus yielding a powerful primitive for plurality consensus.