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.
Leave a Comment so far
Leave a comment