Machinations


Zooming In
February 21, 2011, 11:07 pm
Filed under: Uncategorized | Tags: , ,

I enjoy collecting meta-level tricks for coming up with new research problems.  Two tricks I know of are “zooming out” and “zooming in”.  I think that “zooming out” is the more obvious trick: find several important problems that share some fundamental similarity and formulate a single abstract problem that allows for simultaneous progress in understanding all the particular problems.  Many big problems in complexity theory are of this type.

The other technique, “zooming in” seems to be just as important, but to be used much less frequently, perhaps because it’s harder to determine when it should be applied.  One of my most cited research results is on a problem that was devised using the “zooming in” technique: the problem of choosing a random peer in a large network.  The story behind this paper is that we wanted to solve some hard problem on peer-to-peer networks, and one part of our solution required as a subroutine an algorithm to choose a peer uniformly at random in the network.  Implementing this subroutine seemed like the easiest part of the problem and so we saved it to the end.  But then when it came time to solve it, we became more and more annoyed by the difficultly of the problem.  Finally we did a thorough literature search on this subproblem, which at first we thought would be the easiest part of the paper.  Not only didn’t we find any correct solutions in the literature, but we actually found several incorrect solutions.   At this point, we realized the problem was important and interesting in its own right, and we wrote an entire paper on just this one subproblem.

Today I wanted to highlight a recent nice example of the “zooming in” technique, in a ICDCS paper by my former student Maxwell Young.  This paper, “Practical Robust Communication in DHTs Tolerating a Byzantine Adversary”, by Maxwell Young, Aniket Kate, Ian Goldberg and Martin Karsten, is a systems paper that presents a clever algorithm for efficient and robust communication in a distributed hash table (DHT).  A DHT is  basically a distributed data structure that allows for efficient storage and lookup of content based on keywords.  The nice trick they use in this paper, is to formulate the research problem by “zooming in”.  Instead of designing yet another DHT from scratch that is robust to adversarial control of nodes, they assume that part of the problem is already solved: there is already a DHT that has the property that each “supernode” contains a majority of peers that are not controlled by an adversary (there are any number of papers that show how this property can be maintained).   They then focus only on the problem of routing most efficiently through such a DHT. To my knowledge, this is the first paper that focuses only on this important subproblem of robust communication in a DHT.  And if you take a look at the paper, you’ll see that the results they achieve are much better than other algorithms that have been proposed, as asides and perhaps without too much thought, in other papers for this problem.  While this paper focuses just on the empirical side of this problem, I think there are still many interesting open problems on the theoretical side.

 



Kinesthetic Learning for a Distributed Computing Class
June 10, 2010, 3:15 pm
Filed under: Uncategorized | Tags: , , ,

Suresh Venkatasubramanian at geomblog blogs recent about active learning modules for graduate algorithms. I’ve frequently used active learning in undergraduate classes but somehow have found it less effective for graduate classes.  However, just recently, I ran across a nice paper by Sivilotti and Pike that describes kinesthetic learning activities for a distributed algorithms class.  The basic idea is to have each student simulate a processor that is running a distributed algorithm.  Examples they discuss are non-deterministic sorting, parallel garbage collection, a stabilizing token ring, and stabilizing leader election.  I also think the ideas could be applied to more advanced/theoretical distributed algorithms.  A great thing about distributed computing is that it lends itself nicely to this sort of classroom activity.

I have not yet used these ideas in a graduate class.  However, I frequently using active learning in undergrad classes and the students seem to appreciate it.  I’ll probably try out some of the ideas in the next academic year.  I’m teaching a game theory class in the spring where I can use these types of activities – even perhaps for “hard” problems like e.g rational secret sharing, auctions, etc.



Amitabh
April 2, 2010, 8:04 pm
Filed under: Uncategorized | Tags: , , , ,

Congratulations to my student Dr. Amitabh Trehan who just defended his dissertation yesterday (on April Fool’s Day no less). Amitabh has done some very nice work on self-healing in networks, published in the last two PODC’s and in IPDPS. He’ll be doing a short post doc for several months with Valerie King at U. Victoria and then will be doing a year-long post doc with Shay Kutten at Technion. Congratulations Amitabh!!!

