## Distributed Data Summarization in Well-Connected Networks

Hsin-Hao Su Boston College suhx@bc.edu

Hoa T. Vu Boston College vuhd@bc.edu

## Abstract

We study distributed algorithms for some fundamental problems in data summarization. Given a communication graph G of n nodes each of which may hold a value initially, we focus on computing ∑ N i =1 g f ( i ), where f i is the number of occurrences of value i and g is some fixed function. This includes important statistics such as the number of distinct elements, frequency moments, and the empirical entropy of the data.

In the CONGEST model, a simple adaptation from streaming lower bounds shows that it requires Ω( ˜ D + n ) rounds, where D is the diameter of the graph, to compute some of these statistics exactly. However, these lower bounds do not hold for graphs that are well-connected. We give an algorithm that computes ∑ N i =1 g f ( i ) exactly in τ G · 2 O ( √ log n ) rounds where τ G is the mixing time of G . This also has applications in computing the top k most frequent elements.

We demonstrate that there is a high similarity between the GOSSIP model and the CONGEST model in well-connected graphs. In particular, we show that each round of the GOSSIP model can be simulated almost perfectly in ˜ ( O τ G ) rounds of the CONGEST model. To this end, we develop a new algorithm for the GOSSIP model that 1 ± glyph[epsilon1] approximates the p -th frequency moment F p = ∑ N i =1 f p i in ˜ ( O glyph[epsilon1] -2 n 1 -k/p ) rounds 1 , for p ≥ 2, when the number of distinct elements F 0 is at most O n ( 1 / k ( -1) ) . This result can be translated back to the CONGEST model with a factor ˜ ( O τ G ) blow-up in the number of rounds.

1 ˜ omits polylog( O n ) factors.

## 1 Introduction

Motivation : Analyzing massive datasets has become an increasingly important and challenging problem. Collecting the entire data to one single machine is usually infeasible due to memory, I/O, or network bandwidth constraints. Furthermore, in many cases, data are distributed over the network and we hope to aggregate some of their properties efficiently. In this work, we consider several fundamental data summarization problems in distributed networks, specifically in the CONGEST and GOSSIP models.

In this problem, we have a graph G = ( V, E ) of n nodes. Each node v in the graph may hold a value val ( v ) in the range { 1 , . . . , N } ∪ { NULL } where NULL simply means that the node does not hold a value. If val ( v ) = NULL, we call v an empty node .

We often use the notation [ N ] := { 1 , . . . , N } . Let f i be the number of nodes that hold value i , i.e., f i = |{ v ∈ V : val ( v ) = i }| . We want to compute ∑ N i =1 g f ( i ) for some fixed function g . To demonstrate some important cases, consider the following examples.

Consider g f ( i ) = 1 if f i &gt; 0 and 0 otherwise. This corresponds to the problem of counting the number of distinct elements (or computing the 0-th frequency moment F 0 ). The problem may arise in the following situation: Each node stores a version of a file (e.g. the hash of a blockchain), and we want to know how many different versions there are in the network.

If g f ( i ) = f p i for some fixed p = 2 3 , , . . . , then this corresponds to the problem of computing the p -th frequency moment F p . We note that F p is a basic, yet very important statistic of a dataset. F 2 measures the variance and could be used to estimate the size of a self-join in database applications. For higher p , F p measures the skewness of the dataset (see [AMS99]). Note that F 1 can be computed in O D ( ) rounds by aggregating along a breath-first-search (BFS) tree.

Another example is g f ( i ) = -( f /F i 1 ) · log( f /F i 1 ). In this case, the sum is the empirical entropy of the data. Computing the empirical entropy is motivated by network applications such as detecting anomalies [GMT05,XZB05,WP05].

Models : We now give a formal description of the CONGEST and GOSSIP models, where the running time of an algorithm is measured by the number of rounds.

Definition 1.1. In the CONGEST model, we are given a graph G = ( V, E ) of n nodes, in each synchronous round, each node can talk (send and receive message) to each of its neighbors and then perform local computations. Each message is restricted to be at most O (log n ) bits.

Definition 1.2. In the GOSSIP ( λ ) model with n nodes, in each synchronous round, each node u samples a node t ( u ) from a distribution that satisfies the following: For any node v and any subset of nodes Z where u / Z ∈ ,

$$\Pr \left ( t ( u ) = v \Big | \bigwedge _ { z \in Z } t ( z ) \right ) \in \left [ \frac { 1 - \lambda } { n }, \frac { 1 + \lambda } { n } \right ].$$

In the above, ' ∧ z ∈ Z t ( z )' means conditioning on any assignment of each t ( z ) for z ∈ Z . Then, u can PUSH a message of size O (log n ) to t ( u ) or PULL a message of size O (log n ) from t ( u ). Then, after performing some local computations, it proceeds to the next round. We refer GOSSIP model as the GOSSIP (0) model.

## 1.1 Our results

We organize our main results into three categories: a) results in the CONGEST model, b) an emulation of the GOSSIP model in the CONGEST model, and c) results in the GOSSIP model.

Results in the CONGEST model : We briefly show how to adapt streaming algorithms to approximate F p (for p = 0 2 3 , , , . . . ) in the CONGEST model. We also demonstrate some lower bounds and conditional lower bounds that give evidence that such algorithms are optimal or near-optimal.

The lower bounds show that computing F p exactly for p = 0 2 3 , , , . . . requires Ω( ˜ D + n ) rounds and approximating F p within a constant factor requires polynomial rounds in n for p ≥ 3. Roughly speaking, the hard instances in the CONGEST model are graphs with a small balanced cut of O (1) size that causes an information bottleneck. However, such bottleneck does not occur in graphs that are well-connected. Our first main result aims to answer the following question: Could one design more efficient algorithms for well-connected graphs? We give a positive answer to this question.

By using the permutation routing algorithms of Ghaffari et al. [GKS17] (later improved by Ghaffari and Li [GL18]), we show that there exists an algorithm running in τ G · 2 O ( √ log n ) rounds that computes ∑ N i =1 g f ( i ) for all fixed and computable functions g with high probability (w.h.p.) 2 . This includes all the aforementioned quantities such as the number of distinct elements, higher frequency moments, and the empirical entropy. Thus, if the graph has small mixing time such as expanders [Gol11,HLW06], where τ G = polylog( n ), then we obtain a much more efficient sub-polynomial in n algorithm compared to the adaptation of the streaming counterpart.

Theorem 1.1 ( Main result 1) . There exists an algorithm that computes ∑ N i =1 g f ( i ) exactly for all (fixed and computable) functions g in the CONGEST model in τ G · 2 O ( √ log n ) rounds w.h.p.

Our algorithm can also easily be extended to find the top k frequent elements in O k ( ) + τ G · 2 O ( √ log n ) rounds.

From CONGEST to GOSSIP : The lower bounds do not apply directly to the GOSSIP model either. This is because for any balanced cut of the nodes, one expects O n ( ) messages to be sent across in one round. Moreover, the expected communication degree per node in the GOSSIP model is O (1). Intuitively, the graph formed by the communication pattern in the GOSSIP model is similar to an expander graph.

In fact, we show that well-connected graphs can emulate the GOSSIP model efficiently. In particular, one round of the GOSSIP (1 / poly( n )) model can be emulated in τ G · polylog( n ) rounds in the CONGEST model where the underlying graph is G . Therefore, any algorithm that works in the GOSSIP (1 / poly( n )) model can be turned into an algorithm in the CONGEST model with an ˜ ( O τ G ) factor blow-up.

Consider our results in the CONGEST model. The permutation routing algorithms of [GKS17] and [GL18] introduces a super-logarithmic factor, 2 O ( √ log n ) , on top of the mixing time. It becomes the bottleneck in graphs with small mixing times (e.g., expanders). Improving the permutation routing algorithm directly yields improvements to our results in the CONGEST model (and many other problems). However, it is unclear if it can be

2 We consider 1 -1 / poly( n ) as high probability.

Figure 1: Results summary for computing frequency moments F p . (*) can also be used to compute ∑ i g f ( i ) for all fixed and computable functions g .

|         | Number of rounds                                  | Assumption                 | Approximation       |
|---------|---------------------------------------------------|----------------------------|---------------------|
| CONGEST | τ G · 2 O ( √ log n ) (*)                         |                            | Exact               |
| CONGEST | O ( glyph[epsilon1] - 2 τ G · polylog n )         | F 0 ≤ O ( n 1 / ( p - 1) ) | 1 ± glyph[epsilon1] |
| GOSSIP  | O ( glyph[epsilon1] - 2 · n 1 - k/p · polylog n ) | F 0 ≤ O ( n 1 / ( k - 1) ) | 1 ± glyph[epsilon1] |

