In this paper, we consider lightweight decentralised algorithms for achieving consensus in distributed systems. Each member of a distributed group has a private value from a fixed set consisting of, say, two elements, and the goal is for all members to reach consensus on the majority value. We explore variants of the voter model applied to this problem. In the voter model, each node polls a randomly chosen group member and adopts its value. The process is repeated until consensus is reached. We generalize this so that each member polls a (deterministic or random) number of other group members and changes opinion only if a suitably defined super-majority has a different opinion. We show that this modification greatly speeds up the convergence of the algorithm, as well as substantially reducing the probability of it reaching consensus on the incorrect value.
Consensus can also be reached without using variants of voter models. Instead, agents could simply count the number of agents with values 0 and 1, and thereby choose the majority. It is shown in @cite_4 that such counting problems can be approximated using a gossip algorithm which involves propagating real numbers rather than values from a finite set. If the approximation error in counting is smaller than the margin between the 0 and 1 votes, then this leads to the correct decision regarding the initial majority value. The time required by this approximate counting algorithm is shown in @cite_4 to scale logarithmically in the number of nodes in complete graphs, whereas on general graphs, it can be bounded in terms of the expansion properties of the graph.
@cite_4
2078381259
We consider the problem of estimating the value of max cut in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allows O(n) space, then a near-optimal solution to the max cut value can be obtained by storing an O(n)-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor 2). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space. Our main result is that any streaming algorithm that breaks the 2-approximation barrier requires [EQUATION] space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or 1 2-far from being bipartite, and establishing that [EQUATION] space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that [EQUATION] space is also necessary to test if a graph is bipartite or 1 2-far from being bipartite. We also show that for any e > 0, any streaming algorithm that obtains a (1 + e)-approximation to the max cut value when edges arrive in adversarial order requires n1O(e) space, implying that (n) space is necessary to obtain an arbitrarily good approximation to the max cut value.