Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication

Consider a graph problem P and the uniform distribution $\lambda$ over all $t$-vertex graphs, for some constant $t$. We denote a graph chosen from $\lambda$ as gadget. Our hard input graph distribution is the product distribution $\mu=\lambda^{n/t}$, i.e., graphs consisting of $n/t$ disjoint and independent gadgets chosen from $\lambda$.

Let $\mathcal{P}$ be a $\mathsf{BB}(k)$ communication protocol for problem P. We measure the amount of information about the edges of the input graph that is necessarily revealed by the transcript of $\mathcal{P}$, i.e., by the bits written on the blackboard. This quantity is usually referred to as the external information cost (see (Braverman, 2017) for an excellent exposition) of a protocol $\mathcal{P}$ and constitutes a lower bound on the communication cost of $\mathcal{P}$.

At the core of our lower bound argument lies a direct sum argument. Towards a contradiction, assume that the external information cost of $\mathcal{P}$ is $\delta\cdot n$, for a sufficiently small constant $\delta\ll\frac{1}{t}$. We then prove that $\mathcal{P}$ can be used to obtain a protocol $\mathcal{Q}$ with external information cost $t\cdot\delta$ that solves P on a single $t$-vertex gadget, i.e., on inputs chosen from $\lambda$. We further argue that since $t\cdot\delta$ is a very small constant, $\mathcal{Q}$ cannot depend much on the actual input of the problem. We then give a compression lemma, showing that there is a protocol $\mathcal{Q}^{\prime}$ that avoids communication altogether, while only marginally increasing the probability of error. Finally, to show that such a “silent” protocol $\mathcal{Q}^{\prime}$ cannot exist, we employ Yao’s lemma, which allows us to focus on deterministic protocols with distributional error, and then give simple problem-specific combinatorial arguments.

In Section 2, we define the $\mathsf{BB}(k)$ model and provide the necessary context on information theory. Next, we present our main result, our lower bound for non-trivial graph problems in the blackboard model, in Section 3. In Section 4, we summarize how known algorithms can be adapted to yield optimal (up to poly-logarithmic factors) communication protocols in the blackboard model. Last, we conclude in Section 5.

In the (shared) blackboard model, denoted by $\mathsf{BB}(k)$, we have $k$ parties that communicate by writing messages on a shared blackboard that is visible to all parties. The way the parties interact, and, in particular, the order in which the parties write onto the blackboard, is solely specified by the given communication protocol (and the current state of the blackboard), i.e., the model is therefore asynchronous. All parties have access to both private and public random coins.

In this paper, we study graph problems in the blackboard model. Given an input graph $G=(V,E)$ with $n=|V|$, we consider an edge-partition model without duplications, where the edges of $G$ are partitioned among the $k$ parties according to a partition function $Z:[V\times V]\rightarrow[k]$ that maps the set of all pairs of vertices of $G$ to the machines (since we consider undirected graphs, we assume that $Z(u,v)=Z(v,u)$, for every $u,v\in V$). This function does not reveal the set of edges of $G$ itself, however, it reveals that if an edge $uv$ is contained in the input graph, then it is located at machine $Z(u,v)$. For our lower bounds, we assume that $Z$ is chosen uniformly at random from the set of all symmetric mappings from $[V\times V]$ to $[k]$, and that $Z$ is known by all parties. For our upper bounds, we assume that $Z$ is chosen adversarially and $Z$ is not given to the parties. Instead, each machine $i$ then only knows the edges that are assigned to it at the beginning of the algorithm, i.e., the set of edges $\{uv\in E\ :\ Z(u,v)=i\}$.

For a given problem P, we say that a communication protocol $\mathcal{P}$ has error $\epsilon$ if, for any input graph, the probability that the joint output of the parties is a correct solution for P is at least $1-\epsilon$. This probability is taken over all private and public coins, and the random selection of the partition function $Z$.¹¹1We adapt this definition accordingly when considering adversarially chosen partition functions for the upper bounds in Section 4. We consider the global output of $\mathcal{P}$ as the union of the local outputs of the machines. For example, for MIS, every party is required to output an independent set so that the union of the parties’ outputs constitutes an MIS in the input graph. We say that a protocol is silent if none of the parties write on the blackboard.