improved. This emulation result serves as an alternative route to circumvent the 2 O ( √ log n ) factor, if one develops efficient GOSSIP algorithms.

Theorem 1.2 ( Main result 2) . For λ = 1 / poly( n ) , one round of the GOSSIP ( λ ) model can be emulated in ˜ ( O τ G ) rounds in the CONGEST model where G is a connected graph denoting the underlying network.

We believe that this emulation result may be of independent interest. Jelasity et al. [JVG + 07] studied how to implement the gossip-based peer sampling service empirically. Our result is an additional way to implement the service with theoretical guarantees.

Results in the GOSSIP model : Motivated by our emulation result, we develop algorithms for the GOSSIP model. In particular, we are interested in the following question: Suppose the number of non-empty nodes are sublinear in n . Could we take advantage of the computational power of the empty nodes?

Suppose that the number of non-empty nodes is at most O n ( 1 / k ( -1) ) (or more generally, F 0 ≤ O n ( 1 / k ( -1) )). We show that for any p ≥ 2, F p can be approximated within a 1 ± glyph[epsilon1] factor in O glyph[epsilon1] ( -2 n 1 -k/p log 2 n ) rounds with high probability.

Theorem 1.3 ( Main result 3) . If F 0 = O n ( 1 / k ( -1) ) for some integer 2 ≤ k ≤ p , then there exists an algorithm that approximates F p up to a 1 ± glyph[epsilon1] factor in O glyph[epsilon1] ( -2 n 1 -k/p log 2 n ) rounds in the GOSSIP (1 /n c ) model, for some sufficiently large constant c , w.h.p.

The GOSSIP (1 /n c ) model will incur a ± 1 / poly( n ) additive error which we consider insignificant. Since F 0 ≤ n , we have an algorithm that approximates F 2 in ˜ ( O glyph[epsilon1] -2 ) rounds by setting k = 2. When k &gt; 2, the empty nodes serve as the extra computation power to solve the problem. In such scenarios, we are able to obtain running time that is not known to be achievable by adapting the streaming counterpart. For example, when k = 3, F 0 = O n ( 1 / 2 ), we may approximate F 3 within a constant factor in polylog( n ) rounds. Direct adaption of known streaming algorithms [AKO11,MW10,AMS99] requires super-logarithmic rounds, even in the case where F 0 = O n ( 1 / 2 ).

Combining Theorem 1.3 and Theorem 1.2 with k = p , we have the following corollary.

Corollary 1.4. If F 0 = O n ( 1 / p ( -1) ) , then there exists an algorithm in the CONGEST model that approximates F p up to a 1 ± glyph[epsilon1] factor in ˜ ( O glyph[epsilon1] -2 · τ G ) rounds w.h.p.

## 1.2 Related work and preliminaries

Related work : In the distributed setting, Kuhn et al. [KLS08] studied the problem of finding the mode, i.e., the most frequent element, in the CONGEST model. Let D is the

diameter of the graph, and f ∗ is the largest number of occurrences among the values. They gave an algorithm that uses O D ( + F /f 2 ∗ · log k ) rounds. They also briefly explained how to implement streaming algorithms for approximating F 0 and F 2 in the CONGEST models. Also related to data summarization, Kuhn et al. [KLW07] designed selection algorithms in the CONGEST model.

In the data stream model, each stream token ( i, x ) corresponds to the update f i ← f i + . x The problem of approximating the number of distinct elements F 0 and frequency moments F p have been extensively studied. An incomplete list includes [BJK + 02, GT01, KNW10, AMS99,IW05,Ind06,AKO11,Woo04,Gan15]. Roughly speaking, the space complexity for approximating F p in the data stream model is ˜ ( O glyph[epsilon1] -2 ) for 0 ≤ p ≤ 2 and ˜ ( O glyph[epsilon1] -2 n 1 -2 /p ) for p ≥ 2. Furthermore, it is known that approximating F ∞ (or identifying the mode) is not possible in sublinear space. In the data stream model, researchers have also studied the problem of approximating the entropy [HNO08,CBM06,CCM10].

We will briefly discuss the similarities between the data stream model and the CONGEST model. Roughly speaking, since streaming algorithms use little memory, they can be adapted to the CONGEST model by passing the memory state of the corresponding algorithm along the breadth-first-search tree. Similarly, lower bounds from streaming algorithms literature can also be translated into lower bounds in the CONGEST model. Data aggregation problems have also been studied in directed networks [KO11].

There is also a rich literature in the GOSSIP model started by the work of [DGH + 87]. Some examples include spreading message [FG85,Pit87,KSSV00], computing the sum and average [KDG03,CP12,KDN + 06], renaming [GKW13], and quantile computation [HMS18].

Preliminaries : We introduce basic notations and algorithmic building blocks in the CONGEST model.

To ease our presentation, we assume N = O (poly( n )). In our algorithms, we often want to learn about the sum of all the values (or hash values, indicator variables) held by the nodes; this can be done in O D ( ) rounds. Another algorithmic primitive, based on downcasts and upcasts, is to broadcast the k smallest values in O D ( + ) rounds. k

We define the mixing time similarly to [GKS17]. A lazy random walk is a random walk in which at each step, we stay at the same node with probability 0.5 and move to a random neighbor with probability 0.5. Lazy random walk ensures the existence of a unique stationary distribution (i.e., the walk is aperiodic). From now on, we simply refer to a lazy random walk as a random walk.

Let P t u = ( P t u ( v 1 ) , . . . , P t u ( v n )) ∈ [0 , 1] n denotes the probability distribution on the nodes after t steps of a lazy random walk that starts at u . A crucial property of a random walk is that it will converge to the stationary distribution (deg( v 1 ) / 2 m,... , deg( v n ) / 2 m ). Define the mixing time τ G to be the minimum t such that for any starting node u and any node v i ,

$$\left | P _ { u } ^ { t } ( v _ { i } ) - \frac { \deg ( v _ { i } ) } { 2 m } \right | \leq \frac { \deg ( v _ { i } ) } { 2 m n } \.$$

Using an O D ( )-round pre-proscessing, we can assume that each node has a unique ID in [ n ]. Suppose we want the nodes in a graph to have unique IDs in [ n ]. We can elect a leader and build a breadth-first-search (BFS) tree that is rooted at the leader in O D ( ) rounds [Pel00]. Each node u can learn about the number of nodes in T v where v is a child of u and T v is the subtree that is rooted at v . This is done by aggregating the size from the leaves upward. It is then straightforward to assign the IDs to the nodes based on the depth-first-search (DFS) ordering. Specifically, the root notifies each of its children v the

range of the IDs in T v , based on the DFS ordering, and then recurse on T v . From now on, we can refer to the nodes by their IDs, i.e., ID( v ) = v .

We will also make use of hash functions. An O (1)-wise independent hash function h : [ a ] → [ b ] where a and b are at most poly( n ) can be stored in O (log n ) bits. Hence, if we need to use a hash function, a leader can broadcast such hash function (using a BFS tree) in O D ( +log n ) rounds in the CONGEST model and O (log n ) rounds in the GOSSIP model.

## 2 Algorithms in the CONGEST Model

## 2.1 Approximation algorithms

Upper bounds : We show that we can adapt the streaming algorithms given by Bar-Yossef et al. [BJK + 02] (for approximating F 0 ) and by Alon et al. [AMS99] (for approximating F p , where p ≥ 2) to the CONGEST model (see Appendix A). This is not of particular novelty though we need some careful pipelining arguments to optimize the number of rounds. Kuhn et al. [KLS08] also briefly outlined similar results. However, the exact round-complexity for a good approximation w.h.p. is not very clear from their paper.

Theorem 2.1. There exists an O D ( + glyph[epsilon1] -2 log n ) -round algorithm in the CONGEST model that computes a 1 ± glyph[epsilon1] approximation of F 0 and F 2 w.h.p. Furthermore, for p &gt; 2 , there exists an O D ( + glyph[epsilon1] -2 min( n, N ) 1 -1 /p log n ) -round algorithm that computes a 1 ± glyph[epsilon1] approximation of F p w.h.p.

Lower bounds : We show that the dependence on glyph[epsilon1] is tight via a conditional lower bound. Moreover, computing F p exactly requires ˜ ( Ω n ) rounds. The lower bounds are obtained by adapting the existing streaming lower bounds to the CONGEST model. Due to space constraint, we refer to Appendix A for the discussion.

Theorem 2.2. We have the following lower bounds in the CONGEST model.

glyph[negationslash]

