The Coolest Problem You’ve Never Heard Of
April 20, 2015, 6:32 pm
Filed under: Uncategorized | Tags: , , ,

How do you compute over a noisy channel?   Say Alice and Bob want to run a distributed algorithm, but they can only communicate over a channel where each bit is flipped either stochastically or adversarially.  What is the smallest number of bits they must send in order to obtain the correct output of the algorithm, with high probability?  This general problem is called Interactive Communication, or sometimes Interactive Coding/Computation – let’s use IC for short.  It doesn’t take much imagination to think of applications of IC:  enabling sensor nodes to compute a function on their inputs in a noisy environment; designing reliable algorithms for natural algorithms [1]; and designing attack-resistant algorithms [2], just as some examples.

Wait, you may be thinking, isn’t this problem solved by error correcting codes?  No – the bits sent in the distributed algorithm may be determined only one at a time, in a dynamic manner.  Even for stochastic noise, if we naively encode each bit sent, in order to get a union bound ensuring the probability of any decoding error is small, we’ll need logarithmic blowup for each bit.  We can do better.

In fact, in the first paper on this problem, Coding for Interactive Communication, Leonard Schulman described an algorithm that requires only constant blowup, even when a constant fraction of the bits on the channel are flipped adversarially.  Schulman’s algorithm was based on a new type of code, tree codes, designed specifically for interactive communication. After this paper was published in 1996, subsequent work  focused on improving the error tolerance of Schulman’s algorithm (i.e. tolerating a larger constant fraction of errors); tuning the communication blowup to the (known) error rate; and considering the situation where the computation occurs over more than 2 parties.  See the survey paper Coding for interactive computation: progress and challenges (especially Sections 3 and 4) for details.

I’ll note here that in a sense all of information theory can be though of as a subset of IC. In particular, information theory considers “only” the class of distributed algorithms where Alice has an input that she wants to send to Bob.  In IC, we need to handle all possible distributed  algorithms, and so in a way, it’s pretty amazing that a constant adversarial noise rate can even be tolerated.

A very recent breakthrough in IC occurred in FOCS 2014, where Bernhard Haeupler in the paper Interactive Channel Capacity Revisited, made huge progress on the problem of tuning the communication blowup to a known error rate.  In particular, he described an algorithm that given a fixed and known adversarial noise rate \epsilon, achieves a communication blowup as a function of \epsilon that is conjectured to be optimal.

So what if \epsilon is not known in advance?  I’m going to end this post with a short advertisement for a recent paper with some collaborators of mine that begins to address that problem.  The paper is Interactive Communication with Unknown Noise Rate, with Varsha Dani, Mahnush Movahedi, and Maxwell Young that will be in this upcoming ICALP.  This is the first paper I’ve written about IC, and I hope it won’t be the last.  In fact, I’d like to see more people in the distributed computing community consider the problem.  In particular, it’d be nice to make progress on the (currently very hard) problem of somehow generalizing results to more than 2 parties.

[1]  For example, see this paper for a closely related problem: Breathe before Speaking: Efficient Information Dissemination Despite Noisy, Limited and Anonymous Communication

[2] This last domain is particularly interesting to me.  An obvious connection is attacks on communication channels.  A less-obvious connection is attacks on nodes.  If communication from each node is bounded, as is increasingly common for algorithms on large networks, there may be a fairly tight connection between attacks on communication channels and attacks on nodes.  Thus, there may be connections to attacks like Byzantine faults.

Leave a Comment so far
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: