The role of randomness in the broadcast congested clique model

https://doi.org/10.1016/j.ic.2020.104669Get rights and content

Abstract

We study the role of randomness in the broadcast congested clique model. This is a message-passing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node.

This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results:

  • If more than one round is allowed, public randomness is as powerful as private randomness.

  • One-round public-coin algorithms can be exponentially more powerful than deterministic algorithms running in several rounds.

  • One-round public-coin algorithms can be exponentially more powerful than one-round private-coin algorithms.

  • One-round private-coin algorithms can be exponentially more powerful than one-round deterministic algorithms.

Introduction

The congested clique model is a message-passing model of distributed computation introduced by Lotker, Patt-Shamir, Pavlov, and Peleg [1]. This model allows us to separate and understand the impact of congestion in distributed computing. The point is the following: if the communication network is a complete graph and the cost of local computation is ignored, then the only obstacle to perform any task is due to congestion alone. In other words, we intend to understand the effect of the bandwidth by isolating it.

Despite the theoretical motivation of the congested clique model, examples of distributed and parallel systems where the efficiency depends heavily on the bandwidth, are increasingly less exceptional (Mapreduce [2], Pregel [3], Spark [4], Hadoop [5], Dryad [6], etc.).

The congested clique model is defined as follows. There are n nodes which are given distinct identities (IDs), that we assume for simplicity to be numbers between 1 and n. In this paper we consider the situation where the joint input to the nodes is a graph G. More precisely, each node v receives as input an n-bit boolean vector xv{0,1}n, which is the indicator function of its neighborhood in G. Note that the input graph G is an arbitrary n-node graph, a subgraph of the communication network Kn, which is the complete graph (communication is all-to-all).

Nodes execute an algorithm, communicating with each other in synchronous rounds with the objective of collectively computing some function f that depends on G. In this paper we study a variant of the congested clique model, namely, the broadcast congested clique model, where at each round each vertex broadcasts only one (the same) b-bit message through all of its n1 incident communication links [7], [8]. In each round of the algorithm, each of the n nodes has to decide whether to stop or continue. An algorithm halts when every vertex stops. At that moment, every node must know f(G). Hence, f(G) is called the output of the distributed algorithm. The parameter b (the maximum size of a message sent by a node) is known as the bandwidth of the algorithm. We denote by R the number of rounds. The product Rb corresponds to the total number of bits received by a node through one link, and we call it the cost of the algorithm.

Function f defines the problem to be solved. In this paper we are interested in decision problems. A decision problem is a function where the output is either 0 or 1, or reject-accept, respectively. In such a case, we say that G is accepted if every node outputs accept (or 1) and G is rejected if every vertex outputs reject (or 0). For example, in this paper we study problem Twins, which consists in accepting input graphs containing at least two vertices having the same neighborhood.

In the literature it is common to define the rejection of a distributed decision problem in a slightly different way. Indeed, when G is rejected, instead of asking that every vertex rejects, the most common convention is to ask that at least one vertex rejects. We remark that in the broadcast congested clique model, both definitions are equivalent, since communication is all-to-all, and therefore every vertex can learn in one round (and communicating one bit) whether every vertex accepts or not.

An algorithm may be deterministic or randomized. We distinguish two sub-cases of randomized algorithms: the private coin setting, where each node flips its own coin; and the public coin setting, where the coin is shared among all nodes. An ε-error algorithm A that computes a function f is a randomized algorithm such that, for every input graph G,Pr(Aoutputsf(G))1ε.

In the case where ε=1/nO(1), we say that A computes f with high probability (whp).

In this paper we are particularly interested in the one-round broadcast congested clique model. One can view this particular case as follows: nodes need to send, simultaneously, a b-bit message to some referee allowing him/her to answer, typically, questions of the form “Does the input graph G belong to the graph class C?”

The goal of this work is to explore the role of randomness. Specifically, the difference between deterministic algorithms, public coin algorithms and private coin algorithms.

