Thesis contribution and outline. The essence of this work consists of the analysis of four discrete stochastic processes on graphs in detail, using the knowledge and techniques from probability theory, combinatorics, linear algebra, etc. for the analysis. First, we investigate the Best-of-three voting dynamics for two colours/opinions (with initial colour difference of δ) in a class of non-complete graphs. In this process, at each time-step, every vertex chooses three neighbours at random and adopts the majority colour. We show that the dynamics converges to the initial dominant colour in O(log log n) + O(log(1/δ)) steps with high probability, provided that the underly- ing graph has minimal degree nΩ(1/ log log n) . This, for sufficiently large δ , implies a doubly logarithmic convergence time in sufficiently dense graphs. There is a rich line of research concerning the analysis of simple distributed dynamics for the consensus problem. While most of the research on this topic assume that the underlying graph is complete, we consider the non-complete case, where one technical issue arrises from the fact that the analysis has to keep track of the configurations of the opinions around each vertex at each time-step since the graph is not complete. To manage this, we show how to model the way a vertex decides its colour as a colouring process of a random DAG with a single source and certain levels. Based on that the coupled process where the choices of colour within a certain time-step are pairwise indepen- dent - albeit less of them will in expectation be of the initially dominant colour, we majorise the distribution of the cardinality of the minority colour at a certain time by a binomial distribution. Once the minority colour has diminished enough, the colouring process is then analysed by dividing the DAG into two subgraphs. We then argue and show that after some additional time-steps with high probability any vertex is of initially dominant colour. Next, we analyse the Diversification protocol for generating a weighted partition of a population protocol with random scheduling and random transition. Over the years, population protocols with the goal of reaching consensus have been studied in great depth. However, many systems in the real-world do not result in all agents eventually reaching consensus, but rather in the opposite: they converge to a state of rich diversity. We study an interesting twist on the majority consensus population protocols that have received extensive attention ...