The transcript of a protocol $\mathcal{P}$, denoted by $\Pi(\mathcal{P})$, is the entirety of the bits written onto the blackboard. The communication cost of a protocol $\mathcal{P}$ is the maximum length of $\Pi(\mathcal{P})$ in an execution of $\mathcal{P}$, which we denote by $|\Pi(\mathcal{P})|$. Then, the randomized $\epsilon$-error blackboard communication complexity of a problem P, denoted by $\textsc{CC}_{\epsilon}(P)$ is the minimum cost of a protocol $\mathcal{P}$ that solves P with error at most $\epsilon$.

Let $A$ be a random variable distributed according to a distribution $\mathcal{D}$. We denote the (Shannon) entropy of $A$ by $H_{\mathcal{D}}(A)$, where the index $\mathcal{D}$ may be dropped if the distribution is clear from the context. The mutual information of two random variables $A,B$ distributed according to $\mathcal{D}$ is denoted by $\operatorname*{\textbf{{I}}}_{\mathcal{D}}[A\ :\ B]=H_{\mathcal{D}}(A)-H_{\mathcal{D}}(A\ \mid\ B)$ (again, $\mathcal{D}$ may be dropped), where $H_{\mathcal{D}}(A\ \mid\ B)$ is the entropy of $A$ conditioned on $B$. We frequently use the shorthand $\{c\}$ for the event $\{C\!=\!c\}$, for a random variable $C$, and we write $\operatorname*{\textbf{{E}}}_{C}$ to denote the expected value operator where the expectation is taken over the range of $C$. The conditional mutual information of $A$ and $B$ conditioned on random variable $C$ is defined as

For a more detailed introduction to information theory, we refer the reader to (Cover and Thomas, 2006).

We will use the following properties of mutual information:

1. (1)

   Chain rule for mutual information. $\operatorname*{\textbf{{I}}}[A\ :\ B,C]=\operatorname*{\textbf{{I}}}[A\ :\ B]+\operatorname*{\textbf{{I}}}[A\ :\ C\ \mid\ B]$.

2. (2)

   Independent events. For random variables $A,B,C$ and event $E$: $\operatorname*{\textbf{{I}}}[A\ :\ B\mid C,E]=\operatorname*{\textbf{{I}}}[A\ :\ B\mid C]$, if $E$ is independent of $A,B,C$.

3. (3)

   Conditioning on independent variable. (see e.g. Claim 2.3. in (Assadi et al., 2016a) for a proof) Let $A,B,C,D$ be jointly distributed random variables so that $A$ and $D$ are independent conditioned on $C$. Then, $\operatorname*{\textbf{{I}}}[A\ :\ B\mid C,D]\geqslant\operatorname*{\textbf{{I}}}[A\ :\ B\mid C]\ .$

Our lower bound proof relies on Pinsker’s Inequality, which relates the total variation distance to the Kullback-Leibler divergence of two distributions:

In our input distributions, we assume that the vertex set $V$ of our input graph $G=(V,E)$ is fixed and known to all parties. Furthermore, w.l.o.g. we assume that $V=[|V|]$²²2For an integer $\ell$ we write $[\ell]$ to denote the set $\{1,2,\dots,\ell\}$.. We will now define a distribution $\rho_{N}$ of partition functions that map the set of potential edges $V\times V$ to the parties $[k]$, where the subscript $N$ denotes the cardinality of the set of vertices, and two distributions $\lambda$ and $\mu$ over the edge set of our input graph. Since we need to specify both the partition function and the input graph as the input to a protocol in the $\mathsf{BB}(k)$ model, the relevant distributions are therefore the product distributions $\lambda\times\rho_{N}$ and $\mu\times\rho_{N}$.

The lower bounds proved in this paper hold for non-trivial problems, which are defined by means of good partitions:

Observe that this is only possible if the number of parties exceeds the number of potential edges, i.e., if $k\geqslant{t\choose 2}$. In our setting, $t$ is a small constant and $k$ is sufficiently large. Almost all partitions are therefore good.