- · If the conjecture in [BC09] holds, then approximating F p (for fixed p = 1 ) up to a 1 ± glyph[epsilon1] factor requires Ω( D + glyph[epsilon1] -2 / log n ) rounds.
- · A (1 ± 0 1) . -approximation of F p , for p &gt; 2 , requires Ω ( D + ( N 1 -2 p + n 1 -2 /p 1+1 /p ) / log n ) rounds.
- · Computing F p exactly requires Ω( D + n/ log n ) rounds.

Hence, we cannot expect a sublinear algorithms (in terms of N,n ) when glyph[epsilon1] glyph[lessmuch] 1 / √ n or when we want to obtain the exact answer. The lower bounds arise in graphs with a small balanced cut which causes an information bottleneck. This observation motivates us to design an exact algorithm when the graph is well-connected.

## 2.2 An exact algorithm in near mixing-time

In this subsection, we show that it is possible to beat the lower bounds and achieve an exact algorithm in sublinear time if the graph has fast mixing time. For example, expander graphs are sparse and have O (polylog n ) mixing time.

Suppose each node has a set of messages (of size polylog( n )) each of which has a destination that is another node. In parts of our algorithms, we want to route messages in a small

number of rounds. We rely on the following routing algorithm in the CONGEST model that uses τ G · 2 O ( √ log n ) rounds. We note that 2 O ( √ log n ) is more than polylog n but smaller than any n glyph[epsilon1] for glyph[epsilon1] &gt; 0. Also note that D = O τ ( G ). Let deg( v ) be the degree of v in G .

Theorem 2.3 ( [GL18], [GKS17]) . If each node of G is the source and the destination of at most d G ( v ) 2 · O ( √ log n ) messages, then there is a randomized algorithm in the CONGEST model that delivers all the messages in τ G · 2 O ( √ log n ) rounds w.h.p.

We also rely on the idea of sorting networks. Recall that we refer to the nodes by their unique IDs in [ n ]. In a sorting network, in each step r , the sorting network will pick a set of disjoint pairs of nodes. We use val ( x, r ) to denote the value that node x holds in the beginning of step r . For each pair x and y (where x &lt; y ) that is picked, x will keep the smaller value min(val ( x, r ) , val ( y, r )) and y will keep the larger value max(val ( x, r ) , val ( y, r )). We treat NULL as -∞ . The sorting network can be constructed, solely based on n , so that after t = O (log n ) steps, the values are sorted [AKS83]. That is if x &lt; y , then val ( x, t ) ≤ val ( y, t ).

In the CONGEST model, each node can generate the sorting network (note that the construction of the sorting network is independent of the topology of G and the values held by the nodes). Furthermore, each step can be simulated by invoking Theorem 2.3. Thus, we have the following.

Lemma 2.4. In the CONGEST model, we can sort the nodes' values in τ G · 2 O ( √ log n ) rounds w.h.p.

We now complete the proof of our first main result.

glyph[negationslash]

Proof of Theorem 1.1. We now use val ( v ) to refer to the value that v holds after sorting. We say a node v is a head or a tail if val ( v ) = -∞ and its ID is the smallest or the largest respectively among the IDs of the nodes that hold the value val ( v ). A node v can tell that if it is a head or a tail by checking with the nodes v +1 and v -1 respectively using the routing algorithm in Theorem 2.3. We use head ( ) and tail ( ) to denote the IDs of the head i i and the tail of value i respectively.

Now, every node that is not a head or a tail marks its value as -∞ . Each remaining node forms a token consisting of its value, ID, and whether if it is a head or a tail (or both). We then use sorting networks again to sort the values in the graph. We will also swap the tokens if two nodes swap their values. Afterward, the head and the tail tokens of a value i will be at some two nodes v and v +1 (or just at a node v if f i = 1). To this end, each node v that holds a head token (that is not also a tail token) with value i will check with nodes v +1 and v -1, using the routing algorithm, to collect tail ( ) since either i v +1 or v -1 must have the tail token of i . Now, v can compute g f ( i ) = g (tail ( i ) -head( ) + 1) and set i this as its value. All the nodes that do not hold a head token set their values to 0. We then compute ∑ N i =1 g f ( i ) using the BFS tree in O D ( ) rounds.

The algorithm above is more robust compared to the AMS sketch since it can handle all fixed and computable functions g . The AMS sketch cannot guarantee sublinear space in the streaming model (or sublinear time in the CONGEST model) for many functions [BO10,BC15,BCWY16]. The above algorithm also immediately leads to an algorithm that finds the top k frequent elements.

Finding the top k frequent elements : At the end of the above algorithm, the occurrence of each value i is held by some node v . Recall we can find the top k elements in the graph using O D ( + ) rounds via upcasts. This immediately leads to the following result. k

Theorem 2.5. There exists an algorithm that finds the top k elements (along with their occurrences) in the CONGEST model in O k ( + τ G · 2 O ( √ log n ) ) rounds w.h.p.

## 3 Emulation of GOSSIP Model in the CONGEST Model

√

In Section 2, we have shown that the moments can be computed exactly in τ G · 2 O ( log n ) rounds. If the permutation routing algorithm can be improved to polylog( n ) rounds, then the running time of our algorithms would be improved to ˜ ( O τ G ) rounds. Whether the 2 O ( √ log n ) factor can be improved to polylog( n ) is an intriguing open question.

Instead of tackling the complexity of permutation routing, in this section, we show that one round of the GOSSIP model can be emulated almost-perfectly in ˜ ( O τ G ) rounds in the CONGEST model. Therefore, if there is a polylog( n )-round algorithm in the GOSSIP model, it implies a ˜ ( O τ G ) rounds algorithm in the CONGEST model. In Section 4, we present efficient algorithms in the GOSSIP model when F 0 is small (or when the number of empty nodes is large) which can be translated back to the CONGEST model using the emulation result in this section.

Recall that P t u = ( P t u ( v 1 ) , . . . , P t u ( v n )) ∈ [0 , 1] n denotes the probability distribution on the nodes after t steps of a lazy random walk that starts at u (see Section 1.2). Given λ , we let τ G ( λ ) be the smallest t such that for any starting node u and any node v i ,

$$\left | P _ { u } ^ { t } ( v _ { i } ) - \frac { \deg ( v _ { i } ) } { 2 m } \right | \leq \lambda.$$

Note that if λ = 1 / poly( n ) then τ G ( λ ) = O τ ( G ) [GKS17, Definition 2.1].

We will run several random walks in parallel. The following lemma from [GKS17] shows that the parallel random walks can be performed efficiently in the CONGEST model.

Lemma 3.1 ( [GKS17], Lemma 2.5) . Let G = ( V, E ) be an n -node graph and let t ≥ 1 be a positive integer. Assume that we perform T = O (poly( n )) steps of a collection of independent random walks in parallel. If each node u ∈ V is the starting node of at most t · deg( u ) random walks, w.h.p., the T steps of all the random walks can be performed in O (( t +log n ) · T ) rounds in the CONGEST model.

The main technical difficulty of the emulation lies in the fact that the stationary distribution is not necessarily uniform in general graphs. If G is regular, we could let each node u start a random walk that runs for O τ ( G ) steps. The probability that u ends at each node is (nearly) uniform. If it ends at v then we set t ( u ) = v . Moreover, by Lemma 3.1, all the random walks can be performed simultaneously in ˜ ( O τ G ) rounds.

In irregular graphs, such approach does not work because the stationary distribution is not uniform. One remedy is to regularize the random walk (i.e. adding self-loops to nonmaximum degree nodes). However, this may significantly increase the mixing time of the graph (e.g., a star graph). In the following, we give an emulation algorithm whose running time is within a polylog( n ) factor of the mixing time.

For each node u in G , we split it into deg( u ) compartments . When a random walk enters a node, it is assigned randomly to one of its compartments. There are 2 m compartments in G in total. We outline the emulation algorithm below.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00236v2-figure-a74c6b08-e3ca-44b8-8ab1-e3e01a03354c.jpg)

- (a) Illustration of Step 2. The random walk of u 's source token ends in the compartment containing the destination token of v 4 . Thus, t ( u ) = v 4 .

(b) Illustration of Step 3. u , u 1 2 , u 3 will follow the paths taken by the destination tokens of v back to v . The paths may overlap. W.h.p. every edge is contained in at most O (log n ) paths.

Figure 2

- 1. Let k = 1 5 glyph[floorleft] . m/n glyph[floorright] . Each node creates k destination tokens and distributes them over the compartments in G so that each compartment contains at most one destination token. Now n · k ≈ 1 5 . m compartments are filled with tokens.
- 2. Each node sends out a source token . Each source token starts a random walk to distribute itself randomly over the compartments at the end. If the source token of node u ends in a compartment with the destination token of some node v , we set t ( u ) = v .
- 3. Route the message between u and t ( u ) for each u simultaneously.

