COLLOQUIUM DI MATEMATICA

Luca Trevisan
U.C. Berkeley


Titolo: Some simple distributed network processes

Mercoledi' 12 Giugno 2019 ORE 16:00

Dipartimento di Matematica e Fisica 
Universita' degli Studi Roma Tre
Aula M3, edificio Aule - Largo San Leonardo Murialdo,1

Abstract
We will describe network processes in which, at each step, each node
communicates with its neighbors, or a random subset of neighbors, and
updates its state according to the outcome of these communications. We
will first talk about processes in which each node  updates its state
to be "more like" the state of the neighbors. In a complete
communication network, such protocols provide a solution to the
problem of reaching a consensus, and they do so in a way that is
robust to adversarial interventions. In a communication network with a
clustered structure, such protocols give a decentralized solution to
the community detection problem. We will then discuss a protocol in
which each node wants to choose a constant number of neighbors in such
a way that the resulting constant-degree subnet of the communication
network is an expander. This is done in a way to similar to how
virtual networks are formed in peer-to-peer protocols. We show that if
the original communication network is a dense expanders, the protocol
will construct a constant-degree expander. 
 (Based on joint work with Luca Becchetti, Andrea Clementi, Pasin
Manurangsi, Emanuele Natale, Francesco Pasquale and Prasad
Raghavendra.)