A one slide dissertation summary:



Consensus

Consensus[1] is arguably one of the most fundamental problem in distributed computing.  The basic idea of the problem is: n players each vote on one of two choices, and the players  want to hold an election to decide which choice “wins”.  The problem is made more interesting by the fact that there is no leader, i.e. no single player who everyone knows is trustworthy and can be counted on to tabulate all the votes accurately.

Here’s a more precise statement of the problem.  Each of n players starts with either a 0 or a 1 as input.  A certain fraction of the players (say 1/3) are bad, and will collude to thwart the remaining good players.  Unfortunately, the good players have no idea who the bad players are.  Our goal is to create an algorithm for the good players that ensures that

  • All good players output the same bit in the end
  • The bit output by all good players is the same as the input bit of at least one good player

At first, the second condition may seem ridiculously easy to satisfy and completely useless.  In fact, it’s ridiculously hard to satisfy and extremely useful.  To show the problem is hard, consider a naive algorithm where all players send out their bits to each other and then each player outputs the bit that it received from the majority of other players.  This algorithm fails because the bad guys can send different messages to different people.  In particular, when the vote is close, the bad guys can make one good guy commit to the bit 0 and another good guy commit to the bit 1.

The next thing I want to talk about is how useful this problem is.   First, the problem is broadly useful in the engineering sense of helping us build tools.  If you can solve consensus, you can solve the problem of how to build a system that is more robust than any of its components.  Think about it: each component votes on the outcome of a computation and then with consensus it’s easy to determine which outcome is decided by a plurality of the components (e.g. first everyone sends out their votes, then everyone calculates the majority vote, then everyone solves the consensus problem to commit to a majority vote.)   It’s not surprising then that solutions to the consensus problem have been used in all kinds of systems ranging from flight control, to data bases, to peer-to-peer; Google uses consensus in the Chubby system; Microsoft uses consensus in Farsite; most structured peer-to-peer systems (e.g. Tapestry, Oceanstore) use consensus in some way or another.  Any distributed system built with any pretension towards robustness that is not using consensus probably should be.

But that’s just the engineering side of things.  Consensus is useful because it allows us to study synchronization in complex systems.  How can systems like birds, bees, bacteria, markets come to a decision even when there is no leader.  We know they do it, and that they do it robustly, but exactly how do they do it and what is the trade-off they pay between robustness and the time and communication costs of doing it?  Studying upper and lower bounds on the consensus problem gives insight into these natural systems.  The study of how these agreement building processes, or quorum sensing, occur in nature has become quite popular lately, since they occur so pervasively.

Consensus is also useful because it helps us study fundamental properties of computation.  One of the first major result on consensus due to Fischer, Lynch and Patterson, in 1982, was that consensus is impossible for any deterministic algorithm with even one bad player (in the asynchronous communication model).  However, a follow up paper by Ben-Or showed that with a randomized algorithm, it was possible to solve this problem even with a constant fraction of bad players, albeit in exponential time.  This was a fundamental result giving some idea of how useful randomization can be for computation under an adversarial model.  As a grad student, I remember taking a class with Paul Beame telling us how impressed he was by what these two results said about the power of randomness when they first came out.  Cryptography was also shown to be useful for circumventing the Fischer, Lynch and Patterson result, and I’ve heard of several prominent cryptographers  who were first drawn to that area at the time because of its usefulness in solving consensus.

In the next week or two, I’ll go into some of the details of recent results on this problem that make use of randomness and cryptography.  Early randomized algorithms for consensus like Ben-Or’s used very clever tricks, but no heavy duty mathematical machinery.  More recent results, which run in polynomial time, make use of more modern tricks like the probabilistic method, expanders, extractors, samplers and connections with error-correcting codes, along with assorted cryptographic tricks.  I’ve been involved on the work using randomness, so I’ll probably start there.

[1] The consensus problem is also frequently referred to as the Byzantine agreement problem or simply agreement.  I prefer the name consensus, since it is more succinct and descriptive. While the research community has not yet reached a “consensus” on a single name for this problem, in recent years, the name consensus is being used most frequently.