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.)