For the parties to contribute to the global output of the protocol by only seeing at most one edge and without communication is impossible for most problems. The class of non-trivial problems is therefore large. In Section 3.8, we give formal proofs, demonstrating that many key problems considered in distributed computing are non-trivial.

We now define the (external) information cost of a protocol in the $\mathsf{BB}(k)$ model:

Informally, $\operatorname*{\mathsf{ICost}}_{\mu\times\rho_{n}}(\mathcal{P})$ is the amount of information revealed about the input edge set by the transcript, given that the public randomness and the partition function are known. We define $\operatorname*{\mathsf{ICost}}_{\lambda\times\rho_{t}}(\mathcal{P})$ in a similar way.

It is well-known that the external information cost of a protocol is a lower bound on its communication cost. For completeness, we give a proof in the following lemma:

In this section, we show that the information cost of a protocol for the multi-gadget case is lower-bounded by the information cost of a protocol for the single-gadget case, multiplied by the number of gadgets:

Next, we show that if a protocol $\mathcal{Q}$ solves single-gadget instances with small information cost, then there exists a silent protocol (i.e., a protocol that avoids all communication) with only slightly increased error.

In this section, we show that the existence of a randomized silent protocol for single-gadget instances with a sufficiently small error implies existence of a deterministic silent protocol for single-gadget instances that solves the problem on every input graph under some good partition.

First, we will argue that the probability that the partition function is good is at least $1/2$:

We now state and prove the main result of the section.

Theorem 1. P be a non-trivial graph problem. Then there exists $\delta(P)>0$ and $t=t(P)$ such that for any $k\geqslant 3t^{4}$ and $\epsilon\leqslant\delta(P)$ the randomized $\epsilon$-error blackboard communication complexity $\textsc{CC}_{\epsilon}(P)$ of $P$ is $\Omega(n)$, even if the edges of the input graph are partitioned randomly among the parties.

In this section we establish non-triviality of several fundamental graph problems. We point out that lower bounds are known for all of these problems in other distributed computing models such as the LOCAL model (see (Balliu et al., 2019; Kuhn et al., 2016)). However, these lower bounds do not directly translate to our setting since, in the $\mathsf{BB}(k)$ model, a player who receives an edge as input does not necessarily need to produce an output for this particular edge or its vertices.

In the proof of non-triviality of Maximal Matching we used gadgets of size 3 and in the proofs of non-triviality of all other problems we used gadgets of size 4. Together with Theorem 1 this implies the following

Computing a maximal matching in the $\mathsf{BB}$(k) model with communication cost $O(n\log n)$ is straightforward. The parties can simulate the Greedy matching algorithm, as follows: The blackboard serves as a variable $M$ that contains the current matching. Initially, the blackboard is empty and represents the empty set, i.e., $M\leftarrow\varnothing$. The parties proceed in order. At party $i$’s turn, party $i$ attempts to add each of its edges $e\in E_{i}$ in any order to the blackboard if possible, i.e., if $M\cup\{e\}$ is still a matching. Since any matching in an $n$-vertex graph is of size at most $n/2$, and each edge requires space $O(\log n)$ to be written onto the blackboard (e.g., by indicating the two endpoints of the edge), the communication cost is $O(n\log n)$.

Various algorithms are known for computing a $(1-\epsilon)$-approximation to Maximum Matching by repeatedly computing maximal matchings in subgraphs of the input graph (e.g. (McGregor, 2005; Ahn and Guha, 2011; Eggert et al., 2012; Konrad, 2018; binti Khalil and Konrad, 2020; Sepehr Assadi, 2021)). In order to implement these algorithms in the $\mathsf{BB}$(k) model, we need to make sure that the $k$ parties know which of their edges are contained in each of the respective subgraphs. If this can be achieved with communication cost $O(s)$ per subgraph, then a $\mathsf{BB}$(k) model implementation with cost $O((n\log n+s)\cdot r)$ can be obtained, where $r$ is the number of matchings computed.