In Section 2 we study multi-round randomized algorithms. We start proving that there is essentially no difference between the public and the private coin settings. More precisely, we extend a classic result of Newman [9] and show that any public coin algorithm in the broadcast congested clique model can be simulated by a private coin algorithm (slightly increasing the number of rounds, the bandwidth and the error probability). In order to separate multi-round deterministic and randomized algorithms, we introduce function

defined over labeled graphs of size 2n. This function equals 1 if and only if the adjacency matrix of G[{1,,n}] is equal to the adjacency matrix of G[{n+1,,2n}]. In other words, if for every i,j[n], vertex j belongs to N(i) implies that vertex j+n belongs to N(i+n) and vice versa. We prove that, in the public coin setting, the cost Rb of this function is O(logn), even for one-round algorithms, while the cost in the deterministic setting is Ω(n). (The proof of the upper bound O(logn) corresponding to the public coin algorithm appears in Section 3).

The previous results indicate that relevant differences between public and private randomness can only be found in one-round algorithms. In Section 3 we separate the deterministic, the private coin and the public coin settings of the one-round broadcast congested clique model. For achieving this we use problem Twins and some variants. The boolean function

returns accept if and only if graph G has at least two twins (that is, two nodes having the same neighborhood). We also consider function
, where x is the identifier of a node, and the result is 1 if and only if there is some other node having the same neighborhood of node identified with x. We prove that the deterministic message size complexity of
and Twinsx(G) is Θ(n). Also, both functions can be computed with one-round public coin and one-round private coin algorithms of message size O(logn). These algorithms, based on the classical fingerprint technique, have one-sided error O(1/nc) for any constant c>0. In order to separate the private and public coin settings we use a boolean function called
(see Section 1.3 for details). We prove that the message size complexity of this function is Ω(n) in the private coin setting, while it is O(logn) in the public coin setting. The main results of this paper are summarized in Table 1. Observe in Table 1 the exponential gap between private coins and determinism in the message size complexity of
. This situation is very different from what happens in the simultaneous 2-player case, where the gap between private coins and determinism is at most the square root of n [10] (see Section 1.3 for details).

There are several natural problems that cannot be solved with randomized algorithms using o(n) bits, even with public coins. This is the case of deciding whether the input graph contains a clique of size 4, or deciding whether the input graph has a cycle of length 5. In both cases the cost Rb=Ω(n) [7]. In Section 4 we complement those results, proving that the one-round randomized public coin message size complexity of the boolean functions

(that outputs 1 if and only if G has a triangle) and
(that outputs 1 if and only if G has diameter at most 3) is Ω(n). We obtain those results extending the arguments of [11], from the deterministic setting to the randomized one.

Finally, in Section 5, we revisit problem

, but in the framework of the unicast congested clique model. In the unicast congested clique model, nodes are allowed to send different messages in each round (i.e., sending up to n1 different messages each round). The unicast congested clique model is much more powerful than the broadcast one. In particular, we make use of the algebraic methods given in [12] in order to solve
with cost O(n0.158logn).

The simultaneous two-player model was already present in Yao's seminal communication complexity paper of 1979 [13]. He proved that the message size complexity of Eq, which simply tests whether two n-bit inputs are equal, is Θ(n) in the deterministic case (in fact he proved that this is also true even if players can communicate back-and-forth). Later, clear separations have been proved between deterministic, private coin and public coin algorithms. In the public coin setting with constant one-sided error, the message size complexity of Eq is O(1) [14]. On the other hand, for private coin algorithms of constant one-sided error, the message size complexity is much higher, Θ(n) [14], [15] (see Section 1.3 for details). More generally, Babai and Kimmel [14] proved that, for any function f, the gap between the deterministic and private coin message size complexities is at most the square root of n.

