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