Lune

SODA2024Top-tier venue

The Minority Dynamics and the Power of Synchronicity

Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, Isabella Ziccardi

Abstract

We study the minority-opinion dynamics over a fully-connected network of n nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at random. Each activated node then adopts the opinion that is least common within the received sample.

Unlike all other known consensus dynamics, we prove that this elementary protocol behaves in dramatically different ways, depending on whether activations occur sequentially or in parallel. Specifically, we show that its expected consensus time is exponential in n under asynchronous models, such as asynchronous GOSSIP. On the other hand, despite its chaotic nature, we show that it converges within O(log 2 n) rounds with high probability under synchronous models, such as synchronous GOSSIP.

Finally, our results shed light on the bit-dissemination problem, that was previously introduced to model the spread of information in biological scenarios. Specifically, our analysis implies that the minority-opinion dynamics is the first stateless solution to this problem, in the parallel passive-communication setting, achieving convergence within a polylogarithmic number of rounds. This, together with a known lower bound for sequential stateless dynamics, implies a parallel-vs-sequential gap for this problem that is nearly quadratic in the number n of nodes. This is in contrast to all known results for problems in this area, which exhibit a linear gap between the parallel and the sequential setting.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Asynchronous 3-Majority Dynamics with Many OpinionsColin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu et al.SODA 2025 · 3 citations

Builds on1

  1. Self-Stabilizing Clock Synchronization with 1-bit MessagesPaul Bastide, George Giakkoupis, Hayk SaribekyanSODA 2021 · 6 citations

Related papers

  1. Fast Consensus via the Unconstrained Undecided State DynamicsGregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer et al.SODA 2022 · 12 citations
  2. A time and space optimal stable population protocol solving exact majorityDavid Doty, Mahsa Eftekhari, Leszek Gasieniec, Eric E. Severson et al.FOCS 2021 · 17 citations
  3. A Phase Transition for Opinion Dynamics with Competing BiasesFederico Capannoli, Emilio Cruciani, Hlafo Alfie Mimun, Matteo QuattropaniAAAI 2026
  4. Space-efficient population protocols for exact majority on general graphsJoel Rybicki, Jakob Solnerzik, Olivier Stietel, Robin VacusSODA 2026
  5. Convergence of Opinion Diffusion is PSPACE-CompleteDmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo TurriniAAAI 2020 · 28 citations
Dusk over the sea between two cliffs drawn in fine vertical lines