Some quick info for people going to Kyoto for SODA 2012:

- Hipmunk is a very useful tool for comparing flights based on both price and flight duration. Great for finding inexpensive international flights that don’t involve 5 hour layovers or a large number of stops.
- Kyoto is an interesting and beautiful city [1]. Matsuo Basho wrote:
*“Even in Kyoto, I long for Kyoto”.*Wikitravel has a pretty good basic web page on Kyoto. - If you have an extra day or two after the conference, a ryokan (a traditional Japanese inn) is a great place to spend the night.

Filed under: Uncategorized | Tags: distributed computing, papers, reliability, theory

In today’s post, I want to focus on some of the highlights of the lower bound that I mentioned last time on the “Networks of Noisy Gates“ problem. Recall that, in this problem, you are given a function that can be computed with a circuit of regular gates. You want to construct a new circuit with the smallest number of noisy gates that computes correctly with probability greater than . These new noisy gates each fail independently with some small probability and when they fail, they produce the complement of their correct output.

The result I want to talk about today is the lower bound by Pippenger, Stamoulis and Tsitsiklis which shows that there are some functions that can be computed with gates without noise, but which require noisy gates. In particular, they show that this is true if is the exclusive or function.

The first part of their lower bound is a result that shows a new model of failure where wires can also fail can be made equivalent to the old model of failure where only gates can fail. In particular, in the new model, each wire fails with some probability , independently of all other wires and gates, and failure of a wire results in transmitting the complement of the bit that is sent down that wire.

Lemma 3.1 of the paper “Lower Bound for the Redundancy of Self-correcting Arrangements of Unreliable Functional Elements” by Dobrushin and Ortyukov shows the following. Let be the maximum number of input wires for any gate. Then for any and for any set of inputs to a gate, there exists a vector of malfunction probabilities on the gate such that the probability that the gate fails to produce the correct output is exactly . Essentially this shows that, the new model where we have a small probability of failure on both wires and gates is stochastically equivalent to the old model where we have a larger probability of error just on the gates.

Now we assume we have inputs to the to our exclusive-or function , and we let be these inputs. For the purposes of the lower bound, we’ll assume that each is an independent random variable that is with probability and otherwise. Now for this lower bound, we’re going to be very generous to the noisy circuit. We’re going to assume that 1) no gate ever fails and 2) the only wires that can fail are those that are directly connected to some input bit ( each of these wires fails independently with probability ).

For the -th input bit, we’ll let be the number of wires that are connected directly to that input bit, and hence carry the value if they are not faulty. Now in the backend of the circuit, which is computing the exclusive-or of the input bits, there needs to be some estimate for each value of . Not surprisingly, it is possible to prove (as the paper does) that Maximum Likelihood way to estimate is to take the majority bit over all the wires that are connected to input . We’ll let be an indicator r.v. that is iff the Maximum Likelihood estimate for is wrong. Note that , since if *every* wire that carries that value is faulty, then clearly the circuit will use the wrong value.

Next, note that the probability that the noisy circuit fails is just . So now we have a cute probability problem: assume you’re give independent indicator random variables, you know the probability that each of them is , and you want to compute the probability that their exclusive-or is . The next lemma solves this problem with the help of generating functions.

*Proof:* Let be the generating function for . Note that . Now let and let . Now comes the clever part: note that . This is true since is always and is if is even and if is odd.

But by linearity of expectation, . Next, note that since the are independent. Thus, and . This completes the proof.

The remainder of the proof for the lower bound is just algebra. We’ll make use of the inequality between arithmetic and geometric means, which states that for any set of numbers, , it holds that .

Lemma 2is

*Proof:* Let be the probability of error for the noisy circuit. By assumption, . Using Lemma~1 and our bound on , we have that

Now using the inequality between arithmetic and geometric means, we have that

Again using the inequality between arithmetic and geometric means (now on the term that is being subtracted) and the fact that , we get:

Isolating the term in the above inequality gives us that

Since is a constant depending only on and since , the above inequality completes the proof.

Finally, we note that since each gate is assumed to have constant fan in, if the number of wires is , it follows that the number of gates in the noisy circuit must also be . That basically completes the proof of the lower bound. The interesting thing is that the only difficulty we exploited is the difficulty of estimating the input values in the situation where the wires may be faulty!

As has already been pointed out in several blogs, accepted papers for SODA are now up on the web. I’m on the program committee this year so can tell war stories about reviewing 53 papers over several weeks, but that’s another blog post. For now, I wanted to list some of the papers that I think will be of interest to the distributed computing community:

Gathering despite mischief Yoann Dieudonne, Andrzej Pelc and David Pele Networks Cannot Compute Their Diameter in Sublinear Time Silvio Frischknecht, Stephan Holzer and Roger Wattenhofer Information Dissemination via Random Walks in d-Dimensional Space Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun and Yajun Wang Rumor Spreading and Vertex Expansion George Giakkoupis and Thomas Sauerwald Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks John Augustine, Gopal Pandurangan, Peter Robinson and Eli Upfal Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy Jeff Phillips, Elad Verbin and Qin Zhan SINR Diagram with Interference Cancellation Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter and David Peleg Ultra-Fast Rumor Spreading in Social Networks Nikolaos Fountoulakis, Konstantinos Panagiotou and Thomas Sauerwald A Little Advice Can Be Very Helpful Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen and Toniann Pitassi Physarum Can Compute Shortest Paths Vincenzo Bonifaci, Kurt Mehlhorn and Girish Varma Parallelism and Time in Hierarchical Self-Assembly Ho-Lin Chen and David Doty

Very interesting article: Profiler at the Cellular Level about building a diagnostic biological computing network to detect cancer cells in humans. I’ve seen many talks on biocomputing that have proposed cancer detection as a motivating problem. However, this is the first time I’ve seen researchers directly attacking this problem.

From what I understand about this research area, reliability is still a major problem. In particular, biological gates are significantly less reliable than silicon gates, and it’s unclear how to best improve reliability in the case where large biological circuits are needed. This might lead to some very interesting problems in network reliability.