There are (at least) two natural ways to extend problem Eq to more than two players. This issue is addressed by Fischer, Oshman and Zwick [16] in the context of the number-in-hand model (where each player only knows its own input; players broadcast messages but they are not nodes of some input graph G). First, they define problem AllEq. In this simultaneous multi-party problem, each player receives a boolean vector {0,1}n and they have to decide whether all the k vectors are equal. In problem ExistsEq, the k players have to decide whether there exist at least two players with the same input. It is not difficult to see that in both the deterministic case and the public coin case the results for 2 players can be extended to k players (for ExistsEQ this holds for k2n, otherwise the problem is trivial). The private coin case is more involved. With respect to private coin algorithms of constant error, the authors of [16] prove, for problem AllEq, an upper bound of O(n/k+log(min(n,k))) and a lower bound of Ω(logn). In the case of ExistsEq the upper bound they show is O(logkn) while the lower bound is Ω(n).

An interesting example of a problem defined in the broadcast congested clique model where randomness helps is Connectivity, which is the decision problem of determining whether the input graph is connected. This problem can be easily solved in O(logn) rounds and bandwidth O(logn) by a deterministic algorithm simulating the classical algorithm of Boruvka [17]. A more careful analysis shows that the same argument can be used to solve the problem deterministically in two rounds and bandwidth O(n2logn) [18]. In [19] Jurdziński and Nowicki gave a deterministic algorithm for Connectivity that runs in O(lognloglogn) rounds and bandwidth O(logn). Not much is known with respect to lower bounds. In fact, in [20] Pai and Pemmaraju show that any algorithm solving Connectivity in the broadcast congested clique has cost Ω(logn), far from the cost O(log2nloglogn) of the algorithm of Jurdziński and Nowicki.

In [21], [22] Ahn et al. presented an extremely elegant one-round public coin algorithm that solves connectivity with high probability and bandwidth O(log4n). The algorithm uses a technique called linear sketches, which roughly consists in compressing vectors through a linear function. This technique allows to sample (with high probability) a random edge from the cut induced by any set of vertices. The authors use this capability to simulate in only one round of communication the whole Boruvka's algorithm. It is not known whether private randomness helps to solve Connectivity.

Another example where randomness helps is Reconstruction, the problem consisting in computing the function f(G)=E, i.e., every vertex ends up knowing the adjacency matrix of G. Roughly speaking, this problem is the hardest problem that one might attempt to solve. Indeed, since in this model nodes have unbounded computational power, any vertex knowing the adjacency matrix of G can compute any property of G without any further communication. Of course any algorithm (randomized or deterministic) solving Reconstruction has cost Θ(n). For that reason a restricted version of Reconstruction is considered, where a set of graphs G is fixed. G-Reconstruction is the function that outputs the adjacency matrix of G when G belongs to G, and outputs reject when G does not belong to G.

In [23] it is shown that G-Reconstruction can be solved with a deterministic one-round algorithm with bandwidth O(logn), when G is the class of trees, planar graphs, or any class defined by a finite set of excluded minors. In fact, the algorithm of [23] solves the problem with bandwidth O(d2logn) for every set of graphs of degeneracy at most d (trees have degeneracy 1, planar graphs have degeneracy 5). The upper bound on the bandwidth was improved to O(dlogn) in [18].

In [24] it is shown that any algorithm (deterministic or randomized) solving G-Reconstruction has cost Ω(log|Gn|n), where Gn is the set of n-node graphs in G. A common property of d-degenerate sets of graphs is that Gn=O(2dnlogn), so the lower bound can be reached by a deterministic one-round algorithm. This is not the case for any set of graphs. There are sets of graphs G such that Gn=2O(n), but any one-round deterministic algorithm solving G-Reconstruction has cost Ω(n) [24].

The use of randomness improves the upper bounds on the bandwidth with respect to deterministic algorithms. Indeed, for any set of graphs G, there is a two-round public coin algorithm that solves G-Reconstruction with bandwidth O(log|Gn|logn). Moreover, if G is an hereditary class of graphs, G-Reconstruction can be solved with a one-round private coin algorithm with bandwidth O(log|Gn|n), matching the lower-bound given above [24].

All our graphs are undirected. So, for any pair i,j of nodes, the bit number i of node (with identifier) j equals the bit number j of node i. In full words, each edge of the graph is known by the two players corresponding to its end-nodes. All our algorithms use Ω(logn) bits. We assume, w.l.o.g., that in each round each node sends its own number in the message transmitted to the referee (or broadcasted to the other nodes, or written in a whiteboard visible to every node; all these definitions are equivalent).

In this paper we study, among others, the following three boolean functions on graphs.

  • outputs 1 if and only if G has two vertices u and v with the same neighborhood, i.e., such that N(u)=N(v).

  • Twinsx(G) is a “pointed” version of previous function. Its output is 1 if and only if there is a vertex yx such that N(y)=N(x).

  • Translated-Twins is defined on input graphs G of size 2n, labeled from 1 to 2n. Its output is 1 if and only if G has a vertex i[n] such that, for any vertex j[n], jN(i)j+nN(i+n). In other words, the output is 1 if and only if there exists i such that N(i)+n=N(i+n).

For reductions we also use function

, whose output is G itself, i.e., the adjacency matrix of G. Note that if a deterministic algorithm computes Reconstruction on some family of n-vertex graphs Gn, then the cost Rb of such algorithm must be Ω(log(|Gn|)/n) [11].

The message cost of a one-round algorithm P, denoted by C(P), is the length of the longest message sent to the referee. The deterministic message size complexity, denoted Cdet(f), is the minimum message of any one-round deterministic algorithm computing f. Analogously, we denote Cϵpriv(f), Cϵpub(f), the message size complexity for ϵ-error public coin and ϵ-error private coin algorithms, respectively.

The simultaneous k-player model can be seen as a generalization of the one-round broadcast congested clique (despite having been introduced much earlier). It is defined as follows. Let f be a function having as input k boolean vectors of length n. There are k players {p1,,pk} who wish to compute the value of f on input (x1,,xk)({0,1}n)k. Player pi only sees the input xi, and also knows his/her own index i. All the k players simultaneously send a message to a referee. After that, the referee (another player who sees none of the inputs) announces the value f(x1,,xk) using only the information contained in the k messages. The message size complexities Cdet(f), Cϵpriv(f), Cϵpub(f), are defined as above. (Note that, in the one-round broadcast congested clique model, there is some shared information between the nodes or players: in fact, each edge of the input graph is known by two nodes).

Let us recall some classical results on the simultaneous 2-player model. Babai and Kimmel [14] have shown that the order of magnitude of the private coin randomized message size complexity of any function f is at least the square root of the deterministic message size complexity of f. They also characterize completely the function

, where
iff x=y.

Proposition 1 [14]

Consider the simultaneous 2-player model and a constant ϵ>0. The function

on two n-bit boolean vectors has the following message size complexities:
,
and
. For any boolean function f, Cϵpriv(f)=Ω(Cdet(f)).

We also use the following result of Chakrabarti et al. [10] for private-coin algorithms (the deterministic part is a matter of exercise).

Proposition 2 [10]

Consider the boolean function

that takes as input two boolean n×n matrices, and the output is 1 if and only if there is some 1in such that the i-th rows of the two matrices are equal. Then, for any ϵ<1/2,
. Also,
.

Section snippets

Public versus private randomness for multi-round algorithms

We start this section by showing that, in the broadcast congested clique model, private and public coin multi-round algorithms are equivalent (up to a logarithmic factor).

Theorem 1

Let ϵ,δ>0 be such that ϵ<1/3, and let f be a function f:Gn{0,1}, where Gn is the set of all graphs of size n. For every R-round ϵ-error public coin algorithm computing f in the broadcast congested clique model with bandwidth b, there exists an (R+1)-round (ϵ+δ)-error private coin algorithm computing f in the broadcast

Deterministic algorithms

Theorem 3

The one-round deterministic message size complexity of functions Twins, Twinx and Translated-Twins is Θ(n).

The upper bounds of O(n) are trivial so we only need to prove the lower bounds. For the first two problems, we use the following reduction.

Lemma 2

Assume that there is a one-round deterministic algorithm solving Twins (resp.

) on (2n+1)-node graphs using messages of size g(n). Then one can solve Reconstruction in one round on n-node graphs using messages of size 2g(n).

Proof

Let G be an arbitrary

Hard problems for public coin algorithms

Consider the boolean function

that outputs 1 if and only if G has a triangle, and the function
, that outputs 1 if and only if G has diameter at most 3. In [11] it is shown that the one-round deterministic message size complexity of these problems are lower-bounded by Ω(n), using a reduction from Reconstruction. However, as seen in Theorem 3, a reduction from Reconstruction does not imply lower bounds on the message size of randomized algorithms.

In the following theorem, we

Solving Twins deterministically in the unicast congested clique model

In this section we show that, when we remove the restriction of one-round algorithms, we can solve

in o(n) rounds with bandwidth O(logn) in the unicast congested clique model. Let G be a graph, and let A be the adjacency matrix of G. Call A2 the matrix multiplication of A with itself, over the ring of integer square matrices of dimension n.

Lemma 4

Let u and v be two vertices of G such that deg(u)=deg(v)=d. Then u and v are twins if and only if Auv2=d.

Proof

Observe that deg(u)=w[n]auw=w[n]awu.

Open problems

The future challenge is to determine the one-round message size complexity of Twins for private coin algorithms. Techniques for proving lower bounds in the similar problem ExistsEq, defined in the simultaneous n-player model, can not be used directly: in the broadcast congested clique model nodes share information. This subtle difference makes the problem of finding lower bounds elusive. This seems to be the case of Twins. More generally, as stated by Fischer, Oshman an Zwick [16], “the power

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgements

This research was partially supported by CONICYT PIA / Apoyo a Centros Cientíicos y Tecnológicos de Excelencia AFB 170001 (I.R.), Fondecyt 1170021 (I.R.), FONDECYT 11190482 (P.M.) and CONICYT via PAI + Convocatoria Nacional Subvención a la Incorporación en la Academia Año 2017 + PAI77170068 (P.M.)

References (28)

  • J. Nešetřil et al.

    Otakar Boruvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history

    Discrete Math.

    (2001)
  • E. Kushilevitz

    Communication complexity

    Adv. Comput.

    (1997)
  • Z. Lotker et al.

    Minimum-weight spanning tree construction in O(loglogn) communication rounds

    SIAM J. Comput.

    (2005)
  • J. Dean et al.

    Mapreduce: simplified data processing on large clusters

    Commun. ACM

    (2008)
  • G. Malewicz et al.

    Pregel: a system for large-scale graph processing

  • M. Zaharia et al.

    Spark: cluster computing with working sets

    HotCloud

    (2010)
  • T. White

    Hadoop: The Definitive Guide

    (2012)
  • M. Isard et al.

    Dryad: distributed data-parallel programs from sequential building blocks

  • A. Drucker et al.

    The communication complexity of distributed task allocation

  • A. Drucker et al.

    On the power of the congested clique model

  • E. Kushilevitz et al.

    Communication Complexity

    (1997)
  • A. Chakrabarti et al.

    Informational complexity and the direct sum problem for simultaneous message complexity

  • F. Becker et al.

    Adding a referee to an interconnection network: what can(not) be computed in one round

  • K. Censor-Hillel et al.

    Algebraic methods in the congested clique

  • Cited by (0)

    A preliminary version of (part of) this work appeared in the proceedings of the 21st International Colloquium on Structural Information and Communication Complexity SIROCCO 2014, held in Hida Takayama, Japan.

    View full text