We explain how to implement each step in details.

Step 1 : Each node u creates a destination token ( u, k ) initially. The first component of the token is its identity while the second component of the token is its multiplicity. The goal is to split the tokens and distribute them across the compartments so that all tokens have multiplicity of 1 and each compartment holds at most one token. We divide Step 1 into the splitting phase and the distributing phase .

The splitting phase is further divided into glyph[ceilingleft] log k glyph[ceilingright] stages. At the beginning of each stage, if W &gt; 1, each token ( u, W ) is split into two tokens ( u, glyph[ceilingleft] W/ 2 ) and ( glyph[ceilingright] u, glyph[floorleft] W/ 2 ). glyph[floorright] Then all tokens perform τ G steps of random walks.

We show that w.h.p., there are at most O (log n ) tokens per compartment at the end of each stage. Given a stage, the probability that a token ends up in a given compartment in node v is at most

$$\left ( \frac { \deg ( v ) } { 2 m } + \frac { 1 } { 2 m n } \right ) \cdot \frac { 1 } { \deg ( v ) } \leq \frac { 1 } { m }.$$

Since there are at most k · n ≤ 1 5 . m tokens, there are at most O (1) tokens ending in a compartment in expectation. By standard Chernoff and union bound argument, w.h.p. there are at most O (log n ) tokens in each compartment.

Moreover, since each node u holds at most deg( u ) · O (log n ) tokens at the beginning of each stage, the random walks can be performed in parallel in O τ ( G · log n ) rounds by Lemma

3.1. Therefore, the splitting phase uses O ((log k ) · ( τ G · (log n ))) = ˜ ( O τ G ) rounds. At the end of the splitting phase, the multiplicity of each token is one. Moreover, w.h.p. each compartment contains at most O (log n ) tokens.

In the distributing phase, a compartment containing more than one token will start the random walks on all except one of its token for τ G (0 1 . / 2 m ) steps. Again, by Lemma 3.1, this can be done simultaneously for all nodes in O τ ( G · log n ) rounds. At the end of the random walks, we say a token succeeds if it ends at a compartment without any other tokens. If a token does not succeed, it will go back to the origin. The process is repeated until there is no compartment containing more than one token. Since there are at most n · k ≤ 1 5 . m tokens, at most 1 5 . m compartment can be occupied. Since we run the random walks for τ G (0 1 . / 2 m ) steps, the probability that a random walk ends at a specific compartment is at most 1 1 . / 2 m . Thus, the probability that a token does not succeed is at most (1 5 . m ) · (1 1 . / (2 m )) = 1 65 . / 2.

Therefore, a token will succeed w.h.p. after at most O (log n ) trials. By a union bound over the tokens, w.h.p. all tokens succeed after O (log n ) trials. The total running time is O (log n · ( τ G log n )) = ˜ ( O τ G ).

Step 2 : Each node u creates a source token. The tokens start to perform random walk for τ G ( λ ′ ) steps, where λ ′ = min( λ/ (8 m , ) 0 1 . /m ) (see Figure 2a). If the source token of u ends up in one out of the k compartments with a destination token of v , t ( u ) will be set to v . Otherwise, if it ends up in a compartment without any destination tokens, it will restart the random walk. The process will be repeated until the source token ends up in a compartment with some destination token.

By our choice of λ ′ , the probability that a token ends at a specific node is at least 0 9 . / (2 m ). Therefore, the probability that a token successfully ends up in a compartment with a destination token after the random walk is at least

$$\ n k \cdot \frac { 0. 9 } { 2 m } \geq ( 1. 5 m - n ) \cdot \frac { 0. 9 } { 2 m } \geq ( 1. 5 m - m - 1 ) \cdot \frac { 0. 9 } { 2 m } \geq \left ( \frac { 1 } { 4 } - \frac { 1 } { 2 m } \right ) \cdot 0. 9 \geq 0. 9 / 8 \.$$

The second inequality follows from m ≥ n -1 and the third inequality holds for m ≥ 4. Thus, the number of random walks a token needs to perform until it ends up at a node with some destination token is at most O (log n ) w.h.p. By taking a union bound over all the n tokens, we conclude that w.h.p. every token performs at most O (log n ) random walks. The random walks can be performed simultaneously in O τ ( G · log n ) rounds, so w.h.p. the total number of rounds is O τ ( G · log 2 n ).

Next, we show that given two nodes u, v , Pr( ( t u ) = v ) ∈ [(1 -λ /n, ) (1 + λ /n ) ]. Let E v denote the event that the source token of u ends up in a compartment with a destination token of v . Let E denote the event that the source token of u ends up in a compartment with some destination token.

By our choice of τ ( λ ′ ), we have that for all v , Pr( E v ) ∈ [ k 2 m -kλ , ′ k 2 m + kλ ′ ] and Pr( E ) ∈ [ n ( k 2 m -kλ ′ ) , n ( k 2 m + kλ ′ )] . Therefore, is sufficiently small

$$[ n \left ( \frac { k } { 2 m } - k \lambda ^ { \prime } \right ), n \left ( \frac { k } { 2 m } + k \lambda ^ { \prime } \right ) ]. \text{ Therefore,} \\ \frac { \frac { k } { 2 m } - k \lambda ^ { \prime } } { n \left ( \frac { k } { 2 m } + k \lambda ^ { \prime } \right ) } \leq \Pr ( t ( u ) = v ) & \leq \frac { \frac { k } { 2 m } + k \lambda ^ { \prime } } { n \left ( \frac { k } { 2 m } - k \lambda ^ { \prime } \right ) } \\ \frac { 1 } { n } \cdot \frac { 1 - 2 m \lambda ^ { \prime } } { 1 + 2 m \lambda ^ { \prime } } \leq \Pr ( t ( u ) = v ) & \leq \frac { 1 } { n } \cdot \frac { 1 + 2 m \lambda ^ { \prime } } { 1 - 2 m \lambda ^ { \prime } } \\ \frac { 1 } { n } \cdot ( 1 - 8 m \lambda ^ { \prime } ) & \leq \Pr ( t ( u ) = v ) & \leq \frac { 1 } { n } \cdot ( 1 + 8 m \lambda ^ { \prime } ) \quad \text{ when } \lambda ^ { \prime } \text{ is sufficiently } s ; \\ \frac { 1 } { n } \cdot ( 1 - \lambda ) & \leq \Pr ( t ( u ) = v ) & \leq \frac { 1 } { n } \cdot ( 1 + \lambda ) \quad \quad \lambda ^ { \prime } \leq \lambda / 8 m \.$$

Note that since all the source tokens perform random walks independently, when we condition on the choice of nodes in Z for any u / Z ∈ ⊆ V , it is still true that

$$\Pr \left ( \mathcal { E } _ { v } | \bigwedge _ { z \in Z } t ( z ) \right ) \in \left [ \frac { k } { 2 m } - k \lambda ^ { \prime }, \frac { k } { 2 m } + k \lambda ^ { \prime } \right ]$$

and

$$\Pr \left ( \mathcal { E } | \bigwedge _ { z \in Z } t ( z ) \right ) \in \left [ n ( \frac { k } { 2 m } - k \lambda ^ { \prime } ), n ( \frac { k } { 2 m } + k \lambda ^ { \prime } ) \right ] \.$$

Thus, Pr ( t ( u ) = v | ∧ z ∈ Z t ( z ) ) ∈ [(1 -λ /n, ) (1 + λ /n ) ].

Step 3 : It remains to show that the messages from u to t ( u ) can be routed simultaneously for every u in ˜ ( O τ G ) rounds.

Let mid u ( ) denote the node where the source token of u is located at the end of Step 2. The message from u to mid u ( ) for every u can be simultaneously routed in ˜ ( O τ G ) rounds by following the same path taken by the random walk of the source token of u .

Suppose that t ( u ) = v . After the message reaches mid u ( ), it will follow the path taken by the random walk of the destination token of v to go to v (see Figure 2b). Note that multiple source tokens may be matched to a node v (some possibly from the other destination tokens of v ). When they follow the paths that lead back to t ( v ), it is possible that these paths merge and create congestion. However, using a standard Chernoff Bound argument, we can show that for any node v w.h.p. at most O (log n ) different nodes u have t ( u ) = v . Therefore, each step of the parallel random walk can be done with a O (log n ) factor blowup. Thus, the messages between u and t ( u ) can be routed in ˜ ( O τ G ) rounds. This completes the proof of Theorem 1.2.

