Simple Dynamics as Algorithms and Models

The theory of Distributed Computing copes with systems composed of computa- tional entities able to interact with each other in order to reach a common goal in the most ecient way. Distributed models are used to study many phenomena that come from di↵erent disciplines such as computer science, physics, modern social sci- ence and biology. Common features of such systems are the lack of central control, a huge number of involved individuals, limited communication and computational power, presence of communication noise and faults propensity. Natural systems are able to solve very challenging tasks, relying on limited communication and com- putational resources, with undistinguishable entities. Moreover, at the right level of abstraction, natural and artificial systems solve the same problems: consensus, synchronization, fault tolerance and noise overcoming are some of them. Recently, these observations led researchers in the field to focus on the design and the analysis of simple and light-weight distributed protocols. This line of research includes the analysis of those processes that go by the name of Dynamics. Dynamics are simple stochastic processes on anonymous networks that evolve in rounds and in which each node has an initial state and updates it over time according to a function of its state and the states of its neighbors. Measures of interest in this kind of processes are the number of rounds needed to achieve the desired configuration, the storage capacity of every node and the size of the exchanged messages. In this thesis, we move a step forward in the analysis of dynamics and their ability to solve community detection and consensus problems. In the first part, we formally prove the e↵ectiveness of the Averaging dynamics in solving the community detection problem on a class of graphs containing a hidden k partition and characterized by a mild form of regularity. In the second part, we study the consensus time of some dynamics based on majority rules, introducing di↵erent forms of bias. In particular, in the context of opinion dynamics we define a unified framework to investigate di↵erent update rules when a bias toward one of the two possible opinions exists. The results show that the consensus time is extremely a↵ected by the underlying network structure and opinion dynamics and their interplay may elicit quite di↵erent collective behaviors. Finally, we analyze the k-Majority dynamics in a biased communication model where nodes have some probability to see a fixed state in their neighbors, as if in presence of binary asymmetric communication channels. In this setting, we identify sharp phase transitions on the bias and on the initial configuration.