## Some Simple Distributed Network Processes

by Luca Becchetti, Andrea Clementi, Pasin Manurangsi,
Emanuele Natale, Francesco Pasquale, Prasad Raghavendra,m
and Luca Trevisan.

#### Oded's comments

The talk describes a variety of models that fall under the general
theme of simple network protocols in which each processor updates
its state to be "closer" to the states of its neighbors.
The results refer both to the complete graph, expander graphs,
and graphs consisting of few expanders that are "lightly" connected.
In some cases the results regarding the last type of networks
yield distributed algorithms for finding these expanders
(which may be viewed as "strongly connected" components
in a non-standard sense of this term).
Some of the latter results require that the connections
between the different expanders are not too sparse,
and I believe that a model that allows to communicate
also to random vertices in the graph may be beneficial
and allow to waive the latter requirement.

#### The original abstract

We will describe network processes in which, at each step, each node
communicates with its neighbors, or a random subset of its neighbors,
and 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 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.

Back to
list of Oded's choices.