In the voter model, each node of a graph has an opinion, and in every round each node chooses independently a random neighbour and adopts its opinion. We are interested in the consensus time, which is the first point in time where all nodes have the same opinion. We consider dynamic graphs in which the edges are rewired in every round (by an adversary) giving rise to the graph sequence @math , where we assume that @math has conductance at least @math . We assume that the degrees of nodes don't change over time as one can show that the consensus time can become super-exponential otherwise. In the case of a sequence of @math -regular graphs, we obtain asymptotically tight results. Even for some static graphs, such as the cycle, our results improve the state of the art. Here we show that the expected number of rounds until all nodes have the same opinion is bounded by @math , for any graph with @math edges, conductance @math , and degrees at least @math . In addition, we consider a biased dynamic voter model, where each opinion @math is associated with a probability @math , and when a node chooses a neighbour with that opinion, it adopts opinion @math with probability @math (otherwise the node keeps its current opinion). We show for any regular dynamic graph, that if there is an @math difference between the highest and second highest opinion probabilities, and at least @math nodes have initially the opinion with the highest probability, then all nodes adopt w.h.p. that opinion. We obtain a bound on the convergences time, which becomes @math for static graphs.
The standard voter model was first analysed in @cite_9 . The authors of @cite_9 bound the expected coalescing time (and thus the expected consensus time) in terms of the expected meeting time @math of two random walks and show a bound of @math . Note that the meeting time is an obvious lower bound on the coalescing time, and thus a lower bound on the consensus time when all nodes have distinct opinions initially. The authors of @cite_8 provide an improved upper bound of @math on the expected coalescing time for any graph @math , where @math is the second eigenvalue of the transition matrix of a random walk on @math , and @math is the ratio of the square of the sum of node degrees over the sum of the squared degrees. The value of @math ranges from @math , for the star graph, to @math , for regular graphs.
@cite_9 @cite_8
1971118040 2237112965 2591036807 2090454980
A voter sits on each vertex of an infinite tree of degree @math , and has to decide between two alternative opinions. At each time step, each voter switches to the opinion of the majority of her neighbors. We analyze this majority process when opinions are initialized to independent and identically distributed random variables. In particular, we bound the threshold value of the initial bias such that the process converges to consensus. In order to prove an upper bound, we characterize the process of a single node in the large @math -limit. This approach is inspired by the theory of mean field spin-glass and can potentially be generalized to a wider class of models. We also derive a lower bound that is nontrivial for small, odd values of @math . Distributed voting is a fundamental topic in distributed computing. In the standard model of pull voting, at each step every vertex chooses a neighbour uniformly at random and adopts its opinion. The voting is completed when all vertices hold the same opinion. In the simplest case, each vertex initially holds one of two different opinions. This partitions the vertices into arbitrary sets A and B. For many graphs, including regular graphs and irrespective of their expansion properties, if both A and B are sufficiently large sets, then pull voting requires @math expected steps, where n is the number of vertices of the graph. In this paper we consider a related class of voting processes based on sampling two opinions. In the simplest case, every vertex v chooses two random neighbours at each step. If both these neighbours have the same opinion, then v adopts this opinion. Otherwise, v keeps its own opinion. Let G be a connected graph with n vertices and m edges. Let P be the transition matrix of a simple random walk on G with second largest eigenvalue @math . We show that if the initial imbalance in degree between the two opinions satisfies @math , then with high probability voting completes in @math steps, and the opinion with the larger initial degree wins. The condition that @math , or only a bound on the conductance of the graph is known, the sampling process can be modified so that voting still provably completes in @math steps with high probability. The modification uses two sampling based on probing to a fixed depth @math from any vertex. In its most general form our voting process allows vertices to bias their sampling of opinions among their neighbours to achieve a desired outcome. This is done by allocating weights to edges. We consider distributed plurality consensus in a complete graph of size @math with @math initial opinions. We design an efficient and simple protocol in the asynchronous communication model that ensures that all nodes eventually agree on the initially most frequent opinion. In this model, each node is equipped with a random Poisson clock with parameter @math . Whenever a node's clock ticks, it samples some neighbors, uniformly at random and with replacement, and adjusts its opinion according to the sample. A prominent example is the so-called two-choices algorithm in the synchronous model, where in each round, every node chooses two neighbors uniformly at random, and if the two sampled opinions coincide, then that opinion is adopted. This protocol is very efficient and well-studied when @math . If @math for some small @math , we show that it converges to the initial plurality opinion within @math rounds, w.h.p., as long as the initial difference between the largest and second largest opinion is @math . On the other side, we show that there are cases in which @math rounds are needed, w.h.p. One can beat this lower bound in the synchronous model by combining the two-choices protocol with randomized broadcasting. Our main contribution is a non-trivial adaptation of this approach to the asynchronous model. If the support of the most frequent opinion is at least @math times that of the second-most frequent one and @math , then our protocol achieves the best possible run time of @math , w.h.p. We relax full synchronicity by allowing @math nodes to be poorly synchronized, and the well synchronized nodes are only required to be within a certain time difference from one another. We enforce this synchronicity by introducing a novel gadget into the protocol. In a coalescing random walk, a set of particles make independent random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues the random walk through the graph. Coalescing random walks can be used to achieve consensus in distributed networks, and is the basis of the self-stabilizing mutual exclusion algorithm of Israeli and Jalfon. Let G=(V,E), be an undirected, connected n vertex graph with m edges. Let C(n) be the expected time for all particles to coalesce, when initially one particle is located at each vertex of an n vertex graph. We study the problem of bounding the coalescence time C(n) for general classes of graphs. Our main result is that C(n)= O(1 (1-lambda_2))*((log n)^4 +n A)), where lambda_2 is the absolute value of the second largest eigenvalue of the transition matrix of the random walk, A= (sum d^2(v)) (d^2 n), d(v) is the degree of vertex v, and d is the average node degree. The parameter A is an indicator of the variability of node degrees. Thus 1 <= A =O(n), with A=1 for regular graphs.