## 4 Algorithms in the GOSSIP Model

In this section, we show that if we have a small number of non-empty nodes, then the empty nodes help approximate F p faster. As stated in Corollary 1.4, this result can be translated back to the CONGEST model using Theorem 1.2 with a blow-up factor ˜ ( O τ G ). We exhibit a pre-processing step that duplicates the values so that Ω( n ) nodes become non-empty which is crucial for the algorithms to work while preserving the occurrence ratios.

Throughout this section, for the sake of clarity, we consider the GOSSIP (0) model. However, running our algorithms in GOSSIP (1 /n c ), for some sufficiently large constant c , only incurs a small additive error 1 / poly( n ).

Lemma 4.1. If the number of non-empty nodes z &lt; n/ 3 , we can duplicate the values so that z glyph[ceilingleft] ( n/ 3) /z glyph[ceilingright] nodes become non-empty while preserving the occurrences ratios in O (log 2 n ) rounds in the GOSSIP model.

Proof. We divide the process into three phases. Pre-processing : We assume that the number of non-empty nodes is less than n/ 3, otherwise, we are done. First, the nodes compute the number of non-empty nodes z in O (log n ) rounds [KDG03]. Each node v will form a token that contains val ( v ) and t where t is originally set to glyph[ceilingleft] ( n/ 3) /z glyph[ceilingright] .

Splitting Phase: This phase consists of O (log n ) stages each of which consists of O (log n ) sub-stages. At the beginning of each stage, a node v has a collection of tokens

( x , t 1 1 ) , ( x , t 2 2 ) , . . . in its buffer. Each token ( x , t i i ) is split into two tokens ( x , i glyph[ceilingleft] t / i 2 ) and glyph[ceilingright] ( x, glyph[floorleft] t / i 2 ). glyph[floorright] It will send these two tokens to two random nodes using two rounds and delete ( x , t i i ) from its buffer. Note that the new tokens ( x , i glyph[ceilingleft] t / i 2 ) and ( glyph[ceilingright] x, glyph[floorleft] t / i 2 ) will not be split glyph[floorright] until the next stage. Every stage produces at most z glyph[ceilingleft] ( n/ 3) /z glyph[ceilingright] ≤ 2 n/ 3 new tokens. Each new token is sent to a random node and therefore each node contains O (log n ) new tokens w.h.p by Chernoff bound at the end of that stage. Hence, each sub-stage requires at most O (log n ) rounds to split all the tokens in its buffer w.h.p. After O (log n ) stages, w.h.p all nodes contain O (log n ) tokens and all tokens ( x, t ) satisfy t = 1.

Distributing Phase: At this point, we only have tokens in the form ( x, 1), or simply x . In each stage, if v holds more than one token, it will send all but one token (say the first that arrives at v ) to the nodes that it talks to. By a standard Chernoff bound argument, each stage requires O (log n ) rounds since each node always holds at most O (log n ) tokens w.h.p. We say a token x succeeds if it lands in a previously empty node u while no other token lands in u in the same round. Then, u never sends x away from this point onward. Since we have at most z · glyph[ceilingleft] ( n/ 3) /z glyph[ceilingright] ≤ 2 n/ 3 tokens, at least n/ 3 nodes are empty at all times. Consider a token x . In each stage, conditioning on all other tokens' choices, with probability at least 1 / 3, x succeeds. Hence, after O (log n ) stages, x succeeds w.h.p and therefore all tokens succeed w.h.p by taking a union bound over all tokens. Since we have at least glyph[ceilingleft] n/ 3 glyph[ceilingright] tokens, the number of non-empty nodes is Ω( n ). Note that the occurrence of each value is rescaled by a factor glyph[ceilingleft] ( n/ 3) /z glyph[ceilingright] .

After we estimate F p of the new instance, we can divide the estimator by ( glyph[ceilingleft] ( n/ 3) /z glyph[ceilingright] ) p to get an estimate for F p in the original instance. From now on, we can safely assume that the number of non-empty nodes F 1 = Ω( n ), otherwise, we can apply the above pre-processing. A key observation is that F 0 ≤ z , and thus we can analyze our algorithms for when F 0 is small instead.

An glyph[lscript] p -sampling primitive : An glyph[lscript] p -sampling algorithm samples a value i ∈ [ N ] with probability f p i /F p . More formally, Pr (sample i ) = f p i /F p .

The glyph[lscript] p -sampling primitive (for 0 ≤ p ≤ 2) has been extensively studied in the data stream model. An incomplete list includes [AKO11,JW18,MW10,JST11]. However, most streaming glyph[lscript] p -samplers are rather complicated, and it is unclear how to implement them in the GOSSIP model.

It is trivial to obtain an glyph[lscript] 1 -sample by virtue of the GOSSIP model. To obtain an glyph[lscript] 0 -sample (a random value that occurs at least once), we broadcast a randomly chosen pairwise hash function h : [ N ] → [ N 3 ] and identify the value corresponds to the smallest hash value in O (log n ) rounds.

Assuming that p is fixed, we now show that if F 0 = O n ( 1 / p ( -1) ) , then we can perform glyph[lscript] p -sampling in O (log n ) rounds (hence glyph[lscript] 2 -sampling can always be done in O (log n ) rounds since F 0 ≤ n ). The sampling algorithm proceeds as follows.

Each node v uses p rounds to talk to p random nodes u , . . . , u 1 p . It declares success if val ( u 1 ) = . . . = val ( u p ). In that case, let val ( u 1 ) be v 's sample. Among the successful nodes, to break symmetry, broadcast the sample of the node with the smallest ID. If no node succeeds, repeat the process. The following lemma provides a lower bound on F p based on F 0 .

$$\text{Lemma } 4. 2. \ I f \, F _ { 1 } = \Omega ( n ) \ a n d \, F _ { 0 } = O \left ( n ^ { 1 / ( p - 1 ) } \right ), \, t h e n \, F _ { p } = \Omega \left ( n ^ { p - 1 } \right ).$$

Proof. Let the frequency vector be f = ( f , . . . , f 1 N ). Without loss of generality, suppose the potentially non-zero entries of f be f , . . . , f 1 Kn 1 / p ( -1) for some constant K . Note that

based on our assumption, f j = 0 for all j &gt; Kn 1 / p ( -1) . Let f ′ = ( f , . . . , f 1 Kn 1 / p ( -1) ) be the vector formed by the first Kn 1 / p ( -1) entries. Note that ‖ f ′ ‖ 1 ≥ Cn for some constant 0 &lt; C ≤ 1 as assumed.

We will use the following inequality: if the vector x has n entries then

$$\| x \| _ { q } \leq \left ( n ^ { 1 / q - 1 / p } \right ) \| x \| _ { p } \,, \, \text{for} \, 0 < q < p \,.$$

Note that f ′ has Kn 1 / p ( -1) entries. Let K ′ = K 1 -1 /p . We have

$$\zeta \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdots \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cd. \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cd. \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cd� \quad \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdcolon \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdor \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdet \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdod \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdore \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdi \quad \quad \quad$$

The last step follows since K and C are constants and p is fixed.

Theorem 4.3. If F 0 = O n ( 1 / p ( -1) ) , then the described algorithm obtains an glyph[lscript] p -sample in O (log n ) rounds in the GOSSIP model w.h.p.

Proof. We can apply the pre-processing step so that F 1 = Ω( n ) while the occurrences ratios are preserved. The probability that a node succeeds is Ω ( ∑ N i =1 f p i /n p ) = Ω( F /n p p ).

Appealing to Lemma 4.2, F p ≥ n p -1 /K ′ for some constant K ′ . Hence, Pr ( v succeeds) ≥ 1 / K n ( ′ ). The probability that all n nodes fail is at most (1 -1 / K n ( ′ )) n ≤ e -1 /K ′ . We therefore succeed w.h.p by repeating O (log n ) times. Given that v succeeds, the probability that it samples value i is ( f p i /n p ) / ( ∑ N j =1 f p j /n p ) = f p i /F p as required.

Approximating F p : The algorithm by Bar-Yossef et al. [BJK + 02] that we discuss in Appendix A for approximating F 0 up to a 1 ± glyph[epsilon1] factor w.h.p can be emulated in the GOSSIP model in O glyph[epsilon1] ( -2 log 2 n ) rounds. We now focus on approximating higher frequency moments. Let k ≤ p be an integer. We present an algorithm that w.h.p approximates F p (for p ≥ 2) in ˜ O glyph[epsilon1] ( -2 n 1 -k/p ) rounds if F 0 = O n ( 1 / k ( -1) ) . Recall that F 0 is at most the number of non-empty nodes. To approximate F p , our algorithm makes use of an approximation of F k and glyph[lscript] k -sampling. This generalizes the approach in [AKO11,MW10]. We will prove the following theorem.

