Colloquium di Matematica - Some simple distributed network processes

Link identifier #identifier__10398-1Link identifier #identifier__163906-2

12 Giugno 2019, ore 16:00
Dipartimento di Matematica e Fisica, Aula M3 (edificio nuovo)
Largo San Leonardo Murialdo, 1 palazzina C - Roma

Mercoledì 12 giugno 2019 alle ore 16:00 il Dipartimento di Matematica e Fisica, ospiterà il Colloquium di Matematica del prof. Luca Trevisan dal titolo "Some simple distributed network processes".

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

Per informazioni:
Filippo Viviani
Link identifier #identifier__155127-1viviani@mat.uniroma3.it