5 papers
Cutting Bamboo Down to Size
Davide Bilò, Luciano Gualà, Stefano Leucci +2
This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of bambo…
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,…
Distributed Community Detection via Metastability of the 2-Choices Dynamics
Emilio Cruciani, Emanuele Natale, Giacomo Scornavacca
We investigate the behavior of a simple majority dynamics on networks of agents whose interaction topology exhibits a community structure. By leveraging recent advancements in the…
Phase Transition of the 2-Choices Dynamics on Core-Periphery Networks
Emilio Cruciani, Emanuele Natale, André Nusser +1
Consider the following process on a network: Each agent initially holds either opinion blue or red; then, in each round, each agent looks at two random neighbors and, if the two ha…
Rational Fair Consensus in the GOSSIP Model
Andrea Clementi, Luciano Gualà, Guido Proietti +1
The \emph{rational fair consensus problem} can be informally defined as follows. Consider a network of (selfish) \emph{rational agents}, each of them initially supporting a \em…