We first consider the following algorithm that approximates F k . For j = 1 , . . . , Cglyph[epsilon1] -2 log n , where C is some sufficiently large constant, in the j -th phase, each nonempty node v uses k -1 rounds to talk to k -1 random nodes u , . . . , u 1 k -1 . It declares success if val ( v ) = val ( u 1 ) = . . . = val ( u k -1 ). Let I j,v be the indicator variable for the event v succeeds in the j -th phase. Let T = Cglyph[epsilon1] -2 log n . Return the estimate

$$\hat { F } _ { k } = \frac { n ^ { k - 1 } } { T } \cdot \sum _ { j = 1 } ^ { T } \sum _ { v = 1 } ^ { n } I _ { j, v } \.$$

We now prove Theorem 1.3. This theorem first shows that ˆ F k is a good approximation w.h.p. Then, it combines ˆ F k with glyph[lscript] k -sampling to compute a good estimate of F p in O glyph[epsilon1] ( -2 n 1 -k/p log 2 n ) rounds.

Proof of Theorem 1.3. We again can assume that F 1 = z = Ω( n ) as outlined earlier in this section. We first show that ˆ F k = (1 ± glyph[epsilon1] ) F k w.h.p. In expectation,

$$\mathbf E \left [ \hat { F } _ { k } \right ] = \frac { n ^ { k - 1 } } { T } \sum _ { j = 1 } ^ { T } \sum _ { v = 1 } ^ { n } \mathbf E \left [ I _ { j, v } \right ] = \frac { n ^ { k - 1 } } { T } \sum _ { j = 1 } ^ { T } \sum _ { v = 1 } ^ { n } \frac { f _ { \text{val} ( v ) } ^ { k - 1 } } { n ^ { k - 1 } } = \sum _ { i = 1 } ^ { N } f _ { i } \cdot f _ { i } ^ { k - 1 } = F _ { k } \.$$

Since the indicator variables I j,v are independent, we can apply Chernoff bound directly.

$$\Pr \left ( \left | \hat { F } _ { k } - F _ { k } \right | \geq \epsilon F _ { k } \right ) = \exp \left ( - \Omega \left ( \frac { T \epsilon ^ { 2 } F _ { k } } { n ^ { k - 1 } } \right ) \right ) \leq \exp \left ( - \Omega \left ( T \epsilon ^ { 2 } \right ) \right ) \leq 1 / \text{poly} ( n ) \.$$

The first inequality follows from Lemma 4.2 and the second inequality is because T = Cglyph[epsilon1] -2 log n for some sufficiently large constant C . Hence, we can approximate F k up to a 1 ± glyph[epsilon1] factor in O glyph[epsilon1] ( -2 log n ) rounds.

To approximate F p for p &gt; k , we use the following estimator. Let i be an glyph[lscript] k sample. We can compute f i exactly in O (log n ) rounds. Specifically, each node with value i will put 1 on it and 0 otherwise. Then, we can compute the sum using the algorithm in [KDG03]. Consider the following estimator:

$$\hat { F } _ { p } = \hat { F } _ { k } \cdot f _ { i } ^ { p - k } \.$$

We rely on the following lemma. We defer the proof to the end of this section.

$$L e m m a \ 4. 4. \ W e \ h a v e \ \mathbb { E } \left [ \hat { F } _ { p } \right ] = ( 1 \pm O ( \epsilon ) ) F _ { p } \ a n d \ \mathbb { V } \left [ \hat { F } _ { p } \right ] \leq 2 n ^ { 1 - k / p } F _ { p } ^ { 2 }.$$

Hence, by an application of Chebyshev bound, if we take the average of O n ( 1 -k/p glyph[epsilon1] -2 ) estimators, with constant probability, ˆ F p = (1 ± glyph[epsilon1] ) F p . We can amplify the success probability to 1 -1 / poly( n ) by the standard median trick, i.e., taking the median of O (log n ) such estimators.

Proof of Lemma 4.4. In expectation,

$$\mathbf E \left [ \hat { F } _ { p } \right ] & = \hat { F } _ { k } \cdot \sum _ { i = 1 } ^ { N } \frac { f _ { i } ^ { k } } { F _ { k } } f _ { i } ^ { p - k } \\ & = ( 1 \pm O ( \epsilon ) ) F _ { p } \.$$

We can bound the variance as follows.

$$\text{V} \left [ \hat { F } _ { p } \right ] & \leq ( 1 \pm O ( \epsilon ) ) F _ { k } ^ { 2 } \sum _ { i = 1 } ^ { N } \frac { f _ { i } ^ { k } } { F _ { k } } f _ { i } ^ { 2 ( p - k ) } \\ & \leq 2 F _ { k } F _ { 2 p - k } \.$$

We have ‖ f ‖ k ≤ n 1 /k -1 /p ‖ f ‖ p , and therefore F k ≤ n 1 -k/p F k/p p . Additionally, ‖ f ‖ 2 p -k ≤ ‖ f ‖ p which implies F 2 p -k ≤ F 2 -k/p p . Therefore, V [ ˆ F p ] ≤ 2 n 1 -k/p F 2 p .

## References

| [AKO11]    | Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming al- gorithms via precision sampling. In FOCS , pages 363-372. IEEE Computer Society, 2011.                                                                                                                     |
|------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [AKS83]    | Mikl´s o Ajtai, J´nos a Koml´s, o and Endre Szemer´di. e An o(n log n) sorting net- work. In STOC , pages 1-9. ACM, 1983.                                                                                                                                                         |
| [AMS99]    | Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approx- imating the frequency moments. J. Comput. Syst. Sci. , 58(1):137-147, 1999.                                                                                                                           |
| [BC09]     | Joshua Brody and Amit Chakrabarti. A multi-round communication lower bound for gap hamming and some consequences. In IEEE Conference on Com- putational Complexity , pages 358-368. IEEE Computer Society, 2009.                                                                  |
| [BC15]     | Vladimir Braverman and Stephen R. Chestnut. Universal sketches for the fre- quency negative moments and other decreasing streaming sums. In APPROX- RANDOM , volume 40 of LIPIcs , pages 591-605. Schloss Dagstuhl - Leibniz- Zentrum fuer Informatik, 2015.                      |
| [BCWY16]   | Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, and Lin F. Yang. Streaming space complexity of nearly all functions of one variable on frequency vectors. In PODS , pages 261-276. ACM, 2016.                                                                         |
| [BJK + 02] | Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In RANDOM , volume 2483 of Lecture Notes in Computer Science , pages 1-10. Springer, 2002.                                                                |
| [BO10]     | Vladimir Braverman and Rafail Ostrovsky. Zero-one frequency laws. In STOC , pages 281-290. ACM, 2010.                                                                                                                                                                             |
| [CBM06]    | Amit Chakrabarti, Khanh Do Ba, and S. Muthukrishnan. Estimating entropy and entropy norm on data streams. In STACS , volume 3884 of Lecture Notes in Computer Science , pages 196-205. Springer, 2006.                                                                            |
| [CCM10]    | Amit Chakrabarti, Graham Cormode, and Andrew McGregor. A near-optimal algorithm for estimating the entropy of a stream. ACM Trans. Algorithms , 6(3):51:1-51:21, 2010.                                                                                                            |
| [CKS03]    | Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In IEEE Conference on Computational Complexity , pages 107-117. IEEE Com- puter Society, 2003.                                       |
| [CP12]     | Jen-Yeu Chen and Gopal Pandurangan. Almost-optimal gossip-based aggregate computation. SIAM Journal on Computing , 41(3):455-483, 2012.                                                                                                                                           |
| [DGH + 87] | Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. Epidemic algorithms for replicated database maintenance. In Proc. 6th ACM Symposium on Principles of Distributed Computing (PODC) , pages 1-12, 1987. |

