cs.DCApr 4, 2026

DejaVu: A Minimalistic Mechanism for Distributed Plurality Consensus

Authors: Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, Frédéric Giroire, Emanuele Natale

Organizations: Gran Sasso Science Institute, Italy · INRIA, COATI, Université Côte d’Azur, France · INRIA Rennes

Abstract

We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of kk opinions, aims to agree on the initially most frequent one. In this setting, hh-majority is arguably the simplest and most studied protocol, in which each agent samples the opinion of hh 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 hh); 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 hh-majority and, in some regimes, substantially more communication-efficient, thus yielding a powerful primitive for plurality consensus.

Explore similar work

CardsList
  1. EMS: Multi-Agent Voting via Efficient Majority-then-Stopping

    Apr 3, 2026Yiqing Liu, Hantao Yao, Wu Liu +1Multi-Agent ReasoningEarly Stopping

  2. The End of Consensus Research?

    Oct 21, 2026Clément Burgelin, Rachid Guerraoui, Zicong Hong +5Autonomous Research Agents

  3. Decentralized Ranking Aggregation via Gossip: Convergence and Robustness

    Feb 26, 2026Kerrian Le Caillec, Anna Van Elst, Igor Colin +1Rank AggregationMulti-Agent Consensus