2011 September « Machinations

SODA 2012

September 27, 2011, 3:04 pm
Filed under: Uncategorized | Tags: theory

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.

[1] I lived in Kyoto for 3 fun months while an undergrad at Stanford.

September 20, 2011, 3:28 pm
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 ${f}$ that can be computed with a circuit of ${n}$ regular gates. You want to construct a new circuit with the smallest number of noisy gates that computes ${f}$ correctly with probability greater than ${1/2}$ . These new noisy gates each fail independently with some small probability ${\epsilon}$ 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 ${n}$ gates without noise, but which require ${\Omega(n \log n)}$ noisy gates. In particular, they show that this is true if ${f}$ 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 ${\delta}$ , 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 ${\Delta}$ be the maximum number of input wires for any gate. Then for any ${\delta \in [0, \epsilon/\Delta]}$ 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 ${\epsilon}$ . 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 ${n}$ inputs to the to our exclusive-or function ${f}$ , and we let ${X_{1}, X_{2}, \ldots, X_{n}}$ be these inputs. For the purposes of the lower bound, we’ll assume that each ${X_{i}}$ is an independent random variable that is ${1}$ with probability ${1/2}$ and ${0}$ 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 ${\delta}$ ).

For the ${i}$ -th input bit, we’ll let ${m_{i}}$ be the number of wires that are connected directly to that input bit, and hence carry the value ${X_{i}}$ 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 ${X_{i}}$ . Not surprisingly, it is possible to prove (as the paper does) that Maximum Likelihood way to estimate ${X_{i}}$ is to take the majority bit over all the ${m_{i}}$ wires that are connected to input ${X_{i}}$ . We’ll let ${Z_{i}}$ be an indicator r.v. that is ${1}$ iff the Maximum Likelihood estimate for ${X_{i}}$ is wrong. Note that ${Pr(Z_{i} = 1) \geq \delta^{m_{i}}}$ , since if every wire that carries that value ${X_{i}}$ is faulty, then clearly the circuit will use the wrong value.

Next, note that the probability that the noisy circuit fails is just ${Pr(Z_{1} \oplus \cdots \oplus Z_{n} = 1)}$ . So now we have a cute probability problem: assume you’re give ${n}$ independent indicator random variables, you know the probability that each of them is ${1}$ , and you want to compute the probability that their exclusive-or is ${1}$ . The next lemma solves this problem with the help of generating functions.

Lemma 1

$\displaystyle 1 - 2 Pr(Z_{1} \oplus \cdots \oplus Z_{n} = 1) = \prod_{i=1}^{n} (1 - 2 Pr(Z_{i} = 1))$

Proof: Let ${\phi_{i}(t) = E(t^{Z_{i}})}$ be the generating function for ${Z_{i}}$ . Note that ${\phi_{i}(t) = 1- Pr(Z_{i}= 1) + t Pr(Z_{i} = 1)}$ . Now let ${Z = \sum_{i=1} ^{n} Z_{i}}$ and let ${\psi(t) = E(t^{Z})}$ . Now comes the clever part: note that ${E((1^{Z} - (-1)^{Z})/2) = Pr(Z_{1} \oplus \cdots \oplus Z_{n} = 1)}$ . This is true since ${1^{Z}}$ is always ${1}$ and ${-1^{Z}}$ is ${1}$ if ${Z}$ is even and ${-1}$ if ${Z}$ is odd.

But by linearity of expectation, ${Pr(Z_{1} \oplus \cdots \oplus Z_{n} = 1) = E((1^{Z} - (-1)^{Z})/2) = (\psi(1) - \psi(-1)) / 2}$ . Next, note that ${\psi(t) = \prod_{i=1}^{n} \phi_{i}(t)}$ since the ${Z_{i}}$ are independent. Thus, ${\psi(1) = 1}$ and ${\psi(-1) = 1-2 Pr(Z_{i} = 1)}$ . This completes the proof. $\Box$

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 ${n}$ numbers, ${x_{1}, x_{2}, \ldots x_{n}}$ , it holds that ${(1/n) \sum_{i=1}^{n} x_{i} \geq \sqrt[n] {\prod_{i=1}^{n} x_{i}}}$ .

Lemma 2 ${ \sum_{i=1}^{n} m_{i}}$ is ${\Omega(n \log n) }$

Proof: Let ${p<1/2}$ be the probability of error for the noisy circuit. By assumption, ${Pr(Z_{1} \oplus \cdots \oplus Z_{n} = 1) < p}$ . Using Lemma~1 and our bound on ${Pr(Z_{i} = 1)}$ , we have that

$\displaystyle 1-2p \leq \prod_{i=1}^{n} (1 - 2 \delta^{m_{i}})$

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

$\displaystyle 1-2p \leq \left(1/n \sum_{i=1}^{n} (1 - 2 \delta^{m_{i}})\right)^{n} = \left(1 - 2/n \sum_{i=1}^{n} \delta^{m_{i}}\right)^{n}$

Again using the inequality between arithmetic and geometric means (now on the term that is being subtracted) and the fact that ${1-x \leq e^{-x}}$ , we get:

$\displaystyle 1-2p \leq \left( 1-2\delta^{1/n \sum_{i=1}^{n} m_{i}} \right)^{n} \leq \textrm{exp}(-2n\delta^{1/n \sum_{i=1}^{n} m_{i}})$

Isolating the ${\sum_{i=1}^{n} m_{i}}$ term in the above inequality gives us that

$\displaystyle \sum_{i=1}^{n} m_{i} \geq n \frac{\ln (2n) - \ln \ln (1/(1-2p))}{\ln (1/\delta)}$