The algorithm by McGregor (McGregor, 2005) follows this scheme and relies on the computation of $\frac{1}{\epsilon}^{O(\frac{1}{\epsilon})}$ maximal matchings in order to establish a $(1-\epsilon)$-approximate matching in general graphs. Specifying the respective subgraphs with small communication cost is straightforward for this algorithm, requiring a cost of $O(n\log n)$ (details omitted), and we thus obtain a $(1-\epsilon)$-approximation $\mathsf{BB}$(k) model algorithm with communication cost $O\left(n\log n\cdot\frac{1}{\epsilon}^{O(\frac{1}{\epsilon})}\right)$.

The dependency on $\epsilon$ can be improved in the case of bipartite graphs. Assadi et al. (Sepehr Assadi, 2021) very recently gave an algorithm for Maximum Matching in bipartite graphs that solely relies on the computation of $O(\frac{1}{\epsilon^{2}})$ maximal matchings in subgraphs of the input graph. Specifying the respective subgraphs, however, is slightly more involved, but can be done with communication cost $O\left(n\frac{1}{\epsilon}\log(\frac{1}{\epsilon})\right)$. Taking this into account, a $\mathsf{BB}$(k) model protocol with communication cost $O\left(\left(n\log n+n\frac{1}{\epsilon}\log(\frac{1}{\epsilon})\right)\cdot\frac{1}{\epsilon^{2}}\right)$ can be obtained.

We now discuss how the random order Greedy MIS algorithm can be implemented in the $\mathsf{BB}$(k) model with communication cost $O(n\operatorname{\mathrm{poly}}\log n)$. A similar implementation in the massively parallel computation and the congested clique models was previously discussed by Ghaffari et al. (Ghaffari et al., 2018). The key idea of this implementation, i.e., a residual sparsity property of the random order Greedy algorithm, goes back to the multi-pass correlation clustering streaming algorithm by Ahn et al. (Ahn et al., 2015) and have since been used at multiple occasions (Konrad, 2018; Gamlath et al., 2019).

The random order Greedy MIS algorithm proceeds as follows: First, the algorithm identifies a uniform random permutation $\pi:V\rightarrow[n]$, assigning each vertex a rank. Denote by $v_{i}$ the vertex with rank $i$. The algorithm processes the vertices $V$ in the order specified by $\pi$. When processing vertex $v_{i}$, the algorithm attempts to insert $v_{i}$ into an initially empty independent set $I$ if possible, i.e., if $I\cup\{v_{i}\}$ is an independent set.

To simulate this algorithm in the $\mathsf{BB}$(k) model, the $k$ parties first agree on a uniform random permutation $\pi$ using public randomness. The simulation then proceeds in $O(\log\log n)$ phases, where in phase $i$ Greedy is simulated on vertices $V_{i}:=\{v_{j}\ :\ k_{i-1}\leqslant j<k_{i}\}$, for

Denote by $I_{i}$ the independent set computed after phase $i$ (i.e., after having processed all vertices with ranks smaller than $k_{i}$), and let $I_{0}=\{\}$. In each phase $i$, the parties write the subgraph induced by vertices $V_{i}\setminus N(I_{i-1})$ onto the blackboard, where $N(I_{i-1})$ denotes the neighborhood of $I_{i-1}$. This information, together with $I_{i-1}$, then allows all parties to locally continue the simulation of Greedy on vertices $V_{i}$, resulting in independent set $I_{i}$. As proved by Ghaffari et al., the subgraph induced by vertices $V_{i}\setminus N(I_{i-1})$ has $O(n\operatorname{\mathrm{poly}}\log n)$ edges with high probability. Since the parties know $I_{i-1}$ from the local simulations of the previous phase, they know which of their edges are contained in subgraph $G[V_{i}\setminus N(I_{i-1})]$ and write all of these edges onto the blackboard.

After $O(\log\log n)$ phases, it can be seen that the graph induced by vertices with rank larger than $k_{O(\log\log n)}$ has $O(n\operatorname{\mathrm{poly}}\log n)$ edges. The parties then write this subgraph onto the blackboard, which allows all parties to complete their local simulations of Greedy.