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.
Great post today on the Tomorrows-Professor Mailing list – the advice is clearly applicable to any mathematical or scientific discipline. It took me surprisingly many years to realize this secret, but now it is the first thing I think about in my research. I’m including the post below in its entirety.
The Astonishing Secret to Getting Jobs, Grants, Papers, and Happiness in Biomedical Research
I didn’t notice at the time, but there was a point in my life when I more-or-less stopped asking successful scientists how they did it, and someone asked me. And while I offer neither evidence nor assertion that I am successful (indeed, I think I have a great way to go), the fact that I somehow can continue to do this, and occasionally be asked about it, might be regarded as a kind of success. There are some of us who mark success by tenure (a concept that serves as high comedy among my friends who are in business), “impact factor” (ditto), or the recognition of our peers (which is a wonderful thing, but not why I embarked on this career). But I’m going to go with the first definition: getting to do this thing we do, biomedical research, for now and for the foreseeable future.
But like many of my closest colleagues, for a long time I felt like the farm boy Wesley, who was kidnapped by the Dread Pirate Roberts from the movie “The Princess Bride” (which, if you haven’t seen, will be far more useful for your scientific career than anything I can offer here). Every day, Roberts would say “Goodnight, Wesley, I’ll probably kill you in the morning.” Wesley studied hard at swordsmanship and other piracy skills, and one day, when his captor retired, Wesley was given the ship and the title, and became the Dread Pirate Roberts himself. More or less, this is what happened to me, without the pirate part, and my mandate here is to try to tell those of you who may be looking for some success yourselves how you might do this, too.
So here goes. If you are committed to this path, and want papers, grants, and employment for now and tomorrow, I can sum up in two words what it is that is asked of you, and really, everyone who works in science: Astonish us. That’s it. (There is a maxim that says, “If it fits on a bumper sticker, it isn’t true.” While I generally ascribe to this, it does not apply in this particular case. That said, no, I do not have this on my car’s bumper. It might encourage the wrong sort of driver.)
Really. Look at it this way: When I have a great stack of grants to review, I know that only one in ten or so will likely be “F’ed”. (On U.S. study sections, we are not allowed to say the word “Funded.” Somewhat foolishly, we say “F’ed,” and we know what it means. Such is the way of government. It also lightens the mood when we are reviewing grants. Of course, most proposals will be “F’ed,” which in this context means “Not Funded.”) But if in an astonishing proposal the data look compelling, if the approaches are sound, and if the experiments will most likely work, and in so doing possibly change my thinking about the universe (okay, my little corner of the universe) then it will move to the top of the stack. It has to. I have to do whatever I can to make sure it gets done.
I hear a line of advice all the time that I can confidently tell you is nonsense. It goes like this: “In order to get your grant supported, it has to be letter perfect, with absolutely no mistakes, and every experiment you propose has to already be done.” Don’t believe this, it just ain’t so. We get this advice from folks who don’t get their grants supported (and hey, I’ve been there), who see nit-picky reviews that point out every little problem, no matter how trivial. Hence the advice. But this misses the subtext. A favored application has astonished the reviewers, who can be very forgiving about mistakes, chancy experiments, and the occasional missing control if they are convinced that the work has a real chance of affecting how we think about something important.
So okay, you have to astonish us. And if you do this with what you propose, and if you follow through, great papers and a promising career will come in time. But how can you do this? Most likely, nothing in your training has ever prepared you for this challenge. Indeed, it sounds impossible. But here’s the thing: Most of you, reading this, already know the answer.
Sometime in your past, you read, saw, or heard something about the universe that astonished you, so much so that you simply needed to know more about it. And the more you learned, the more astonished you became. And this approach to knowing something amazing, which could not have been known by reason or belief or any other method, convinced you that however astonishing it all is, it is as close to “true” as we can get, in a way that satisfied you. Many people love to be astonished by all sorts of means, but this path to astonishment worked for you, and hopefully still does. It’s why you became a scientist.
The rest is relatively easy. The trick is for us to remember to apply this to our own research: Which avenues of investigation will lead us, not only to information that may be useful, but to something remarkable? Sure, much of what we do is not surprising, amazing, or astonishing, but has to be done anyway. But go beyond the drudgery? Why do we need to spend time, energy, and resources to answer a question? Somewhere at the end of the Yellow Brick Road of your efforts there must be something wondrous you can envision. If not, follow another road.
This is not salesmanship, branding, or trickery; it is not “grantsmanship.” This is at the most fundamental core of what we do, as humans, following our evolutionarily selected impulses to explore our world, in this case with the technical and conceptual tools available to us as scientists. And there is a bonus as well. When we actually achieve our own moments of astonishment in our own research, however fleeting, these represent our real success. The sort of success we got into this to attain. The other kinds will follow, and we may not even notice.
* Douglas R. Green studies cell death and survival at the Department of Immunology, St. Jude Children’s Research Hospital, Memphis, TN. He recently wrote “Stress in biomedical research: Six impossible things,” Mol Cell, 40:176-178, 2010. He is also the author of Means to an End: Apoptosis and Other Cell Death Mechanisms, available from Cold Spring Harbor Press. He is a member of the Faculty of Cell Biology at F1000. For his latest evaluations, click here.