In this post, I will discuss Distributed Verification and Hardness of Distributed Approximation, by Das Sarma and seven other authors. I enjoyed this paper for a couple reasons: first, it highlights a major difference between “traditional” computing and distributed computing; and, second, it puts forth a research program that seems to have a lot of promise. In a nutshell, the authors present a way to translate lower bounds in communication complexity into lower bounds in distributed verification and distributed approximation, so a straightforward technique is able to answer multiple open questions at one fell swoop.
Verification is harder than construction
We are used to NP-completeness results where verifying the accuracy of a witness at least appears to be much easier than constructing a witness. (“Is this set of vertices a -clique?” is easier to answer than “Produce a -clique” is to follow.) However, in a distributed setting, this intuition fails us. Consider the distributed computation of a spanning tree. At the end of the computation, each node in the network knows whether it is part of the spanning tree, and knows which of its edges are part of the spanning tree. This can be accomplished easily by running a breadth-first search on the graph, and terminating in rounds, where is the diameter of the graph (the longest minimum path between any two vertices). However, suppose the problem is one of verifying that a certain set of nodes and edges is indeed a minimum spanning tree. One result of this paper is that such verification requires at least rounds, where is the number of nodes in the network. So the time bound for verification is strictly greater than for construction.
From communication complexity to distributed computing
The basic idea of communication complexity is to bound the minimum number of bits two parties (Alice and Bob) need to exchange to compute a function, even if both parties have access to unlimited computational resources. One classic example of such a function is the set disjointness function (are the sets the two parties start out with disjoint, or do they share at least one element). The set disjointness function has high communication complexity, and the authors use this fact to obtain lower bounds to verification in distributed computing.
How to move from communication complexity to time complexity in a distributed system? The authors define a class of networks, such that there are two labeled nodes on either side of the network. They show that if the two labeled nodes can compute a function fast with high probability, then Alice and Bob can compute the same function fast with high probability. Turning this around, of course, if Alice and Bob provably have no fast algorithm for a function, then the nodes on the special network don’t either.
One of these special networks encodes on its “left side” edge set the bit string that Alice would start with, and, on its “right side” edge set the bit string that Bob would start with. Then, beginning at a node halfway between the “Alice” and “Bob” nodes, one decides how to traverse the network to get information to “Alice” and “Bob.” Since there is a lower bound on the number of bits required to transfer back and forth in the original communication complexity problem, there is a lower limit on the number of rounds needed to get the right information through the network to “Alice” and “Bob.”
What I mean by the edge sets encoding the bit strings is that the edges chosen comprise the subgraph that we want to verify has a particular property. So the lower bound on communication complexity becomes a lower bound on distributed verification. More precisely, the network version of the set disjointness problem has a time lower bound of , where is the upper bound on the number of bits of a single message. The authors then use already-known reduction techniques from the data stream literature to reduce the distributed set disjointness problem to questions like, “Is a spanning connected subraph?” and they show the answers to such questions require communication rounds to be answered with high probability.
There are many other results in this paper, but I will skip them. I hope this high-level sketch helps people who want to read it. I found it helpful for my own thinking to write this up.