Since ${\delta}$ is a constant depending only on ${\epsilon}$ and since ${p<1/2}$ , the above inequality completes the proof. $\Box$

Finally, we note that since each gate is assumed to have constant fan in, if the number of wires is ${\Omega(n \log n)}$ , it follows that the number of gates in the noisy circuit must also be ${\Omega(n \log n)}$ . 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!

2 Comments

SODA accepted papers

September 14, 2011, 3:14 am
Filed under: Uncategorized | Tags: distributed computing, SODA, theory

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

1 Comment

On Networks of Noisy Gates

September 12, 2011, 6:24 pm
Filed under: Uncategorized | Tags: expanders, networks, robustness, theory

In 1952, Von Neumann proposed the following problem. You are given a function f that can be computed with a circuit of n gates. You have to build a new circuit to compute f, but all the gates in your new circuit are unreliable. In particular, each new gate fails independently with some small probability epsilon, and when a gate fails, it computes the NOT of what it should compute. What is the smallest number of gates you need in order to compute f with a probability of error strictly less than 1/2?

Turns out that in general you need Theta(n log n) gates. The upper bound was shown by Von Neumann, and the lower bound for the exclusive-or function was first proved by Pippenger, Stamoulis and Tsitsiklis (after a previous incorrect attempt by others).

Today I want to talk about the upper bound result. You might think this is pretty easy – just duplicate each gate log n times, do majority filtering, and use Chernoff bounds to show that the majority output will be correct. Unfortunately, duplication and majority filtering alone fails since the fraction of faulty wires will increase by a constant with each level of the circuit.

To fix this, you need a sampler (aka a concentrator). A sampler is just a special type of bipartite graph. In the simplest case, there are the same number of nodes on the top as on the bottom and the graph is d-regular for some constant d. The very useful property of a sampler is that it reduces error in the following sense. If some fraction x of the nodes in the top are “bad”, then the fraction of nodes on the bottom that have a majority of bad neighbors is less than x/4. We can make the denominator an arbitrary large constant by increasing d, but 4 will suffice for our purposes. For more about samplers, including how to construct them and other applications, see Section 3.2.1 of our Breaking the O(n^2) Bit Barrier paper.

Once, you’ve got a sampler, Von Neumann’s construction is pretty easy and is illustrated in the figure below. In the upper right corner of the figure is a noiseless gate G with two input wires and a single output wire. The large circuit to the left replicates this functionality with noisy gates. In the large circuit, in place of the two input wires, we have two “cables”, each consisting of Theta(log n) wires. In place of G, we have Theta(log n) replicas of G. One wire from each cable goes into each of these replicas. Below this, we have wires connected via a sampler to a bunch of simple circuits (“Maj”) that simply compute the majority of their inputs.

These majority circuits (Maj in the figure) are themselves also noisy. However, since they have constant degree input, its not hard to construct them so that they fail only with constant probability.

The names “Executive Organ” and “Restoring Organ” used in the figure are Von Neumann’s original terminology. A bit colorful perhaps, but who are we to change it?

The simple analysis of this circuit is illustrated below. Adjacent to each cable is now an upper bound on the fraction of wires in the cable whose output is faulty. Each of these upper bounds holds with high probability (whp), i.e. a probability of error that is polynomially small in n). Adjacent to each gate is the probability that the gate is faulty.

We assume inductively that the fraction of bad wires in each of the input cables is no more than \theta for some fixed constant \theta. The first observation is that the fraction of faulty wires coming out of the gates G is then no more than 2\theta + 2\epsilon. To see this, note that, whp, the fraction of gates that fails is no more than 2\epsilon by Chernoff bounds. In the worst case, each faulty gate and each faulty input wire causes its own separate faulty output, which gives us 2\theta + 2\epsilon faulty wires.

Next notice that by the properties of the sampler, if all the Maj circuits are correct, we would have a factor of 4 decrease in the fraction of faulty wires leaving these, so that the fraction of faulty output wires would be only 1/2(\theta + \epsilon). But again by Chernoff bounds, whp, at most 2\epsilon of the Maj circuits will be faulty. Thus we have at most a 1/2(\theta + \epsilon) + 2\epsilon fraction of faulty wires coming out and this last term is no more than \theta for \theta large enough but depending only on \epsilon.

The final thing to note is that the fraction of faulty wires on the final output cable is the same as the fraction of faulty wires on the two input cables. Thus, the fraction of faulty wires does not increase with the depth of the circuit!

This is a remarkable result, particularly since it dates back to 1956! I’d argue that the Von Neumann fault model continues to have the same sway over CS as the Von Neumann architecture. Our fault models still generally assume that a linear number of processing elements are made faulty, and we seek to tolerate these faults while minimizing resource costs with respect to computation in a world without faults. Unfortunately, a resource blowup of a logarithmic factor seems to be completely intolerable to practitioners – especially if in the common case, there are no faults at all! This has been a barrier to use of these types of results.

How can we go beyond this model in order to get more practical robustness? Should we use properties of modern computational networks, i.e. their ability to be reconfigured and to allow for feedback? Should we use a more modern type of competitive analysis: i.e. assume an adversary with a fixed but unknown budget b of processing units that it can corrupt, and then demand that our resource blowup be competitive with b instead of n? Should we try to get improved results for specialized classes of functions, rather than try to attack the general problem for all types of functions?

	Jared on Self-healing of Byzantine…
	Max on Self-healing of Byzantine…
	amitabht on Self-healing of Byzantine…
	George Saad on Self-healing of Byzantine…
	Jared on Puzzle 2

Machinations

Archives

Recent Comments

Top Posts

Top Clicks

Tags

Blog Stats

Follow Blog via Email

Follow “Machinations”