Lower Bounds for Distinct Elements in the Message Passing Model

David Woodruff and Qin Zhang

This interview introduces the results of two papers, one published at SODA 2014, one at DISC 2013.

——– SODA 2014 ————
Title: An Optimal Lower Bound for Distinct Elements in the Message Passing Model

Abstract: In the message-passing model of communication, there are k players each with their own private input, who try to compute or approximate a function of their inputs by sending messages to one another over private channels. We consider the setting in which each player holds a subset S_i of elements of a universe of size n, and their goal is to output a (1+\eps)-approximation to the total number of distinct elements in the union of the sets S_i with constant probability, which can be amplified by independent repetition. This problem has applications in data mining, sensor networks, and network monitoring. We resolve the communication complexity of this problem up to a constant factor, for all settings of n, k and \eps, by showing a lower bound of \Omega(k \cdot \min(n, 1/\eps^2) + k \log n) bits. This improves upon previous results, which either had non-trivial restrictions on the relationships between the values of n, k and \eps, or were suboptimal by logarithmic factors, or both.

———- DISC 2013 —————–
Title: When Distributed Computation is Communication Expensive

Abstract: We consider a number of fundamental statistical and graph problems in the message-passing model, where we have k machines (sites), each holding a piece of data, and the machines want to jointly solve a problem defined on the union of the k data sets. The communication is point-to-point, and the goal is to minimize the total communication among the k machines. This model captures all point-to-point distributed computational models with respect to minimizing communication costs. Our analysis shows that exact computation of many statistical and graph problems in this distributed setting requires a prohibitively large amount of communication, and often one cannot improve upon the communication of the simple protocol in which all machines send their data to a centralized server. Thus, in order to obtain protocols that are communication-efficient, one has to allow approximation, or investigate the distribution or layout of the data sets.
Guest: Qin Zhang
Host: Yvonne-Anne Pignolet

Conflict Resolution and Membership Problem in Beeping Channels

Bojun Huang and Thomas Moscibroda

Abstract: Consider a group of nodes connected through multiple-access channels and the only observable feedback on the channel is a binary value: either one or more nodes have transmitted (busy), or no node has transmitted (idle). The channel model thus described is called Beeping Model and captures computation in hardware using a group of sequential circuit modules connected by a logic-OR gate. It has also been used to study chemical signaling mechanisms between biological cells and carrier-sensing based wireless communication. In this paper, we study the distributed complexity of two fundamental problems in the Beeping Model. In both problems, there is a set of nodes each with a unique identifier i ∈ {1,2,…,n}. A subset of the nodes A ⊆ {1,2,…,n} is called active nodes. In the Membership Problem, every node needs to find out the identifiers of all active nodes. In the Conflict Resolution Problem, the goal is to let every active node use the channel alone (without collision) at least once. We derive two results that characterize the distributed complexity of these problems. First, we prove that in the Beeping Model the two above problems are equally hard. This is in stark contrast to traditional channel models with ternary feedback in which the membership problem is strictly harder than conflict resolution. The equivalence result also leads to a randomized lower bound for conflict resolution, which shows a relative powerlessness of randomization in the beeping model. Secondly, we give a new deterministic algorithm for the problems that achieves the best known parallelization among all practical algorithms.

Guest: Bojun Huang
Host Prof. Zvi Lotker