The power of two choices in distributed voting

Colin Cooper, Robert Elsässer, and Tomasz Radzik

Abstract: Distributed voting is a fundamental topic in distributed computing. In pull voting, in 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. On many graph classes including regular graphs, pull voting requires Θ(n) expected steps to complete, even if initially there are only two distinct opinions.
In this paper we consider a related process which we call two-sample voting: every vertex chooses two random neighbours in each step. If the opinions of these neighbours coincide, then the vertex revises its opinion according to the chosen sample. Otherwise, it keeps its own opinion. We consider the performance of this process in the case where two di?erent opinions reside on vertices of some (arbitrary) sets A and B, respectively. Here, |A|+|B|=n is the number of vertices of the graph.
We show that there is a constant K such that if the initial imbalance between the two opinions is of a certain value then with high probability two sample voting completes in a random d regular graph in O(logn) steps and the initial majority opinion wins. We also show the same performance for any regular graph, for some bounds of the second largest eigenvalue of the transition matrix. In the graphs we consider, standard pull voting requires Ω(n) steps, and the minority can still win with probability |B|/n.

Guest: Robert Elsässes, Universität Salzburg,
Host: Yvonne-Anne Pignolet

A Super-Fast Distributed Algorithm for Bipartite Metric Facility Location

James Hegeman and Sriram Pemmaraju

Abstract:  The facility location problem consists of a set of facilities F, a set of clients C, an opening cost f_i associated with each facility x_i, and a connection cost D(x_i,y_j) between each facility x_i and client y_j. The goal is to find a subset of facilities to open, and to connect each client to an open facility, so as to minimize the total facility opening costs plus connection costs. This paper presents the first expected-sub-logarithmic-round distributed O(1)-approximation algorithm in the CONGEST model for the metric facility location problem on the complete bipartite network with parts F and C. Our algorithm has an expected running time of O((log log n)^3) rounds, where n = |F| + |C|. This result can be viewed as a continuation of our recent work (ICALP 2012) in which we presented the first sub-logarithmic-round distributed O(1)-approximation algorithm for metric facility location on a clique network. The bipartite setting presents several new challenges not present in the problem on a clique network. We present two new techniques to overcome these challenges. (i) In order to deal with the problem of not being able to choose appropriate probabilities (due to lack of adequate knowledge), we design an algorithm that performs a random walk over a probability space and analyze the progress our algorithm makes as the random walk proceeds. (ii) In order to deal with a problem of quickly disseminating a collection of messages, possibly containing many duplicates, over the bipartite network, we design a probabilistic hashing scheme that delivers all of the messages in expected-O(log log n) rounds.

Guest: James Hegeman
Host: Yvonne-Anne Pignolet

New Challenges and Algebraic Topology

Maurice Herlihy

Maurice Herlihy discusses his view on the challenges distributed computing faces in the future, describes some of his work on programming abstractions and how he uses algebraic topology as a tool to reason about distributed protocols.

Guest: Maurice Herlihy
Host: Zvi Lotker and Yvonne-Anne Pignolet

Performing Dynamically Injected Tasks on Processes Prone to Crashes and Restarts

Chryssis Georgiou and Dariusz Kowalski

Abstract: To identify the tradeoffs between efficiency  and fault-tolerance in dynamic cooperative computing, we initiate the study of a task performing problem under dynamic processes’ crashes/restarts and task injections. The system consists of $n$ message-passing processes which, subject to dynamic crashes and restarts, cooperate in performing independent tasks that are continuously and dynamically injected to the system. The task specifications are not known a priori to the processes. This problem abstracts todays Internet-based computations, such as Grid computing and cloud services, where tasks are generated dynamically and different tasks may be known to different processes. We measure performance in terms of the number of pending tasks, and as such it can be directly compared with the optimum number obtained under the same crash-restart-injection pattern by the best off-line algorithm. We propose several deterministic algorithmic solutions to the considered problem under different information models and correctness criteria, and we argue that their performance is close to the best possible offline solutions.

Guest: Chryssis Georgiou
Host: Yvonne-Anne Pignolet

Optimal Random Sampling from Distributed Streams Revisited

Srikanta Tirthapura and David Woodruff

Abstract: We give an improved algorithm for drawing a random sample from a large data stream when the input elements are distributed across multiple sites which communicate via a central coordinator. At any point in time the set of elements held by the coordinator represent a uniform random sample from the set of all the elements observed so far. When compared with prior work, our algorithms asymptotically improve the total number of messages sent in the system as well as the computation required of the coordinator. We also present a matching lower bound, showing that our protocol sends the optimal number of messages up to a constant factor with large probability. As a byproduct, we obtain an improved algorithm for finding the heavy hitters across multiple distributed sites.

Guest: Srikanta Tirthapura
Host: Yvonne-Anne Pignolet

Leakage-Resilient Coin Tossing

Elette Boyle, Shafi Goldwasser and Yael Tauman Kalai

Abstract: The ability to collectively toss a common coin among n parties in the presence of faults is an important primitive in the arsenal of randomized distributed protocols. In the case of dishonest majority, it was shown to be impossible to achieve less than 1/r bias in O(r) rounds (Cleve STOC ’86). In the case of honest majority, in contrast, unconditionally secure O(1)-round protocols for generating common unbiased coins follow from general completeness theorems on multi-party secure protocols in the secure channels model (e.g., BGW, CCD STOC ’88).
However, in the protocols with honest majority, parties must generate and hold local secret values which are assumed to be perfectly hidden from malicious parties: an assumption which is crucial to proving the resulting common coin is unbiased. This assumption unfortunately does not seem to hold in practice, as attackers can launch side-channel attacks on the local state of honest parties and leak information on their secrets.
In this work, we present an O(1)-round protocol for collectively generating an unbiased common coin, in the presence of leakage on the local state of the honest parties. We tolerate t ≤ ( 1/3 − ϵ)n computationally-unbounded Byzantine faults and in addition a Ω(1)-fraction leakage on each (honest) party’s secret state. Our results hold in the memory leakage model (of Akavia, Goldwasser, Vaikuntanathan ’08) adapted to the distributed setting.
Additional contributions of our work are the tools we introduce to achieve the collective coin toss: a procedure for disjoint committee election, and leakage-resilient verifiable secret sharing.

Guest: Elette Boyle
Host: Yvonne-Anne Pignolet