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.
This paper considers a probabilistic local polling process, examines its properties, and proposes its use in the context of distributed network protocols for achieving consensus. The resulting consensus algorithm is very simple and lightweight, yet it enjoys some desirable properties, such as proportionate agreement (namely, reaching a consensus value of one with probability proportional to the number of ones in the inputs), resilience against dynamic link failures and recoveries, and (weak) self-stabilization. The paper also investigates the maximum influence of small sets and establishes results analogous to those obtained for the problem in the deterministic polling model. 2001 Elsevier Science In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues a random walk through the graph. Let @math be an undirected and connected graph with @math vertices and @math edges. The coalescence time, @math , is the expected time for all particles to coalesce, when initially one particle is located at each vertex. We study the problem of bounding the coalescence time for general connected graphs and prove that @math . Here @math is the second eigenvalue of the transition matrix of the random walk. To avoid problems arising from, e.g., lack of coalescence on bipartite graphs, we assume the random walk can be made lazy if required. The value of @math is given by @math , where @math is the degree of vertex @math , and @math is the average degree. The parame...