I haven’t been posting in a while because I’ve been busy with preparing NSF grant proposals (which have shifted their deadlines this year from spring to December). In the interest of getting out a post (and procrastinating), I’m going to write today about my great passion as a researcher: grant writing. Seriously, I do sometimes enjoy the opportunity to plan out a research agenda for the next 3-5 years, and always the proposals I write do inform the research I will do in the future. Also, so far I’ve also been really lucky with grants, with a hit rate of about 60% (we’ll see how it goes this year now that we have a toddler around the house). When your grants are funded, the grant writing process is much more fun!
Here are some of the tricks that I’ve learned for good grants. Mostly these are from my experiences with NSF grants but they have been useful for other agencies. I’d love to hear about some other ideas in the comments section.
The Introduction:
- Nail Motivation: Start with the problem you are trying to solve. Show that solving this problem has big implications, hopefully outside your own narrow area of work; and that your research will take significant steps towards solving the problem
- Nail Novelty: What is it about your approach that will cause you to succeed where others have failed? What unique ideas/tools/techniques do you bring to the problem?
- Expose a gap: As early as possible in the proposal, describe a gap in current research
- Don’t repeat: Don’t repeat text from the grant summary in the intro of your grant! This risks starting a bad precedent of the reader skipping over parts of your grant.
- Pull in the reader. Write a first sentence for both the summary and intro that is controversial, asks an interesting question, evokes strong emotions (hopefully not disgust
, etc.
The body:
- Less is More: Don’t tack on ideas or problems that you don’t really understand. The reviewers will uncover your ignorance and your grant will be skewered. The main constraint on conveying ideas is not the page length, but rather reviewers time. Expect a reviewer to spend about 30 minutes on your grant. You can really only get across a couple of clear ideas in this time. I know this from experience – whole sections of my grants have been misunderstood by reviewers in the past because I tried to cram too much in. Make it clear what the grant will not cover as well as what it will cover.
- Pictures are crucial: Spend as much time putting in 2-3 useful figures as you would writing a section of the grant
- Related Work is crucial: You’re proposal should be like an exciting conversation with the research community. Thread related work throughout your proposal – be generous with praise for great ideas, and make it clear how your efforts fit into the broader scheme. If you make the related work look exciting, your own research will look more exciting. Don’t miss anything that is remotely relevant to your work. A common way to have a grant shot down is a review like: “This proposal ignores results from the work of researcher X”.
- Technical depth: a portion of your proposal (maybe a third?) can and should be addressed to the experts. This is the place to include proofs, equations and enough technical details to convince the experts you have a good idea.
- Try to give something to the reader: teach the reader something new, include an interesting story or analogy, describe a cool problem. The reader will appreciate anything that breaks the monotony of reading grant proposals.
Some ideas about the process:
- Give a talk: I have found it useful to give a talk on preliminary results and future ideas as part of the proposal writing process. It works well to do this for both an expert audience and a non-expert audience. See what questions and ideas you get and use these to improve the proposal.
- Become your own worse enemy: you absolutely need to anticipate the 2 or 3 most devastating criticisms of your grant and then address those in the proposal
- Get feedback: Get an expert and a non-expert to spend half an hour with the grant and give quick feedback,
- Be intellectually mature: Don’t pretend you’ll solve every problem. Give credit where it is due. Be realistic about the research time line and the limitations of your technique.
- Try to write an hour a day on the grant to keep up momentum.
- Develop a style: I like to use a sort of dialect style where I describe problems and then solutions, or questions and then answers. This usually determines the broad outline of my proposal. However, there are many different writing styles and you should figure out what works best for you.
Obligatory Albuquerque Photo: Light Snow Today!
We’re hiring for one tenure track Assistant Professor position at the University of New Mexico. From the ad: “We seek applicants across computer science, including but not limited to large scale data systems, networks, software design and engineering, graphics and visualization, and AI and adaptive systems.” More details are available here.
Filed under: Uncategorized | Tags: algorithms, data streams, game theory, greed, local, mapreduce, theory
We just recently finished talking about greedy algorithms in my graduate algorithms class. In the past few months, I’ve developed a new appreciation for greed. Part of this is due to a discussion with Alan Borodin at a recent workshop, who made a good case for greediness as a stand-in for simplicity. Anyone working in algorithms will agree that simple algorithms are better; even more so in the area of distributed computing, where even simple algorithms can be notoriously difficult to implement. Unfortunately, it’s hard to improve what you can’t measure, and so there is a real need for good measures of algorithmic simplicity. This makes me think of several important techniques in algorithm design and how these might intersect with the notion of simplicity.
- Local algorithms: In distributed computing, local algorithms are those that run in time independent of the network size – i.e. each node in the network only receives information from its local neighborhood. Clearly, these types of algorithms are more simple than algorithms that require information to be exchanged over long distances in the network. Approximate edge coloring of graphs and some resource allocation problems are amenable to this approach. See the two great papers: What can be computed locally? by Naor and Stockmeyer and What cannot be computed locally by Kuhn, Moscibroda and Wattenhoffer for more on this area.
- Data streams: Algorithms that use little space are likely to be simple. Data stream algorithms use very little space (or more specifically the amount of space used is very small compared to the input size). While the analysis for many of these algorithms can be quite sophisticated, the algorithms themselves can usually be described in less than a quarter of a page of pseudo-code. Muthukrishnan’s book is a great resource in this area (plus it is freely available here). Recently, there has been a lot of interest in applying the data stream model in a distributed setting. See for example the Massive, Unordered Data (MUD) model, which tries to capture the approach of systems like Mapreduce.
- Greedy algorithms : Many of us are familiar with several algorithms of this type. Perhaps Kruskall’s algorithm is the most frequently used greedy algorithm that is always correct. Of course, there are many, many heuristics that are greedy that are not guaranteed to be correct. I wonder what are the most frequently used greedy approximation algorithms. Nothing comes to mind except for the greedy set cover algorithm or greedy approximation algorithms for maximizing submodular functions.
- “Selfish” algorithms: This is a phrase I just made up to describe distributed algorithms that require each node to behave selfishly. In particular, these are problems for which 1) the social welfare in any Nash equilibria is close to the optimal social welfare, and 2) the players can quickly converge to a Nash by following a locally optimal strategy. There is a lot of interest in these types of algorithms in the distributed computing community right now, partially, I think, because of the great fact that they are simple to describe and implement. Selfish algorithms are also simple in the sense that they may arise naturally when large groups of agents get together; in some sense, the algorithmic engineer is (at least partially) removed from the picture.
Are there other ways of formulating problems that ensure “simple” algorithms? Perhaps you, dear reader, can help me flesh out this list.
When I first started as a professor, I felt that what students needed to do well in a class, above all else, was precise, error-free lectures, and lot’s of practice doing problems. Based on this ideas, I did most of my lectures from slides that I had very carefully prepared before hand, and gave the class lots and lots of problems to solve. This actually worked pretty well for a while – I got great feedback from students, was nominated for some teaching awards, and enjoyed the experience.
However, eventually I realized that my lectures were not as exciting as they could be. I read some articles on Tomorrows Professor listserv, that bemoaned the use of pre-prepared slides. They claimed that extensive use of slides makes lectures completely predictable and unresponsive. This semester, as an experiment, I stopped using slides, or even lecture notes of any kind. I memorize enough of the lecture so that I can be sure to use terminology that is reasonably close to the textbook and to the notes I’ve posted from previous years of the class.
How have things changed? I find teaching a more exciting and sometimes scary activity. Also, it’s easier for me to respond to feedback from the class as a whole about e.g. whether it’s worthwhile to go over an example of a particular concept. When a student asks an interesting question, I definitely spend more time than I used to on exploring the answer in depth. For me, at least, the lectures are a lot more fun and challenging. From the feedback I’m getting from students so far, they also seem to be more engaged. Do I make more mistakes in lecture? Definitely. However, I feel that I’m slowly getting better at checking things on the fly and am making fewer mistakes now than when I started this.
How has this changed my teaching philosophy? I realize now that a big part of education is inspiration, motivation, and a kind of educational “entertainment”. I also realize that it’s just much more engrossing and memorable to watch someone walk carefully across a rope in the air, than to trudge across a line on the floor that was drawn before the performance even began!
Filed under: Uncategorized | Tags: Akamai, Bittorrent, churn, cloud computing, IPDPS, peer-to-peer, secret sharing, Skype, Sybil attack, theory, Vanish
Maxwell Young and I were talking the other day about the ups and downs of research in peer-to-peer systems. In 2002, when I got my PhD, I and everyone I knew at UW, felt that the popularity of p2p research was at a crescendo, and would quickly taper off in a year or two. However, this morning, seven years later, I’m reviewing IPDPS submissions, and I see that about 20% of the papers are on p2p (or their close relative overlay networks). What’s going on?
Partially, I think the interest in academic circles comes from the fact that p2p research allows us to study what happens when there is no leader. There are many challenging and fun problems in designing distributed systems that work when all components of the system are equal; that is, equal in terms of resources available, and also equal in the sense that all members of the system both use the system, and contribute to the system. Maybe p2p thinking suits the egalitarian bent of academics? Maybe it comes from a desire to imitate natural systems like ants and bees?
However, a perennial question is: are there legitimate uses of p2p systems? Isn’t the trend currently in the opposite direction, with cloud computing promising that someday networks will consist of mindless clients on one side, and computationally powerful servers on the other. In such a situation, will there be much need for direct communication between the clients? It’s hard for me, at least, to predict where these trends will eventually play out. However, I would not be surprised if both the p2p extreme and the weak client, powerful server extreme continue to exist side-by-side for a long time to come.
I did want to try to list some potential legitimate uses of p2p that I have heard about recently below. I’d love to hear about others, or arguments for or against the continued existence of p2p. Here’s are some of the big system (or ideas for systems) that I know about now.
- Vanish: A system that prevents archiving of sensitive data. In other words, Vanish attempts to enable that data like private email exchanges, photos, or messages can be given a deadline after which they simply can no longer be reconstructed. To do this, Vanish breaks up content into pieces using Shamir secret sharing, distributes these pieces across a p2p network, and depends on sufficiently active churn in the peer-to-peer network to ensure that eventually enough of these pieces will leave the network, and so the original message will be lost forever. Vanish got a nice writeup in the New York Times in July, but the original system has been shown to be vulnerable to a certain type of Sybil attack in this paper.
- Akamai is a company with a billion dollar market cap that enables Internet content and application delivery. As I understand it, the “peers” in the Akamai system are actually companies; and the Akamai network ensures robust and efficient delivery of content from these “peers” to end users. This paper is what enabled Akamai to get its first round of VC funding, I hear. But, I’m not sure if the algorithms now used still have any connection to the paper.
- Skype is a peer-to-peer system for voice calls over the Internet that I used a lot when I was on sabbatical in Europe. In my experience, the voice quality and reliability of google chat was much better than Skype, but somehow it was much easier for us to get friends and family to use skype than google chat. I still use Skype nowadays for research conference calls.
- Bittorrent is a p2p system allowing for quick collaborative downloading of large data items. Estimates are that it consumes about one quarter to one half of all traffic on the Internet. Don’t know how much of this traffic is “legitimate”, but at least some portion of bittorrent bandwidth has been used by publishers for distribution of free music, TV shows, and software. Vuze is a bittorrent client with over 1 million users: clearly a well-used network, and perhaps the largest overlay network on the Internet.
The following parody of Jorge Luis Borges is from McSweeney’s, an excellent literary/humor website. You need to read at least some Borges to appreciate the humor, which you absolutely should do if you’re interested in literature with a mathematical bent. Let me recommend starting with the short story The Library of Babel. There’s an entire book based on this short story called The Unimaginable Mathematics of Borges Library of Babel.
BORGES TEACHES SELF-DEFENSE by Susan Schorn
Those who write of self-defense inevitably fail to celebrate the mysterious and the multiple. These scribes imagine safety to be a litany of banal proscriptions: do not go out alone in the evening, avoid eye contact with strangers, carry always in your mind an image of Shakespeare riding a lamed horse. Such writers commit a deplorable error, for to place one’s hope for safety in changeless things is the fallacy of realism and the unspoken goal of pepper-spray manufacturers. Instead, one correctly perceives safety in the fabrication of new and undreamt paths, paths engendered by the laborious placement of one’s feet somewhere in the world, in any world, of the many divergent and proliferating worlds in which one may be harassed or assaulted. From one’s stance may spring any and all actions. To slouch or lean, then; to stand less than heroically—these things usurp the power of the omnipotent stance. Wearing high heels does not help, either. Flats are more stable and better for one’s ankles.
Let us enumerate, then, the multiplicity of places where the human form is vulnerable: The eyes. The soft tissue of the throat. The nose and the glabrous upper lip. The fingers, astoundingly fragile and exposed. The groin. The absurd knee, notoriously false. The toes. Note also the curious paradox of these targets’ coexistence with the myriad uncounted bodily weapons: The elbow. The fingernails. The front of the first two knuckles of the right hand. The heel of the foot. The arcing curve of the back of the skull. The base of the palm. The teeth, if one is not overly squeamish. The possible combinations of these weapons against the human frailties are numberless.
Now we shall role-play one or two.
Imagine that in the year 1934 you are returning from your friend Carolus Ernst’s house, where you have been engaged in a fierce and discordant dispute concerning a corrupt translation of Herodotus from a Persian manuscript. Suddenly, near some undocumented alleyway, a tall, sharp-featured stranger with gray eyes approaches and seizes you by the left wrist. Time stops, revealing its irrefutable triviality. Expanding outward from this attack are illimitable, inexhaustible responses.
Here is a practical three-part strategy that I recommend: You will strike this attacker in the throat with the hardest weapon available to you. Perhaps it is an elbow. Perhaps it is an 1847 edition of The Encyclopedia of Celestial Navigation. Perhaps it is a small, strange bird of infinite plumage, or a monstrous iron implement once used to prod the sacred tortoise in the savage jungles of Uln. Perhaps it is all these things. It depends, ultimately, on your inclination and talents, and also on the size of the purse one carries. Decidedly, you must also raise an alarm. As you strike, you voice words of opprobrium; you issue a polemic against the imprisonment of wrists; you invent a language spoken only by those who struggle for the free movement of their left arm. One might say, for example, “No,” or “Let go of me,” or, conceivably, “Look at the moon, rising above the pyramids.”
After striking, you will rotate your seized hand radially about the axis of your attacker’s forearm, effecting the negation of his grip by virtue of the thumb’s fallibility. The attacker, stunned by your articulation, and rendered breathless by the crushing of his larynx, steps back from you as if seeing 500 red-tinged angels descending an ebony staircase. Now run.
Very good. I reverently applaud your efforts.
Conceivably, one does not wish to strike the assailant. This may be due to an excess of compassion, or to impenetrable melancholy, or to obscure religious commitments. In the mirrors of possibility, many reactions are reflected. Other corridors of action extend, any one of which you may travel. You may choose, instead of fighting, to pray, to declare yourself invisible, to recite the 13 lamentations of Ramón Beckjord, to feign idiocy, to utter mystical predictions concerning nameless men in three anonymous cities. All responses are valid. It is a good idea to practice them at home when you can; this builds confidence.
I had planned to end our session today with a parable about a tiger and a nightingale, but I see we are out of time.
Filed under: Uncategorized | Tags: algorithms, cryptography, election, leader election, security, theory, Uri Feige
“Whenever a man has cast a longing eye on offices, a rottenness begins in his conduct.” ~Thomas Jefferson
I want to continue my occasional series about consensus today by talking about leader election. Actually, it’s going to be the problem of “committee election”, or as it is referred to more fancily, universe reduction. The problem is basically this: you have a collection of n people, some hidden fraction of which are bad, and you want to elect a small committee of the people such that the fraction of bad people in the committee is not much more than the fraction of bad people in the general population. The problem is complicated by the fact that there is no trusted outside party that can be used to, e.g. count up all the votes. Instead, the problem needs to be solved just through direct communication among the players. We’ll assume everyone has synchronized clocks and, moreover, that there is a way to broadcast a message to everyone (i.e. a consensus algorithm).
We’ll be interested in the very challenging case where the bad guys are computationally unbounded, i.e. no cryptography! Why do we torture ourselves like this? Well there are a few reasons. First, the intellectual interest in determining exactly what is and is not possible with cryptographic assumptions. Second, the practical problem of maybe avoiding some of the computational overhead associated with cryptography e.g. setting up a PKI. Finally, the desire to avoid assumptions about the “hardness” of certain problems, assumptions that may in the end not wind up not being completely correct.
In FOCS 1999, Uri Feige proposed a very clever solution to the committee election problem in his paper “Non-cryptographic Selection Protocols”. I’m going to simplify the algorithm a bit to make it blog friendly. So here’s the setup: we have n people, a hidden fraction of whom are bad and we want to elect a committee of these people such that the fraction of bad people in the committee is not much more than the fraction of bad in the general population. Here’s the algorithm: we put everyone up on a ledge and we put a certain number of large bins under the ledge. Each person then must jump into a bin. We tell the good guys to choose their bins independently and uniformly at random. Then, once everyone has jumped (we give them a fixed amount of time to do so), we take the bin with the smallest number of people in it and select these people as the winners. The rest of the bins are carted off to the politician recycling center.
Why should this work? We have no control over what the bad guys do, and moreover we assume they are omniscient and can secretly collude. Thus, we can expect the bad guys to hem and haw standing on the ledge until all the good guys have jumped, and then carefully decide amongst themselves what bins to jump into in order to try to throw the election. Except it turns out that there’s really nothing much they can do. Assume there are x bins and n people and that t of those people are bad. Then the expected number of good people jumping in each bin is (n-t)/x. Moreover, if x is chosen carefully, we can show that with high probability, the number of good people in every bin is very closely concentrated around the expected value[1]. But then what is the worst the bad people can do? The chosen bin will certainly have no more than n/x people in it. Thus, the chosen bin will have a fraction of good people in it that is very close to the fraction of good people in the general population.
So that’s the idea. Cool no? Much of the technical challenge of Feige’s paper is showing how you can extend this idea to choose a single leader, so that this leader has probability of being bad no more than a fixed constant. The paper is a good read so I won’t reveal any of the details of how to do this. Also I want to point out that Feige’s algorithm is a critical tool in many of the modern consensus algorithms. But doesn’t his algorithm require a consensus algorithm in order to announce bin choices for each person? Yes, the trick is to use his algorithm among small groups where consensus is not that costly and then to create a kind of tournament network to eventually elect a very small representative group after running many election protocols in parallel.
[1] For example, let t = n/3 and x = n/(log n). Then Chernoff bounds and a union bound show that with probability that goes to 1 as n gets large, the number of good players in every bin is between (1-epsilon) and (1+epsilon) times (2/3)log n.
Filed under: Uncategorized | Tags: conferences, game theory, Rome, WINE
As reported here, Accepted papers for WINE 2009 (Workshop on Internet & Network Economics) are now up on the workshop web page. My paper Fear in Mediation: Exploiting the Windfall of Malice , that I’d previously blogged about here, was accepted, so I’m looking forward to taking another trip out to Rome. Amazingly, this will be my 3rd trip to Rome this year. Clearly I need to stop throwing so many coins into Trevi fountain!
Filed under: Uncategorized | Tags: enigma, grid computing, nazis, volunteer computing
Do your part at Enigma@Home
