4 papers · 1 filter
DejaVu: A Minimalistic Mechanism for Distributed Plurality Consensus
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis +2
We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of opinions, aims to agree on the init…
On the -majority dynamics with many opinions
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis +1
We present the first upper bound on the convergence time to consensus of the well-known -majority dynamics with opinions, in the synchronous setting, for and that ar…
Threshold-Driven Streaming Graph: Expansion and Rumor Spreading
Flora Angileri, Andrea Clementi, Emanuele Natale +2
A randomized distributed algorithm called RAES was introduced in [Becchetti et al., SODA 2020] to extract a bounded-degree expander from a dense -vertex expander graph $G = (V,…
Fast and Robust Information Spreading in the Noisy PULL Model
Niccolò D'Archivio, Amos Korman, Emanuele Natale +1
Understanding how information can efficiently spread in distributed systems under noisy communications is a fundamental question in both biological research and artificial system d…