| [FG85]     | A.M. Frieze and G.R. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics , 10(1):57 - 77, 1985.                                                                                          |
|------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [Gan15]    | Sumit Ganguly. Taylor polynomial estimator for estimating frequency moments. In ICALP (1) , volume 9134 of Lecture Notes in Computer Science , pages 542- 553. Springer, 2015.                                                            |
| [GKS17]    | Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and routing in almost mixing time. In PODC , pages 131-140. ACM, 2017.                                                                                                     |
| [GKW13]    | George Giakkoupis, Anne-Marie Kermarrec, and Philipp Woelfel. Gossip pro- tocols for renaming and sorting. In Yehuda Afek, editor, DISC , 2013.                                                                                           |
| [GL18]     | Mohsen Ghaffari and Jason Li. New distributed algorithms in almost mixing time via transformations from parallel algorithms. In DISC , volume 121 of LIPIcs , pages 31:1-31:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. |
| [GMT05]    | Yu Gu, Andrew McCallum, and Donald F. Towsley. Detecting anomalies in network traffic using maximum entropy estimation. In Internet Measurment Conference , pages 345-350. USENIX Association, 2005.                                      |
| [Gol11]    | Oded Goldreich. Basic facts about expander graphs. In Studies in Complexity and Cryptography , volume 6650 of Lecture Notes in Computer Science , pages 451-464. Springer, 2011.                                                          |
| [GT01]     | Phillip B. Gibbons and Srikanta Tirthapura. Estimating simple functions on the union of data streams. In SPAA , pages 281-291. ACM, 2001.                                                                                                 |
| [HLW06]    | Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society , 43(4):439-561, 2006.                                                                              |
| [HMS18]    | Bernhard Haeupler, Jeet Mohapatra, and Hsin-Hao Su. Optimal gossip al- gorithms for exact and approximate quantile computations. In PODC , pages 179-188. ACM, 2018.                                                                      |
| [HNO08]    | Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming entropy via approximation theory. In FOCS , pages 489-498. IEEE Computer Society, 2008.                                                                 |
| [Ind06]    | Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM , 53(3):307-323, 2006.                                                                                                        |
| [IW05]     | Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In STOC , pages 202-208. ACM, 2005.                                                                                                   |
| [JST11]    | Hossein Jowhari, Mert Saglam, and G´bor a Tardos. Tight bounds for lp samplers, finding duplicates in streams, and related problems. In PODS , pages 49-58. ACM, 2011.                                                                    |
| [JVG + 07] | M´rk a Jelasity, Spyros Voulgaris, Rachid Guerraoui, Anne-Marie Kermarrec, and Maarten van Steen. Gossip-based peer sampling. ACM Trans. Comput. Syst. , 25(3), August 2007.                                                              |

| [JW18]     | Rajesh Jayaram and David P. Woodruff. Perfect lp sampling in a data stream. In FOCS , pages 544-555. IEEE Computer Society, 2018.                                                                                                      |
|------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [KDG03]    | David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS) , pages 482-491, 2003.                                                           |
| [KDN + 06] | Srinivas Kashyap, Supratim Deb, K. V. M. Naidu, Rajeev Rastogi, and Anand Srinivasan. Efficient gossip-based aggregate computation. In Proc. of the 25th ACM Symposium on Principles of Database Systems (PODS) , pages 308-317, 2006. |
| [KLS08]    | Fabian Kuhn, Thomas Locher, and Stefan Schmid. Distributed computation of the mode. In PODC , pages 15-24. ACM, 2008.                                                                                                                  |
| [KLW07]    | Fabian Kuhn, Thomas Locher, and Rogert Wattenhofer. Tight bounds for dis- tributed selection. In Proc. of 19th Annual ACM Symposium on Parallel Algo- rithms and Architectures (SPAA) , pages 145-153, 2007.                           |
| [KNW10]    | Daniel M. Kane, Jelani Nelson, and David P. Woodruff. An optimal algorithm for the distinct elements problem. In PODS , pages 41-52. ACM, 2010.                                                                                        |
| [KO11]     | Fabian Kuhn and Rotem Oshman. The complexity of data aggregation in di- rected networks. In DISC , volume 6950 of Lecture Notes in Computer Science , pages 416-431. Springer, 2011.                                                   |
| [KSSV00]   | R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS) , pages 565-574, 2000.                                                       |
| [MW10]     | Morteza Monemizadeh and David P. Woodruff. 1-pass relative-error l p-sampling with applications. In SODA , pages 1143-1160. SIAM, 2010.                                                                                                |
| [Pel00]    | David Peleg. Distributed Computing: A Locality-sensitive Approach . Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.                                                                                       |
| [Pit87]    | Boris Pittel. On spreading a rumor. SIAM Journal on Applied Mathematics , 47(1):213-223, 1987.                                                                                                                                         |
| [Woo04]    | David P. Woodruff. Optimal space lower bounds for all frequency moments. In SODA , pages 167-175. SIAM, 2004.                                                                                                                          |
| [WP05]     | Arno Wagner and Bernhard Plattner. Entropy based worm and anomaly detec- tion in fast IP networks. In WETICE , pages 172-177. IEEE Computer Society, 2005.                                                                             |
| [XZB05]    | Kuai Xu, Zhi-Li Zhang, and Supratik Bhattacharyya. Profiling internet back- bone traffic: behavior models and applications. In SIGCOMM , pages 169-180. ACM, 2005.                                                                     |

## A Upper and Lower Bounds for Approximating F p in the CONGEST model

## A.1 Upper bounds

Approximating F 0 : We show how to run the algorithm by Bar-Yossef et al. [BJK + 02] in the CONGEST model. Kuhn et al. [KLS08] also outlined how to run a different streaming algorithm for estimating F 0 . However, the number of rounds for a 1 ± glyph[epsilon1] approximation w.h.p is unclear in their paper.

The algorithm is as follows. We pick a pairwise hash function h : [ N ] → [ M ]. Let t = glyph[ceilingleft] 100 glyph[epsilon1] -2 glyph[ceilingright] , M = N 3 , and w be the glyph[ceilingleft] t glyph[ceilingright] -th smallest value among the hash values W = { h (val ( v )) : v ∈ V } . We have the following: tM/w is a 1 ± glyph[epsilon1] approximation of F 0 with probability at least 2/3 [BJK + 02].

In the CONGEST model, the leader can broadcast the hash function. Then, each node v computes h (val ( v )). As mentioned above, the nodes can find the t -th smallest hash value in W in O D ( + ) rounds. t Hence, the total number of rounds is O D ( + glyph[epsilon1] -2 ) for constant success probability.

To amplify the success probability to 1 -1 / poly( n ), we use log n different hash functions and take the median of the corresponding estimates. At first, it is unclear how to pipeline this approach on the BFS tree to run in O D ( + glyph[epsilon1] -2 log n ) rounds instead of O (log n · ( D + glyph[epsilon1] -2 )) rounds. We show that this is possible. The following lemma generalizes Lemma 4.3.1 in [Pel00].

Lemma A.1. Suppose each element belongs to exactly one of k groups. Upcasting the t smallest elements of k groups on a tree T can be performed in O ( depth ( T ) + kt ) rounds in the CONGEST model.

Proof. Let the levels of the nodes be 1 , 2 , . . . , depth ( T ) where the root is at level depth ( T ). For each node v , from round level( v ) + j to level( v ) + j + t -1, it sends the smallest value in group j in its memory that has not been sent before to its parent.

Suppose that the i -th smallest element of group j is in the subtree T v (the subtree that is rooted at v ) originally. Then, we claim that at the end of round level( v ) + j + i -1, it will be stored in v . Furthermore, at the end of round level( v ) + j + , it will be upcasted i to v 's parent. We prove by triple-induction on level( v , j ) and i . The base case where level( v ) = 1 , j = 1 , i = 1 can easily be checked.

Consider a node v where level( v ) = glyph[lscript] . Suppose the i -th smallest element x of group j is in T v originally. We first need to show that at the end of round glyph[lscript] + j + i -1, the element x is sent to v . We know that one of v 's children, say u , must have x in T u ; note that level( u ) = glyph[lscript] -1. By induction, at the end of round ( glyph[lscript] -1) + j + , we know that i u must have sent x to v . It remains to show that at the end of round glyph[lscript] + j + , i v will send x to its parent. By induction, all the i ′ -th smallest elements of group j that are in T v , where i ′ &lt; i , must have been upcasted to v 's parent at the end of round glyph[lscript] + j + i -1. Hence, v must upcast the i -th smallest value of group j to its parent at the end of round glyph[lscript] + j + . i Therefore, after O ( depth ( T ) + kt ) rounds, the root must have all the desired values. It can downcast them back to other nodes in O ( depth ( T ) + kt ) rounds.

As a result, we can find all O glyph[epsilon1] ( -2 ) smallest hash values of each of O (log n ) hash functions in O D ( + glyph[epsilon1] -2 log n ) rounds using the BFS tree.

Approximating F 2 : To approximate the second frequency moment F 2 , we adapt the well-known tug-of-war sketch in [AMS99] to the CONGEST model. The adaptation, using O D ( + glyph[epsilon1] -2 log n ) rounds, for a 1 ± glyph[epsilon1] approximation with high probability is quite simple and can be found in [KLS08].

