Filed under: Uncategorized | Tags: distributed algorithms, security, theory

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.

Filed under: Uncategorized | Tags: distributed algorithms, education, game theory, theory

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.

Filed under: Uncategorized | Tags: algorithms, distributed algorithms, self-healing, students, theory

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: