5 citations · 8 across the 4 of their papers we have counts for
6 papers · 1 filter
Parallel Load Balancing on Constrained Client-Server Topologies
Andrea Clementi, Emanuele Natale, Isabella Ziccardi
We study parallel \emph{Load Balancing} protocols for a client-server distributed model defined as follows. There is a set $\sC$ of clients and a set $\sS$ of servers where…
On the Necessary Memory to Compute the Plurality in Multi-Agent Systems
Emanuele Natale, Iliad Ramezani
We consider the Relative-Majority Problem (also known as Plurality), in which, given a multi-agent system where each agent is initially provided an input value out of a set of …
Finding a Bounded-Degree Expander Inside a Dense One
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if is a -regular dense expander then there is an edge-induced subgraph $H=(V…
Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise
Andrea Clementi, Luciano Gualà, Emanuele Natale +3
Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast,…
Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation
Luca Becchetti, Vincenzo Bonifaci, Emanuele Natale
The computation of electrical flows is a crucial primitive for many recently proposed optimization algorithms on weighted networks. While typically implemented as a centralized sub…
Ignore or Comply? On Breaking Symmetry in Consensus
Petra Berenbrink, Andrea Clementi, Robert Elsässer +3
We study consensus processes on the complete graph of nodes. Initially, each node supports one from up to n opinions. Nodes randomly and in parallel sample the opinions of cons…