Distributed Voting in Large Networks

The main focus of the project is to design efficient distributed voting algorithms for large networks. Initially, we are given a graph and some opinions assigned to its nodes. Most of the work in the literature is devoted to the traditional single-sample voting model, in which each node of the graph consults - in synchronous rounds a neighbor chosen uniformly at random, and adopts the opinion of this node. We concentrate in this project on the so-called two-sample voting, where the nodes choose two neighbors uniformly at random, and adopt the opinion of these two nodes if they coincide. This protocol turns out to complete much faster than the traditional (well- analyzed) model in graphs with very good expansion properties. Our goals are three-fold: In regular graphs, we will analyze two-sample voting in the case, where each node is assigned one of two distinct opinions at the beginning. First, we consider graphs with a second largest eigenvalue of the transition matrix of a corresponding random walk bounded away from 1. A first analysis shows that the voting process converges in time O(log n) for < 3/5, as long as the initial imbalance between the two opinions is O(1). In order to cope with graphs having a second largest eigenvalue beyond 3/5, we will analyze the relationship between the eigenvalue mentioned above and the convergence time of the two-party two-sample voting model. Then, we are going to extend our results to k-party voting (i.e., initially there are k different opinions in the system) for any constant k. Motivated by previous results on the structure of real-world networks, we will study our algorithms in non- regular graphs with power law degree distribution. To analyze the performance of our protocols, we have to take into account the dynamics of the process, which may depend on the degree distribution of the neighborhood of an arbitrary but fixed node. We think that two-party two-sample voting still has a (poly- )logarithmic runtime, with high probability, as long as the graph structure possesses enough randomness. Concerning k-party two-sample voting this running time might not hold anymore, if the initial imbalance is only moderately biased toward one opinion. We will analyze these cases analytically as well as empirically. Finally, we will analyze distributed voting on general graphs. Our goal is to obtain a (tight) relationship between the expansion properties and degree distributions on one side, and the convergence time of c-sample voting on the other side, where c can be any constant. First, we are going to analyze two-party voting, and then extend our results to k-party voting for any k independent of n. We think that these results will provide new insight into the relationship between the structure of a graph and its algorithmic properties.

The main focus of the project was to design efficient distributed voting algorithms for large networks. Initially, we are given a graph and some opinions assigned to its nodes. Before the beginning of the project, most of the work in the literature was devoted to the traditional single-sample voting model, in which each node of the graph consults - in synchronous rounds - a neighbor chosen uniformly at random, and adopts the opinion of this node. We concentrated in this project on the so-called two-sample voting, where the nodes choose two neighbors uniformly at random, and adopt the opinion of these two nodes if they coincide. This protocol turns out to complete much faster than the traditional (well-analyzed) model in graphs with very good expansion properties. In this project we achieved the following results: - we showed that simple modifications of the two-sample voting can reach consensus within (poly-)logarithmic time in all graphs with good expansion properties, including non-regular graphs - we analyzed the case when the number of opinions grows with the number of nodes in the network. We presented lower and upper bounds for this scenario, and derived new algorithms, which are able to efficiently solve consensus in complete graphs. Adopting the modifications described above, these algorithms can be generalized to arbitrary (regular) graphs at the cost of an additional factor of the mixing time of the graph - we analyzed voting processes in the asynchronous setting, in which nodes possess a random clock, and they are activated when the clock ticks. We have shown that if the clocks have the so called positive aging property and there is a sufficient gap between the largest and second largest opinion, then voting terminates fast, even for n^{1/2-\epsilon} many initial opinions (\epsilon > 0 can be any small constant).