Approximating F p (for p &gt; 2 : ) The AMS sketch for F p in [AMS99] can be adapted to the CONGEST model as follows. First, the leader samples a node v and try to compute r = |{ u ∈ V : u &gt; v ∧ val ( u ) = val ( v ) }| . We can compute r in O D ( ) rounds. After the leader broadcasts v , we let v broadcasts its value val ( v ). Finally, each node u now knows if u &gt; v and val ( u ) = val ( v ). Then, we can compute the sum r = ∑ u ∈ V I [ u &gt; v ∧ val ( u ) = val ( v )]. All of these steps can be done in O D ( ) rounds. Let X = n r ( p -( r -1) p ). One can argue that E [ X ] = F p . Furthermore, if we repeat O glyph[epsilon1] ( -2 min( n, N ) 1 -1 /p log n ) times and take the average as the final estimate ˆ , X it can be shown that ˆ X is a 1 ± glyph[epsilon1] approximation of F p with high probability [AMS99].Thus, we obtain an O D ( + glyph[epsilon1] -2 min( n, N ) 1 -1 /p log n )-round algorithm via a careful pipelining.

We summarize the discussion above in Theorem 2.1.

## A.2 Lower bounds

glyph[negationslash]

Ω( D ) lower bound for approximating F p up to a 1 ± 0 1 . factor : We now present lower bounds suggesting that these algorithms are tight. This provides a clear context and a good motivation for our exact algorithm in Section 2.2 which is one of our main results. It is easy to see that Ω( D ) rounds are required for some constant approximation. Consider n nodes a , . . . , a 1 n that are connected to one end c 1 of a chain c 1 , . . . , c D . Let the nodes b 1 , . . . , b n connect to the other end c D of the chain. Set val ( a i ) = i for all i and val ( c j ) = NULL for all j . In the first case, val ( b i ) = i and in the second case val ( b i ) = i + n . In order for each a i to distinguish between the two cases, Ω( D ) rounds are clearly needed. In the first case, F 0 = n and in the second case F 0 = 2 n (for p = 0, the first case corresponds to F p = n 2 p and the second case corresponds to F p = 2 n ). A (1 ± 0 1) approximation for . p ∈ { 0 2 3 , , , . . . } distinguishes the two cases and therefore requires Ω( D ) rounds.

glyph[negationslash]

Conditional ˜ ( Ω glyph[epsilon1] -2 ) lower bound for approximating F p up to a 1 ± glyph[epsilon1] factor : We now reason why the above algorithms might be optimal for a 1 ± glyph[epsilon1] approximation, in terms of glyph[epsilon1] , based on a conjecture of Brody-Chakrabarti [BC09]. For F p (where p = 1 is a fixed), we consider the following communication problem in which Alice and Bob have the sets A ⊆ [ N ] and B ⊆ [ N ] respectively. Let C be the multiset formed by A and B . The goal is to estimate F p ( C ) up to a 1 ± 1 / √ N factor with some sufficiently large constant success probability. For this problem, Woodruff gave a one-round lower bound Ω( N ) on the number of bits that Alice and Bob need to communicate, via a reduction from the one-way GapHamming-Distance problem of size N [Woo04]. Hence, if glyph[epsilon1] = Θ(1 / √ N ), this implies an Ω( glyph[epsilon1] -2 ) lower bound.

It is conjectured in [BC09] (see conjecture 2) that the total communication of the GapHamming-Distance problem of size N , irrespective of the number of rounds, must be Ω( N ) bits. Hence, if Alice and Bob can communicate O (log n ) bits in each round, the number of rounds must be Ω( glyph[epsilon1] -2 / log n ).

Assuming their conjecture holds, then in the worst case, Ω( glyph[epsilon1] -2 / log n ) rounds are needed in the CONGEST model to approximate F p up to a 1 ± glyph[epsilon1] factor. To see this, consider a graph G of 2 N nodes, i.e., n = Θ( N ). If i ∈ A , then Alice sets val ( ) = i i , otherwise, she sets val ( ) = NULL. i Similarly, if i ∈ B then Bob sets val ( N + ) = i i , otherwise, he sets

val ( N + ) = NULL. One example that works is that i L and R are cliques and (1 , N +1) ∈ E . In fact, the conditional lower bound holds for any graph in which L and R are connected component and | E L,R ( ) | = O (1).

Observe that G is connected as required, but in each round, only O (log n ) bits can be communicated between L and R via the edge (1 , N + 1). Hence, if we can approximate F p ( C ) up to a 1 ± glyph[epsilon1] factor in G in r rounds, it means that Alice and Bob can use this as a protocol to approximate F p ( C ) using O r ( log n ) bits of communication and therefore r = Ω( glyph[epsilon1] -2 / log n ). In this construction, n = Ω( N ).

˜ ( Ω N 1 -2 /p ) lower bound for approximating F p up to a 1 ± 0 1 . factor : We also observe that approximating F p (for p &gt; 2) cannot be done in fewer than O N ( 1 -2 /p / log n ) rounds. This is based on a suitable modification of the reduction in [AMS99]. In the t -player disjointness problem, player i has the set A i and the players want to learn (with some sufficiently high constant success probability) if the all the sets are disjoint (YES case) or they intersect at a unique element (NO case), with the promise that one of the two cases happens. In the blackboard model, the players can send messages to a blackboard for others to see. The total size of all the messages must be at least Ω( N/t +log N ) [CKS03]. Consider a graph with t parts each of which is a clique of N nodes. The i -th part encodes A i in the same fashion above. It is easy to see that if t &gt; 2 1 /p N 1 /p , then, a (1 ± 0 1)-approximation of . F p can distinguish the YES case ( F p ≤ N ) and the NO case ( F p ≥ t p &gt; 2 N ). Each part connects with a node b that serves as a blackboard via a single edge. In each round in the CONGEST model, the players can send O t ( log n ) bits of message to the blackboard in total. Hence, the number of rounds must be Ω( N/ t ( 2 log n )) = Ω( N 1 -2 /p / log n ) = Ω( n (1 -2 /p / ) (1+1 /p ) / log n ), since n = t · N = Θ( N 1+1 /p ).

glyph[negationslash]

An ˜ ( Ω n ) lower bound for computing F p exactly : Next, we give a simple unconditional lower bound for computing F p exactly. Consider the 2-player disjointness problem. In the NO case, we have F 0 = | A | + | B | -1 and in the YES case, we have F 0 = | A | + | B | . For general p , the NO case corresponds to F p = | A | + | B | -2+2 p and the YES case corresponds to F p = | A | + | B | . Hence, for p = 1, given an exact algorithm for F p in the CONGEST model that uses r rounds, the two players can use that to solve Disjointness with O r ( log n ) bits of communication (they use 2 extra rounds to send each other | A | and | B | ). Hence, r = Ω( n/ log n ).
Hsin-Hao Su Hoa T. Vu
Distributed Data Summarization in Well-Connected Networks
We study distributed algorithms for some fundamental problems in data
summarization. Given a communication graph $G$ of $n$ nodes each of which may
hold a value initially, we focus on computing $\sum_{i=1}^N g(f_i)$, where
$f_i$ is the number of occurrences of value $i$ and $g$ is some fixed function.
This includes important statistics such as the number of distinct elements,
frequency moments, and the empirical entropy of the data.
  In the CONGEST model, a simple adaptation from streaming lower bounds shows
that it requires $\tilde{\Omega}(D+ n)$ rounds, where $D$ is the diameter of
the graph, to compute some of these statistics exactly. However, these lower
bounds do not hold for graphs that are well-connected. We give an algorithm
that computes $\sum_{i=1}^{N} g(f_i)$ exactly in $\tau_G \cdot 2^{O(\sqrt{\log
n})}$ rounds where $\tau_G$ is the mixing time of $G$. This also has
applications in computing the top $k$ most frequent elements.
  We demonstrate that there is a high similarity between the GOSSIP model and
the CONGEST model in well-connected graphs. In particular, we show that each
round of the GOSSIP model can be simulated almost-perfectly in
$\tilde{O}(\tau_G $ rounds of the CONGEST model. To this end, we develop a new
algorithm for the GOSSIP model that $1\pm \epsilon$ approximates the $p$-th
frequency moment $F_p = \sum_{i=1}^N f_i^p$ in $\tilde{O}(\epsilon^{-2}
n^{1-k/p})$ rounds, for $p \geq2$, when the number of distinct elements $F_0$
is at most $O\left(n^{1/(k-1)}\right)$. This result can be translated back to
the CONGEST model with a factor $\tilde{O}(\tau_G)$ blow-up in the number of
rounds.