Speaker: Luca Trevisan (U.C. Berkeley and Simons Institute for the Theory of Computing)
When: WEDNESDAY, June 14th, 2017 — 15:30 – 16:30
Where: Room A1.3, first floor, Alan Turing building (Coppito 0).
Title: 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 it updates its state to be “more like” the state of the neighbors. In a discrete setting, where there is a finite set of possible states, each node node updates to the state held by a plurality of sampled neighbors. Here we show that, in a complete communication network, there is a quick convergence to a consensus, regardless of the initial configuration and even in the presence of adversarial faults. If the set of possible states is ordered, and nodes update to the median of neighbors, convergence was known to be even faster, but less robust to adversarial tampering. In a continuous setting, each node holds a bounded real number, and it updates to the average of sampled neighbors. Here we show that if the graph has a clustered structure, such as the one generated by the stochastic block model, the nodes can identify the cluster they belong to based on the evolution of the local state. This holds even in an asynchronous model in which only two nodes are active at a time, and the study of the latter setting leads to interesting questions about the concentration of the product of iid random matrices.
(Based on joint work with Luca Becchetti, Andrea Clementi, Pasin Manurangsi,Emanuele Natale, Francesco Pasquale, Prasad Raghavendra and Riccardo Silvestri)